A is one of the most basic data structures in computer science. In this article, we will go through the following topics: linked list 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 https://youtu.be/o3QSIpwbnWA 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. https://youtu.be/My9EhWutFLA 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: https://youtu.be/M6arY_grcQk Insert a node at a position greater than the length of the list: https://youtu.be/WV0Yg2V7uwQ Insert a node at a position between 0 and the length of the list: https://youtu.be/Erj15RJKbWA 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. https://youtu.be/CO9y3i2KdGM 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. https://youtu.be/E0qOO7bcyBY 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. https://youtu.be/-Za3ox3H2sk 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.
