An Introduction to Linked List Data Structures
Linked lists are one of the fundamental linear data structures alongside stacks, queues, arrays, and lists.
A linked list is a continuous list of nodes where a node is a block structure housing the node value and a pointer (or memory) address to the next node. Each node from the head node has a next
pointer that keeps the address of the next node till it gets to the last node, which points to nothing.
Linked lists are used in web browsers to keep track of web pages visited and moves in multi-player board games. Linked lists also find usage in implementing other linear data structures and graphs, dynamic memory allocation, and performing arithmetic operations on long integers.
The connection from one node to another node differentiates linked lists from a regular list or array. Unlike the linked lists, arrays don’t keep track of their next or other values.
Here is a visual representation of a linked list:
Types of Linked Lists
The last node always points to NULL, except for circular linked lists.
Types of Linked Lists
There are three types of linked lists:
- Singly-linked list
- Doubly linked list
- Circular linked list
You can derive other linked lists from the basic ones, e.g., circular doubly linked lists. This article teaches you how to implement the singly and doubly linked list and briefly discusses the circular linked list.
💡 In this article, we’ll use the Python programming language for the implementations.
Singly-linked list
You’re tasked with building a tool to retrieve documents connected to each other but stored at random memory locations. You’re puzzled as to what data structure to use to fit this use case, as arrays store documents sequentially. The good news is that you can use the singly linked list for this task.
A singly linked list is defined by its node. A singly linked list node has a value and the next pointer. The diagram below is an example of a singly linked list.
To implement the linked list, start with the node class:
class Node:
def __init__(self, value) -> None:
self.value = value
self.next = None
Code language: Python (python)
In the code block above, the node class comprises two attributes:
value
: The value to be stored in the node.next
: The pointer address to the next node. It has a default value of None ( NULL ).
Next, you need to implement the linked list class.
The linked list class
The linked list class is a wrapper for adding methods for node operations, such as appending a node, prepending a node, and deleting a node. Let’s say you want to append a node to the middle of a long chain of nodes. Doing so manually would look like this:
nodes = Node(10)
nodes.next = Node(11)
nodes.next.next = Node(13)
nodes.next.next.next = Node(14)
# Insert a new node after 11.
new_node = Node(12)
new_node.next = nodes.next.next
nodes.next.next = new_node
Code language: Python (python)
The process above is stressful. In a scenario where you need to perform this same operation for a couple of nodes, say 10, you have to do this manually every time. This operation brings forth unnecessary code bulkiness and complexity – known as space complexity. Having a linked list class with a method solves this all.
ℹ️ Each new variable defined in a program takes a significant amount of space. For example, a node costs 48 bytes of space, and a thousand nodes will cost 48000 bytes. Each time the program is executed, this amount of space is used for a single node initialization operation ignoring the internal space used by the linked list methods. Not only does this extra space slow down your application, but it also impacts the planet via poor eco-design.
The linked list class is independent. The LinkedList
class implementation is:
class LinkedList:
def __init__(self) -> None:
self.head = None
self.tail = None
Self.size = 0
Code language: Python (python)
In the code block above, the linked list class comprises three attributes:
head
: The head of the linked list, which is the first node.tail
: The tail of the linked list, which is the last node.size
: The size of the linked list.
Singly-linked list operations
The primary operations of a singly linked list include:
- Traversal
- Insertion
- Deletion
To perform the operations mentioned above, you need to define the methods under the linked list class.
Before you begin to implement the primary operations, however, you will need to implement the __len__
method in the LinkedList
class to return the length of your linked list stored in the self.size
variable:
def __len__(self) -> int:
return self.size
Code language: PHP (php)
With the __len__
method implemented, you can return the size of the linked list with len(linkedlist)
.
Traversal
In simple words, traversal is a process of accessing elements stored in an object. A traversal operation is executed to print the elements in a linked list.
Let’s implement our first method, __str__
, to print out the elements in the linked list:
def __str__(self) -> str:
linkedlist = ""
current = self.head
while current and current.next is not None:
linkedlist += str(current.value) + "->"
current = current.next
linkedlist += str(current.value)
return linkedlist
Code language: Python (python)
The __str__
method in Python returns the string representation of an object. This method returns the node values in your linked list as a string separated by ->
.
Insertion
The insertion operation enables you to add nodes to your linked list. You can add nodes to your linked list by prepending the node, appending the node, or by adding nodes at specific positions in the linked list.
Prepending a node
The prepend method adds a new node at the head of the linked list, making it the new head node. The previous head node is automatically set as the next node after the new node.
Implement the prepend method in the LinkedList
class:
def prepend(self, element) -> None:
new_node = Node(element)
new_node.next = self.head
self.head = new_node
if self.tail == None:
self.tail = self.head
self.size += 1
Code language: Python (python)
In the code block above, the prepend
method takes an argument element
, which is, in turn, passed to the Node
class to form a node new_node
. The new_node
has its next pointer set to the head of the linked list self.head
, and the linked list’s head node also points to the new node created.
The method then checks if the tail of the linked list does not exist; if the tail doesn’t exist, it is set to the value of the head node.
Lastly, the method increments the size of the linked list.
Appending a node
The append
method adds a new node to the end of the linked list. This method traverses the linked list until the next node pointer points to None
– signifying the end of the linked list. The new node is attached to the tail’s node pointer, and the size of the linked list is incremented.
Implement the method in the linked list class:
def append(self, element) -> None:
node = self.head
while node.next != None:
node = node.next
node.next = Node(element)
self.tail = node.next
self.size += 1
Code language: Python (python)
Appending at a specific position
The last insertion operation is to append at a specific position. In this operation, a new node is added to the position specified. For example, if the linked list has four values, you can insert a new node at the third position. The node in the second position will have its next pointer pointing at the new node, and the new node points at the node originally in the third position.
In the LinkedList
class, add the method:
def add_at_position(self, position, element) -> None:
if position < 1 or position > self.size:
raise IndexError("Position is invalid")
if position == 1:
self.prepend(element)
return
index = 1
prev = None
current = self.head
new_node = Node(element)
while index != position:
index += 1
prev = current
current = current.next
prev.next = new_node
new_node.next = current
self.size += 1
Code language: Python (python)
With the insertion methods in place, create a new linked list and perform some operations:
ll = LinkedList()
ll.prepend(40)
ll.append(50)
ll.add_at_position(2, 45)
print(len(ll)) # 3
print(ll) # 40 -> 45 -> 50
Code language: Python (python)
Deletion
The deletion operation involves removing a node from the linked list either from the head, tail or at a specified position. Implement the method for this operation in the LinkedList
class:
def delete_node(self, position) -> None:
if position < 1 or position > self.size:
raise IndexError("Invalid position!")
if position == 1:
self.head = self.head.next
return
if position == self.size:
prev = None
current = self.head
while current.next is not None:
prev = current
current = current.next
prev.next = None
self.tail = prev
self.size -= 1
return
# Position specified isn't head nor tail.
index = 1
prev = None
current = self.head
while index != position:
index += 1
prev = current
current = current.next
prev.next = current.next
self.size -= 1
return current.element
Code language: Python (python)
In the code block above, the delete_node
function performs three delete operations:
- Deleting the head node: If the position specified is 1, the head node is deleted by setting the value of the head node to the second node in the linked list.
- Deleting the tail node: If the position specified equals the number of nodes present in the linked list, the linked list is traversed to the end, and the second to the last node’s pointer is set to
None
to eliminate the tail node. - Deleting a different node: If the position doesn’t match the head or tail nodes, the linked list is traversed until the specified position is reached. The node preceding the node at the specified position will have its next pointer set to the node located after the deleted node.
All of the operations above decrease the size of the linked list. An IndexError
will be returned if a wrong position is passed to the method.
If you delete the second node you created earlier, the new linked list will be:
ll.delete_node(2)
print(ll, len(ll)) # Prints 40 -> 50, 2
Code language: Python (python)
Doubly linked list
You’re tasked with implementing a new feature in a multiplayer board game (chess, checkers, tic-tac-toe, etc.) that enables a user to go back to their previous move. To implement this feature, you’ll likely need to use a doubly linked list data structure.
A doubly linked list has two node pointers—one pointer pointing to the previous node and the other pointing to the next node.
Here is a graphical representation:
To implement a doubly linked list, implement the node class first:
class Node:
def __init__(self, value):
self.value = value
self.previous = None
self.next = None
Code language: Python (python)
The Node
class above comprises three attributes:
value
: The value to be stored in the node.previous
: The pointer address of the previous node.next
: The pointer address of the next node.
The linked list class
The linked list class is a wrapper for adding methods for node operations. The LinkedList
class definition for a doubly linked list is:
class LinkedList:
def __init__(self) -> None:
self.head = None
self.tail = None
self.size = 0
Code language: Python (python)
Doubly linked list operations
Just as before, the primary operations of a doubly linked list include:
- Traversal
- Insertion
- Deletion
To perform the above-mentioned operations, you need to define the methods under the linked list class.
Before you begin to implement the primary operations, implement the __len__
method in the LinkedList
class to return the length of your linked list stored in the self.size
variable:
def __len__(self) -> int:
return self.size
Code language: Python (python)
With the __len__
method implemented, you can return the size of the linked list with len(linkedlist)
.
This should look familiar, because it is the exact same method definition as a singly linked list.
Traversal
Let’s implement our first method, __str__
, to print out the elements in the linked list:
def __str__(self) -> str:
linkedlist = ""
current = self.head
while current and current.next is not None:
linkedlist += str(current.value) + "<->"
current = current.next
linkedlist += str(current.value)
return linkedlist
Code language: Python (python)
In the code block above, the __str__
method will iterate through the linked list and store each node value separated by the delimiter <->
in a variable linkedlist
which is returned when a linked list object is to be printed.
ℹ️ The
__str__
and__len__
methods are the same for all linked lists. The only difference is the delimiter-
> for singly and<->
for the doubly linked list.
Insertion
The insertion operation enables you to add nodes to your linked list either by prepending the node, appending the node, or adding the node at specific positions in the linked list.
Prepending a node
The prepend
method adds a new node at the head of the linked list. Implement the prepend method in the LinkedList
class:
def prepend(self, element) -> None:
new_node = Node(element)
new_node.next = self.head
if self.head is not None:
self.head.previous = new_node
self.head = new_node
if self.tail == None:
self.tail = self.head
self.size += 1
Code language: Python (python)
In the code block above, the method starts by creating a new node, new_node
, with the argument passed to the prepend
method. The method assigns the next pointer to the head node. It then checks if the linked list is not empty and assigns the head node’s previous pointer to the new node.
Once the pointer assignments are complete, the new node is assigned as the new head of the linked list.
Appending a node
The append
method adds a new node to the end of the linked list. This method traverses the linked list until the next node pointer points to None
(the end of the linked list). Once the end of the linked list is reached, the new node is attached to the tail’s node pointer, and the size of the linked list is incremented.
Implement the method in the linked list class:
def append(self, element) -> None:
if self.tail is None:
self.prepend(element)
return
new_node = Node(element)
self.tail.next = new_node
new_node.previous = self.tail
self.tail = new_node
self.size += 1
Code language: Python (python)
In the code block above, the append
method checks if the tail of the linked list is None
. If the tail is None
, the method performs a prepend operation and exits.
However, if the tail exists, a new node is created and its previous pointer is set to the linked list tail node. The tail node as well sets its next pointer to the new node. Once the pointer assignment is completed, the new node is made the new tail by assigning the node to the self.tail
variable.
Appending at a specific position
Linked list nodes can be appended at a specified position. An example is inserting a new node at the fourth position in a linked list with five values.
The node before the position specified will have its next pointer pointing at the new node and its next pointer pointing at the node originally at the position specified.
In the LinkedList
class, add the method:
def add_at_position(self, position, element):
if position < 1 or position > self.size:
raise IndexError("Position is invalid")
if position == 1:
self.prepend(element)
return
index = 1
current = self.head
new_node = Node(element)
while index != position:
index += 1
current = current.next
prev = current.previous
prev.next = new_node
new_node.previous = prev
new_node.next = current
current.previous = new_node
self.size += 1
Code language: Python (python)
In the code block above, the method first checks if the position is valid before proceeding. If the position is invalid, the method returns an IndexError
.
If the position specified is the head node position 1, the method invokes the prepend
method for the insertion. Otherwise, the method traverses the whole linked list until it gets to the position and performs the following:
- The method assigns the preceding node’s next pointer to the new node
- Sets the new node’s previous pointer to the preceding node
- Sets the new node’s next pointer to the current node
- Sets the current node’s previous pointer to the new node
With the insertion methods in place, create a new linked list and perform some operations:
dll = LinkedList()
dll.prepend(40)
dll.prepend(30)
dll.append(50)
dll.add_at_position(1, 10)
print(dll) # 10<->30<->40<->50
Code language: Python (python)
Deletion
The deletion operation removes a node from the linked list either from the head, tail or at a specified position. Implement the method for this operation in the LinkedList
class:
def delete_node(self, position):
if position < 1 or position > self.size:
raise IndexError("Invalid position!")
if position == 1:
node_to_remove = self.head
newHead = self.head.next
node_to_remove.next = None
node_to_remove.previous = None
self.head = newHead
self.size -= 1
return node_to_remove.value
if position == self.size:
node_to_remove = self.tail
new_tail = self.tail.previous
node_to_remove.previous = None
new_tail.next = None
self.tail = new_tail
self.size -= 1
return node_to_remove.value
index = 1
current = self.head
while index != position:
index += 1
current = current.next
prev = current.previous
prev.next = current.next
current.next.previous = prev
self.size -= 1
return current.value
Code language: Python (python)
In the code block above, the delete_node
function performs three delete operations:
- Deleting the head node: If the position specified is 1, the head node is deleted by setting both pointers to
None
, and the second node is assigned the head node. - Deleting the tail node: If the position specified equals the number of nodes present in the linked list, the linked list is traversed to the end, and the second to the last node’s pointer is set to
None
to eliminate the tail node. The outgoing tail node’s pointers are also set toNone
respectively. - Deleting a different node: If the position doesn’t match the head or tail nodes, the linked list is traversed until the specified position is reached. For example, to delete the third node in a 5-value linked list, the second node will have its next pointer pointing to the fourth node, and the fourth node’s previous pointer will now point to the second node.The node preceding the node at the position will have its next pointer set to the node of the next pointer of the node to be deleted. The next pointer after the node to be deleted will have its previous pointer pointing to the node preceding the current node to be deleted.
All of the operations above decrease the size of the linked list. An IndexError
will be returned if a wrong position is passed to the method.
If you delete the second node you created earlier, the new linked list will be:
dll.delete_node(2)
print(dll) # 10<->40<->50
Code language: Python (python)
Circular linked lists
Circular linked lists are singly linked lists except that their last node points to the first node as opposed to None. As a result, the circular linked list does not have a tail node. Circular linked lists are commonly used to manage computing resources.
The circular linked list shares the same logic for insertion, traversal, and deletion as the singly linked list with the only difference being the assignment of the last node’s next pointer to the head node.
For example, the append method for the circular linked list is:
def prepend(self, value):
cur = self.head
new_node = Node(value)
new_node.next = self.head
if not self.head:
new_node.next = new_node
else:
while cur.next != self.head:
cur = cur.next
cur.next = new_node
self.head = new_node
Code language: PHP (php)
In the code block above, the prepend
method first checks if the head node is not present in the linked list. If there’s no head node, the new node’s next pointer is set to itself, creating a circle.
The circular linked list is implemented in the sandbox below to avoid repeating the implementation of the singular linked list.
Try it out in the CoderPad sandbox!
In this article, you have learned what linked lists are and how to implement singly and doubly linked lists. You can play with the sandboxes beneath this section to test the method you learned as well as implement new methods – the Coderpad Sandbox is an interactive sandbox for peer coding, live coding, and interviews.
Want more challenges? Create a sandbox and implement the reversal method for singly and doubly linked lists, create a tweet with your sandbox link, and tag CoderPad.