A linked list is one of the most basic data structures in computer science. In this article, we will go through the following topics:
- Advantages and disadvantages of linked list over arrays.
- What is a linked list?
- Insertion in a linked list (insert node).
- Deletion from a linked list (delete node).
What is a linked list?
It is a list of nodes where each node contains data and a pointer to the next node in the list. It is a linear data structure, meaning it can be traversed by following only one pointer at a time. The first node is called the head, and the last node is called the tail. The tail node points to null.
class Node:
def __init__(self, data: int, next_node: 'Node' = None):
self.data = data
self.next = next_node
Insertion in a linked list (insert node)
There are three ways to insert a node in a linked list:
- Insert at the beginning of the list.
- Insert at the end of the list.
- Insert at a given position.
Insert at the beginning of the list
Let's start with the simplest one. We will insert a node at the beginning of the list. The algorithm consists of the following steps:
- Create a new node.
- Set the next pointer of the new node to point to the head.
- Set the head to point to the new node.
- Return the new head.
def insert_at_beginning(head: Node, data: int) -> Node:
new_node = Node(data)
new_node.next = head
return new_node
Let's create a list of 4 nodes with that method:
head = None
for i in range(4):
head = insert_at_beginning(head, i + 1)
The time complexity of this algorithm is O(1) because we are only changing the head pointer
Insert at the end of the list
That algorithm is a bit more complicated, but still an easy one. We will insert a node at the end of the list.
- Create a new node.
- Set the next pointer of the new node to point to null.
- Iterate through the list until we find the last node.
- Set the next pointer of the tail node to point to the new node.
- Return the head.
def insert_at_end(head: Node, data: int) -> Node:
new_node = Node(data)
if head is None:
return new_node
current = head
while current.next is not None:
current = current.next
current.next = new_node
return head
head = None
for i in range(5):
head = insert_at_end(head, i + 1)
The time complexity of this algorithm is O(n) because we are iterating through the list until we find the tail.
Insert at a given position.
We will insert a node at a given position. The algorithm consists of the following steps:
- Create a new node.
- Iterate through the list until we find the node at the given position.
- Set the next pointer of the new node to point to the node at the given position.
- Set the next pointer of the previous node to point to the new node.
- Return the head.
def insert_at_position(head: Node, data: int, position: int) -> Node:
new_node = Node(data)
if position == 0:
new_node.next = head
return new_node
current = head
current_position = 0
while current is not None and current_position < position - 1:
current = current.next
current_position += 1
if current is None:
return head
new_node.next = current.next
current.next = new_node
return head
The time complexity of this algorithm is O(n) because we are iterating through the list until we find the node at the required position
Insert a node at position 0:
Insert a node at a position greater than the length of the list:
Insert a node at a position between 0 and the length of the list:
Deletion from a linked list
There are three ways to delete a node from a linked list:
- Delete the first node.
- Delete the last node.
- Delete a node at a given position.
Delete the first node
The algorithm consists of the following steps:
- Set the head to point to the second node.
- Return the new head.
def delete_first(head: Node) -> Node:
if head is None:
return None
return head.next
The time complexity of this algorithm is O(1) because we are only changing the head pointer.
Delete the last node
The algorithm consists of the following steps:
- Iterate through the list until we find the second last node.
- Set the next pointer of the second last node to point to null.
- Return the head.
def delete_last(head: Node) -> Node:
if head is None:
return None
if head.next is None:
return None
current = head
while current.next.next is not None:
current = current.next
current.next = None
return head
The time complexity of this algorithm is O(n) because we are iterating through the list until we find the second last node.
Delete a node at a given position
The algorithm consists of the following steps:
- Iterate through the list until we find the node at the given position.
- Set the next pointer of the previous node to point to the node after the node at the given position.
- Return the head.
def delete_at_position(head: Node, position: int) -> Node:
if position == 0:
return head.next
current = head
current_position = 0
while current is not None and current_position < position - 1:
current = current.next
current_position += 1
if current is None or current.next is None:
return head
current.next = current.next.next
return head
The time complexity of this algorithm is O(n) because we are iterating through the list until we find the node at the required position.
Conclusion
In this article, we have seen how to implement a linked list in Python. That data structure is very efficient when you need to add or remove elements from the head of the list. It is also very easy to implement.