DSA Linked Lists
A linked list stores a sequence of elements as separate nodes that point to one another, trading random access for cheap insertion and removal.
What Is a Linked List?
A linked list is a linear data structure made of nodes. Each node holds a piece of data and a reference, or pointer, to the next node in the sequence. The list itself only needs to remember the head, the first node, because every other node can be reached by following next pointers one at a time.
Linked Lists vs. Arrays
Arrays store elements in one contiguous block of memory, so you can jump straight to any index in constant time, but inserting or removing an element in the middle requires shifting every element after it. Linked lists scatter their nodes across memory and connect them with pointers, so inserting or removing a node is a constant-time operation once you already hold a reference to it, but reaching the nth node requires walking the list one step at a time from the head.
- Node: a container holding a value and a pointer to the next node (and, in a doubly linked list, a pointer to the previous node too).
- Head: a reference to the first node in the list; an empty list has a head of None.
- Tail: the last node in the list, whose next pointer is None, marking the end of the chain.
- Singly linked list: each node points only to its successor, so traversal only moves forward.
- Doubly linked list: each node points to both its successor and its predecessor, allowing traversal in either direction.
Example
class Node:
def __init__(self, value):
self.value = value
self.next = None
# Build the list 10 -> 20 -> 30 manually
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
print(head.value, head.next.value, head.next.next.value) # 10 20 30Example
class DoublyNode:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
first = DoublyNode(1)
second = DoublyNode(2)
third = DoublyNode(3)
first.next = second
second.prev = first
second.next = third
third.prev = second
# Walk forward from the head
print(first.next.next.value) # 3
# Walk backward from the tail
print(third.prev.prev.value) # 1When to Choose a Linked List
Example
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
return
current = self.head
while current.next is not None:
current = current.next
current.next = new_node
def __str__(self):
values = []
current = self.head
while current is not None:
values.append(str(current.value))
current = current.next
return " -> ".join(values) + " -> None"
numbers = LinkedList()
numbers.append(1)
numbers.append(2)
numbers.append(3)
print(numbers) # 1 -> 2 -> 3 -> NoneExercise: DSA Linked Lists
What does each node in a singly linked list typically store?
