Back to blog

# An Introduction to Linked List Data Structures

Development

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:

The last node always points to NULL, except for circular linked lists.

There are three types of linked lists:

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.

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.

``````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 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.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.

The primary operations of a singly linked list include:

1. Traversal
2. Insertion
3. 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:

while current and current.next is not None:
current = current.next

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

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)

if self.tail == None:

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:
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
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)

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:
return

if position == self.size:
prev = None

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

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:

1. 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.
2. 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.
3. 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)```

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 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.tail = None
self.size = 0```Code language: Python (python)```

Just as before, the primary operations of a doubly linked list include:

1. Traversal
2. Insertion
3. 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:

while current and current.next is not None:
current = current.next

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)

if self.tail == None:

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
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)

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.next = None
node_to_remove.previous = None

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

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:

1. 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.
2. 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 to `None` respectively.
3. 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 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):
new_node = Node(value)

new_node.next = new_node
else:
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.