## Remarks

• Linked List is a sequence of node objects where each node store pointers to
1. some other node in the sequence
2. the data this node is associated with
• Linked List can be used as the underline data structure for many common abstract data types like lists, stacks, queues, etc.
operation time
push at front O(1)
pop at front O(1)
push at back O(1)
pop at back O(N)
access via index O(N)
insert in middle O(N)
delete in middle O(N)
swap two nodes O(N)

## Common operations on singly linked list.

### 1 Node class for singly linked list.

class ListNode:
def __init__(self, item: Optional=None):
self.item = item
self.next = None

def __repr__(self) -> str:
return f"{super().__repr__()[:-1]} of {self.item} >"

nodes = list(map(ListNode, ['Head', 'Shoulders', 'Knees', 'Toes']))
for prev, next_ in zip(nodes, nodes[1:]):
prev.next = next_

tail = nodes[-1]
del nodes


### 2 Traverse the linked list.

def traverse(head: ListNode, verbose: int=0) -> tuple[ListNode, int]:
n = 0
while curr:
if verbose: print(curr.item)
if not curr.next: tail = curr
curr = curr.next
n += 1
return tail, n

# def traverse(head, k):
# def traverse(head, val):

assert traverse(head) == (tail, 4)


### 3 Push and pop node at front.

def push_front(head, node):
return node

node = ListNode('Hat')
assert head == node and traverse(head)[1] == 5

assert head == node.next and traverse(head)[1] == 4


### 4 Push and pop node at back.

def push_back(tail, node):
tail.next = node
return node

while curr.next is not tail: curr = curr.next
curr.next = None
tail = curr
return tail

node = ListNode('Shoes')
tail = push_back(tail, node)
assert tail == node and traverse(head)[1] == 5

tail = pop_back(head, tail)
assert traverse(head)[1] == 4 and tail.next == None


### 5 Insert and delete nodes in the middle.

def get(head, i):
prev = None
while curr and i:
i -= 1
prev = curr
curr = curr.next
return prev, curr

def insert(head, i, node):
prev, next_ = get(head, i)
prev.next = node
node.next = next_

prev, curr = get(head, i)
prev.next = curr.next

node = ListNode('Belly Button')
assert get(head, 2)[1] == node and traverse(head)[1] == 5

assert get(head, 2)[1] == node.next and traverse(head)[1] == 4


### 6 Swap nodes.

def swap(head, i, j):
i, j = sorted([i, j])
prev_i, node_i = get(head, i)
prev_j, node_j = get(node_i, j-i)

if prev_i:
prev_i.next = node_j
else:

prev_j.next = node_i
node_i.next, node_j.next = node_j.next, node_i.next



### 7 Reverse Linked List.

def reverse(head):
prev = None
while trav: trav.next, prev, trav = prev, trav, trav.next
return prev


## Common Problems

1. Two Pointers
1. left, right - Palindrome
2. slow, fast - cycle, last k
2. Multiple Lists
1. Merge, Intersection
3. Search and Sorting
4. Implement Stack/Queue/Deque etc.
5. Doubly Linked List + Hash Table