Algorithm Related to List: Part 1

∘ Introduction
∘ Operations
∘

Introduction

In this article algorithms related to list data structure will be summarized. List is a very common data structure, and people often compare list data structure with array data structure. The major difference between these two data structures lies in the fact that elements in a list are not kept in continuous memory space compared to array data structure. Therefore, array structure is often used in the case where 1) the data items are fixed; 2) data element needs to be required frequently (via index); 3) there is less need to delete some elements in the array.

List can be defined as follows:

class ListNote(object):
  def __init__(self, value, next=None):
    self.value = value
    self.next = next 

Operations

Deletion

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        
        dumpy_value = 10*val if val!=0 else val+10
        
        dumpy_head = ListNode(dumpy_value)
        dumpy_head.next = head 
        
        tmp_ele = dumpy_head 
        pre_ele = None
        while tmp_ele is not None:
            if tmp_ele.val == val:
                pre_ele.next = tmp_ele.next 
            else:
                pre_ele = tmp_ele
            tmp_ele = tmp_ele.next
            
        return dumpy_head.next

• because header needs to be treated carefully if the target value is equal to the value the header has, we use a dummy header
• make sure that dumpy header has a value that is not the same with the target value

Single-link List

class Node:
    
    def __init__(self, val):
        self.val = val
        self.next = None
class MyLinkedList:
def __init__(self):
        self._head = Node(0)  
        self._count = 0
def get(self, index: int) -> int:
        """
        Get the value of the index-th node in the linked list. If the index is invalid, return -1.
        """
        if 0 <= index < self._count:
            node = self._head
            for _ in range(index + 1):
                node = node.next
            return node.val
        else:
            return -1
def addAtHead(self, val: int) -> None:
        """
        Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
        """
        self.addAtIndex(0, val)
def addAtTail(self, val: int) -> None:
        """
        Append a node of value val to the last element of the linked list.
        """
        self.addAtIndex(self._count, val)
def addAtIndex(self, index: int, val: int) -> None:
        """
        Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
        """
        if index<0 or index>self._count:
            return 
        
        self._count += 1
        
        previous_ele, cur_ele = None, self._head
        for i in range(index+1):
            previous_ele, cur_ele = cur_ele, cur_ele.next
        
        new_ele = Node(val)
        new_ele.next = cur_ele
        previous_ele.next = new_ele
def deleteAtIndex(self, index: int) -> None:
        """
        Delete the index-th node in the linked list, if the index is valid.
        """
        if 0 <= index < self._count:
             
            self._count -= 1
            prev_node, current_node = None, self._head
            for _ in range(index + 1):
                prev_node, current_node = current_node, current_node.next
             
            prev_node.next =  current_node.next

Reverse Link List

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        cur=head
        pre=None
        while cur!=None:
            temp = cur.next
            cur.next = pre
            pre = cur 
            cur = temp 
            
        return pre