Linked Lists

Lesson 3 · OKSTEM College · AS Computer Science

Singly Linked List

Each node holds a value and a pointer to the next node. The list ends when next is None. No random access — traversal is O(n) — but insertion/deletion at the head is O(1).

class Node: def __init__(self, val): self.val=val; self.next=None class LinkedList: def __init__(self): self.head=None def prepend(self, val): # O(1) node=Node(val); node.next=self.head; self.head=node def append(self, val): # O(n) node=Node(val) if not self.head: self.head=node; return cur=self.head while cur.next: cur=cur.next cur.next=node def delete(self, val): if not self.head: return if self.head.val==val: self.head=self.head.next; return cur=self.head while cur.next and cur.next.val!=val: cur=cur.next if cur.next: cur.next=cur.next.next def to_list(self): res,cur=[],self.head while cur: res.append(cur.val); cur=cur.next return res

Array vs Linked List Trade-offs

Operation	Array	Linked List
Access by index	O(1)	O(n)
Search	O(n)	O(n)
Insert at head	O(n) shift	O(1)
Insert at tail	O(1) amortised	O(n) or O(1) w/ tail ptr
Delete middle	O(n) shift	O(n) find + O(1) remove
Memory	Contiguous, cache-friendly	Scattered, pointer overhead

Doubly Linked List & Sentinel Nodes

Each node also holds a prev pointer, enabling O(1) deletion given the node (no traversal to find the predecessor). Sentinel (dummy) nodes at head and tail eliminate edge cases.

Python’s collections.deque is implemented as a doubly linked list of fixed-size blocks — that’s why both ends are O(1).

Practice

1. Reverse a singly linked list in-place (O(n) time, O(1) space).

def reverse(self): prev, cur = None, self.head while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt self.head = prev

2. Detect a cycle in a linked list (Floyd's algorithm).

def has_cycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: return True return False # Slow moves 1 step, fast moves 2 — they meet iff a cycle exists.

Knowledge Check

Linked list prepend (insert at head) is

Correct — update two pointers: new.next = head, head = new.

No traversal needed for head insertion.

No divide-and-conquer step.

Irrelevant here.

Recap: prepend = set new.next = old head, then head = new. Two pointer assignments regardless of list size.

The main advantage of arrays over linked lists is

Array front insertion is O(n) due to shifting.

Correct — arrays use direct addressing: address = base + i × element_size.

Arrays are compact; linked lists add a pointer per node. But arrays may over-allocate.

Arrays also need O(n) shifting after deletion.

Recap: array strength = O(1) index access. Linked list strength = O(1) head insert/delete without shifting.

Floyd's cycle detection uses

That's valid but O(n) space. Floyd's is O(1) space.

Correct — slow moves 1 step, fast moves 2. They meet iff there's a cycle.

That destroys the list structure.

Counting can't detect a cycle (would loop forever).

Recap: Floyd's tortoise-and-hare. O(n) time, O(1) space. If fast ever catches slow, there's a cycle.

Deleting a node from the middle of a doubly linked list given a pointer to it is

With a direct pointer and prev/next pointers, no traversal needed.

Correct — four pointer updates, no traversal.

No binary search involved.

It's one of the key advantages of doubly linked lists.

Recap: doubly linked delete = node.prev.next = node.next; node.next.prev = node.prev. Four lines, O(1). This is why LRU Cache uses a doubly linked list.

A sentinel (dummy) head node helps because

Sentinels don't store length by default.

Correct — head deletion becomes a normal middle deletion since sentinel is always present.

Linked lists never have O(1) random access regardless of sentinels.

Sentinels add one node — they don't save memory.

Recap: sentinel = dummy node that never holds real data. head.next is the first real element. Simplifies insert/delete logic by removing nil-head edge cases.

← Previous Next →