- Each node object must hold at least two pieces of information.
- the node must contain the list item itself (i.e. data field).
- each node must hold a reference to the next node.
-
Traverse a linked list
node = root while node: print(node.val) node = node.next
-
When we talk about linked list, we are normally talk about singly linked list. There is also a Doubly Linked list defined as follows:
class Node def __init__(self, val): self.val = val self.prev = None self.next = None
-
Linked list in-place operation can be confusing (i.e. insert or delete), its better to draw the structure and it'll become much more obvious
For example when deleting a node in the middle :
node = self.get_node(index) prev_node = node.prev next_node = node.next prev_node.next = next_node next_node.prev = prev_node
-
Its better to use a Dummy head most of time, especially when deleting node is required
For example:
def linked_list(root): dummy = Node("x") dummy.next = root # Do your logic here return dummy.next
-
In many cases, you need to track the previous node of the current node.
dummy = Node("x") dummy.next = root prev = dummy node = head while node: prev = node node = node.next
-
Two pointer approach is widely used in linked list, such as detecting cycle, remove n-th node etc
For example when detecting cycle:
def hasCycle(self, head: ListNode) -> bool: slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False
-
It is common to use Hashmap or hashset to store visited nodes, its widely use to find intersection or beginning of cyclic linked list
def detectCycle(self, head: ListNode) -> ListNode: visited = set() while head: if head.next in visited: return head.next visited.add(head) head = head.next return
Here is a great comparison of time complexity between the linked list and the array from Leetcode.
Reference:
Practice: