List: Linked List Implementation
Explore how linked lists work with dynamic node management, pointer manipulation, and sequential access patterns. Understanding the foundation of many advanced data structures.
Interactive Operations
Dynamic Nodes
O(n) Access
Linked List Visualization
HEAD
Empty List
Size: 0
Memory: Dynamic allocation (node-based)
Head: NULL
Current Step:
Select an operation to begin visualization
Complexity Analysis
O(n)
Access
O(n)
Insert/Delete
O(n)
Search
O(1)*
Head Insert*
O(n) Space
Dynamic allocation + pointer overhead
*Operations at head are O(1), others require traversal
Operations
Insert
Create node, traverse to position, update pointers
Delete
Traverse to position, update pointers, deallocate
Access
Sequential traversal from head to index
Search
Linear traversal comparing values
vs Array Implementation
Advantages
• O(1) insertion/deletion at head
• Dynamic size (no capacity limit)
• Memory efficient (allocate as needed)
• No shifting required for insertions
Disadvantages
• O(n) random access by index
• Extra memory for pointers
• Poor cache locality
• No direct indexing benefits
Traversal Patterns
• Sequential Access: Follow next pointers from head
• No Random Access: Must traverse to reach any index
• Forward Only: Standard singly-linked list
• Termination: Stop when next pointer is NULL
• Index Tracking: Manual counting during traversal
Applications
• Memory Pools: Dynamic memory management
• Music Playlists: Sequential playback
• Undo Systems: Action history chains
• Sparse Data: Representing non-contiguous data
• Graph Adjacency: Edge lists in graph representations
Implementation
class Node:
def __init__(self, value):
self.value = value # Data stored in the node
self.next = None # Reference to next node
class LinkedList:
def __init__(self):
self.head = None # Reference to first node
self.size = 0 # Track number of elements
def insert(self, index, value):
# Validate index
if index < 0 or index > self.size:
raise IndexError("Index out of bounds")
# Create new node
new_node = Node(value)
if index == 0:
# Insert at head
new_node.next = self.head
self.head = new_node
else:
# Traverse to position before insertion
current = self.head
for i in range(index - 1):
current = current.next
# Insert the node
new_node.next = current.next
current.next = new_node
self.size += 1
def delete(self, index):
# Validate index
if index < 0 or index >= self.size:
raise IndexError("Index out of bounds")
if index == 0:
# Delete head
value = self.head.value
self.head = self.head.next
else:
# Traverse to position before deletion
current = self.head
for i in range(index - 1):
current = current.next
# Get value and update pointer
value = current.next.value
current.next = current.next.next
self.size -= 1
return value
def search(self, value):
# Linear search through the list
current = self.head
index = 0
while current:
if current.value == value:
return index
current = current.next
index += 1
return -1 # Not found
def access(self, index):
# Validate index
if index < 0 or index >= self.size:
raise IndexError("Index out of bounds")
# Traverse to the index
current = self.head
for i in range(index):
current = current.next
return current.value
def append(self, value):
# Insert at the end
self.insert(self.size, value)
def prepend(self, value):
# Insert at the beginning
self.insert(0, value)
def get_size(self):
return self.size
def display(self):
# Return list of all elements
elements = []
current = self.head
while current:
elements.append(current.value)
current = current.next
return elements