Linked lists are the first data structure most developers implement themselves, and understanding when they actually beat an array (genuinely rare in modern high-level languages) is more valuable than the implementation itself.
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def prepend(self, value):
node = Node(value)
node.next = self.head
self.head = node # O(1) - no shifting needed, unlike array insertion at index 0
def find(self, value):
current = self.head
while current:
if current.value == value:
return current
current = current.next
return None # O(n) - no random access, must walk from the head
Arrays vs Linked Lists
- Arrays — O(1) random access, but O(n) insertion/deletion in the middle (everything shifts)
- Linked lists — O(1) insertion/deletion once you have a reference to the node, but O(n) access (no indexing, must walk from the head)
In practice, modern CPU cache behavior favors arrays heavily even for insertion-heavy workloads, since contiguous memory access is dramatically faster than following pointers scattered across memory — linked lists remain genuinely useful mainly for specific structures (LRU caches, certain queue implementations) rather than as a general-purpose default.