Linked List Implementation With Examples and Animationby@akankov
3,167 reads
3,167 reads

# Linked List Implementation With Examples and Animation

November 6th, 2022

## Too Long; Didn't Read

A linked list is very efficient when you need to add or remove elements from the head of the list. It is also very easy to implement.

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:

1. Insert at the beginning of the list.
2. Insert at the end of the list.
3. 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:

1. Delete the first node.
2. Delete the last node.
3. 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.

L O A D I N G
. . . comments & more!

### About Author

Aleksei Kankov@akankov
Convert coffee into code )