What is a Linked List?
A linked list is a series of nodes linked together in a linear sequence. Linked lists are a null-terminated data structure, meaning the final node points to null.
This guide walks you through everything you need to know about the linked list data structure, with clear, commented code samples.
- When to use a linked list
- Big O time complexity of operations
- Singly linked lists
- Implement a singly linked list in Python
- Doubly linked lists
- Singly vs. doubly linked lists
- Solving linked list problems
- Sample linked list problems
When to Use a Linked List
To understand when to use a linked list, we must understand its structure. There is order to a linked list, unlike hash tables, which means they should be considered when a problem requires the preservation of element order.
Adding and deleting from the start of a singly linked list can also be done in constant time O(1), but search is slower, at O(n). Therefore, if we need to access specific items on a regular basis, arrays may be a better option, as the time complexity to access their items is O(1).
Main advantages over arrays:
- Lets you insert to the middle using pointers
- Only change that happens is in the middle. Same for deletes
- These are faster operations than inserts and deletes in arrays, which can require shifting. O(n)
- Static arrays also only have a certain amount of memory allocation. They can double in size when the limit is reached, but costs O(n)
Big O Time Complexity of Operations
- Prepend: O(1)
- Append: O(1)
- Lookup: O(n)
- Insert: O(n)
- Delete: O(n)
Singly Linked Lists
Each node is represented as a unique object. A node stores two references, one being its data and the other being a pointer to the next node (or None, if node is the tail).
In a linked list, the first node is called the head and the last node is called the tail. The tail can be identified by its pointer to null.
Pros
- O(1) time complexity to add an element at either end, provided you maintain a reference to the tail.
- O(1) time complexity to remove the first element. Arrays require O(n) time (to shift items around).
- Can expand without specifying its size ahead of time.
Cons
- Slow lookup. O(k) time to go from the head of the list to the kth element for access. Arrays have O(1) constant time for access.
Implement Singly Linked List in Python
To create a linked list, you’ll typically create a class for the Node, and a separate class for the list operations.
A basic implementation of the Node class:
class Node:
def __init__(self, data):
self.data= data
self.next = None
You can create a linked list by instantiating multiple nodes, then pointing them to each other by setting their next attribute.
For example, a linked list of a -> b -> c -> null could be implemented as follows:
a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c
print(a.value) # 1
print(a.next.data) # 2
A more complete implementation of a singly linked list class can be found below. This includes the following operations:
- prepend: Add a new node at the start of the linked list, which becomes the new head.
- append: Add a new node at the end of the linked list, which becomes the new tail.
- traverse: Loop through the linked list and print the data stored at each node.
- get_head: Retrieve a reference to the current head node.
- is_empty: Check if the linked list contains any nodes.
- clear: Clears a linked list by setting its head to
None. - reverse: Reverse the linked list in place, given a reference to its head node.
class Node:
def __init__(self, data):
"""
Attributes:
data: The data to be contained within the node.
next: Pointer reference to the next node in the list.
"""
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
"""
Attributes:
head: Pointer to the head of the linked list.
"""
self.head = None
def prepend(self, val):
"""Insert a new node at the head of the linked list.
Args:
val: The value being added to the linked list.
"""
newNode = Node(val)
if self.head is None:
self.head = newNode
else:
newNode.next = self.head
self.head = newNode
def append(self, val):
"""Insert a new node at the tail of the linked list.
Args:
val: The value being added to the linked list.
"""
if self.head is None:
self.head = Node(val)
else:
node = self.head
while node.next:
node = node.next
node.next = Node(val)
def traverse(self):
"""
Traverse the linked list and print its data.
"""
node = self.head
while node:
print(node.data)
node = node.next
def get_head(self):
"""Get the head of the linked list.
Returns:
A reference to the current head node.
"""
return self.head
def is_empty(self):
"""Checks if the linked list contains nodes.
Returns:
True if nodes in list, otherwise False.
"""
if(self.head is None):
return True
else:
return False
def clear(self):
"""
Clears a linked list, removing all nodes.
"""
self.head = None
def reverse(self):
"""
Reverses a linked list in place.
"""
previous = None
current = self.head
while current:
nextnode = current.next
current.next = previous
previous = current
current = nextnode
self.head = previous
Delete Node from Singly Linked List
To delete a node from a singly linked list can be more complex than simple operations such as search and append.
Deleting from the head is simple enough. You simply repoint the head reference to the next node.
But what if we’re asked to delete a given node? How do we repoint the node that points to it, when we can only move forwards using node.next?
Case 1: Given only the node to delete
def delete_node(node):
# Get the input node's next node, the one we want to skip to
next_node = node.next
if next_node:
# Set the input node's value and pointer to be the next node's value and pointer.
node.value = next_node.value
node.next = next_node.next
else:
raise Exception("Can't delete the last node with this technique!")
Trade-offs:
- Doesn’t work for deleting the last node in the list.
Side Effects:
- References to the input node now effectively reference its next node
- Pointers to the input node’s original next node are now pointing to an unconnected node
Big O Complexity:
O(1) time and O(1) space.
Case 2: Given the node and the full list
Given node ‘n’, find the previous node ‘prev’ and set ‘prev.next’ equal to ‘n.next’.
If the list is doubly linked, also update ‘n.next’ to set ‘n.next.prev’ equal to ‘n.prev’.
Important: Check for the null pointer, and update the head or tail pointer as necessary.
Case 3: Given the index of a node
Add ‘length’ attribute to the SinglyLinkedList class __init__, to make checks easier. Iterate through the linked list until you find an index that matches the input, then perform the same steps that you would to solve Case 2.
Doubly Linked Lists
Each node stores three references:
- Pointer to the previous node (or None, if node is the head)
- Its data
- Pointer to the next node (or None, if node is the tail)
Implement Doubly Linked List in Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.prev = a
b.next = c
c.prev = b
print(b.value) # 2
print(b.prev.data) # 1
print(b.next.data) # 3
Singly vs. Doubly Linked Lists
Singly Linked List
- Require less memory (don’t have to store pointer to previous element) and simpler to implement
- Downside is they cannot be traversed in reverse
- Good when fast insertion and deletion is goal, and memory should be preserved
Doubly Linked List
- Better when searching
- Downside is requires more memory and more complex
- Good when less limitation on memory
Solving Linked List Problems
The ‘Runner’ Technique
Iterate through the linked list with two pointers, simultaneously, with one ahead of the other.
The ‘fast’ pointer can be ahead by a fixed amount, or hop multiple nodes for each one node the ‘slow’ pointer increments through.
e.g. Have one pointer p1 (fast) move two elements for every one move that p2 (slow) makes. When p1 hits the end of the linked list, p2 is at the midpoint.
Analogy:
Two runners. If runner1 starts on a straight track ahead of runner2, they should never meet. If he starts ahead of runner2 but is on a loop, they will eventually meet.
Sample Linked List Problems
Problem 1:
Write a function to reverse a Linked List in place. The function will take in the head of the list as input and return the new head of the list.
We can reverse the list by changing the next pointer of each node. Each node’s next pointer should point to the previous node.
In one pass from head to tail of our input list, we will point each node’s next pointer to the previous element.
Make sure to copy current.next_node into next_node before setting current.next_node to previous.
Solution 1:
def reverse(head):
"""
Reverses a linked list in place.
"""
previous = None
current = head
while current:
nextnode = current.next
current.next = previous
previous = current
current = nextnode
self.head = previous
Problem 2:
Given a singly-linked list, check if it contains a cycle.
Solution 2a: Hash map technique
Big O Complexity: O(n) time. O(n) space.
def contains_cycle(node):
dict1 = {}
while node:
if node not in dict1:
dict1[node] = 1
else:
return True
node = node.next
return False
Solution 2b: Runner technique
Big O Complexity: O(n) time. O(1) space.
def contains_cycle2(node):
slow = node
fast = node
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
