A linked list is a linear data structure in which pointers are used to connect its nodes. Linked lists hold elements at separate locations and connect them via pointers, in contrast to arrays, which store elements in contiguous memory locations.
For understanding linked lists, it is advised to have a basic knowledge of python programming and OOPs concept.
In this article, we will learn about the implementation of a linked list in Python. Python classes will be used to implement the linked list. As we now know, a linked list is made up of nodes, each of which has two components: data and a reference to another node.
What is a Linked List?
Linked list is a kind of linear data structure that resembles arrays is a linked list. It is made up of a number of interconnected nodes. Data and a connection that links it to another node are the two components that make up a node.
A linked list is a collection of nodes where each node contains:
Data – The actual value stored in the node.
Pointer (Next) – A reference to the next node in the sequence.
Structure of a Linked List
A simple linked list with four elements:
Advantages and Disadvantages of Linked Lists
Advantages
Dynamic Size: Linked lists don't need to have a set size like arrays do.
Effective Insertions/Deletions: When adding or deleting nodes, there is no need to move elements.
Memory Utilization: By allocating memory as needed, waste is minimized.
Disadvantages
Additional Memory Usage: Memory usage rises as a result of each node storing an extra pointer.
Slow Search Operations: Due to linked lists' inability to directly index data, search operations are slower with O(n) complexity than arrays.
When to Use a Linked List?
If the quantity of components is unpredictable and fluctuates regularly.
If there is a need for frequent additions and deletions.
If quick access is less significant than memory economy.
Implementation of a Singly Linked List in Python
Step 1: Defining a Node
Each node in the linked list will have:
A value (data).
A pointer to the next node (initialized as None).
class Node: def init(self, value): self.value = value # Data stored in the node self.next = None # Pointer to the next node |
Explanation:
self.value stores the value of the node.
self.next is a pointer to the next node in the sequence. It is initially None since the node is not connected yet.
Step 2: Defining the Linked List
Now, let's create the LinkedList class to manage the linked list operations.
class LinkedList: def init(self, head=None): self.head = head # The first node in the list |
Explanation:
self.head is the starting point of the linked list.
If no head is provided, it is initialized as None.
Step 3: Appending a Node
To add a new node to the end of the linked list, we define an append method.
def append(self, new_node): current = self.head if current: while current.next: current = current.next current.next = new_node else: self.head = new_node |
Explanation:
If the list is empty, the new node becomes the head.
Otherwise, the method traverses the list until it reaches the last node, then sets its next pointer to the new node.
Step 4: Deleting a Node
To remove a node with a specific value, we define a delete method.
def delete(self, value): current = self.head if current.value == value: self.head = current.next else: while current: if current.value == value: break prev = current current = current.next if current is None: return current = None |
Explanation:
If the node to delete is the head, we simply update self.head.
Otherwise, we traverse the list to find the node, update the previous node's next pointer to skip the deleted node, and remove it.
Step 5: Inserting a Node at a Specific Position
To insert a node at a specific position, we define an insert method.
def insert(self, new_element, position): count = 1 current = self.head if position == 1: new_element.next = self.head self.head = new_element while current: if count + 1 == position: new_element.next = current.next current.next = new_element return else: count += 1 current = current.next |
Explanation:
If inserting at the head, update self.head to the new node.
Otherwise, traverse the list to the correct position and update pointers accordingly.
Step 6: Displaying the Linked List
To print all nodes in the linked list, we define a print_list method.
def print_list(self): current = self.head while current: print(current.value, end=" -> ") current = current.next print("None") |
Explanation:
This method iterates through the list and prints each node’s value.
It prints "None" at the end to indicate the end of the list.
Example Usage
# Create nodes e1 = Node(1) e2 = Node(2) e3 = Node(3) # Create a linked list and append nodes l = LinkedList(e1) l.append(e2) l.append(e3) # Print the list l.print_list() # Output: 1 -> 2 -> 3 -> None # Insert a node at position 2 e4 = Node(4) l.insert(e4, 2) l.print_list() # Output: 1 -> 4 -> 2 -> 3 -> None # Delete a node l.delete(2) l.print_list() # Output: 1 -> 4 -> 3 -> None |
Output:
1 -> 2 -> 3 -> None
1 -> 4 -> 2 -> 3 -> None
1 -> 4 -> 3 -> None
Types of Linked Lists
Singly Linked List (SLL)
Every node in a singly linked list points to the node after it, enabling traversal in just one direction.
Characteristics
Data and a pointer to the next node are contained in each node.
The reference to the first node is stored in the head.
The pointer of the final node is set to NULL.
Python Implementation of Singly Linked List
# Node class to represent each element in the list class Node: def init(self, data): self.data = data # Store data self.next = None # Pointer to the next node # Singly Linked List class class SinglyLinkedList: def init(self): self.head = None # Initialize an empty list # Function to insert a node at the end of the list def insert_at_end(self, data): new_node = Node(data) # Create a new node if not self.head: # If the list is empty, set head to new node self.head = new_node return temp = self.head # Start from the head while temp.next: # Traverse to the last node temp = temp.next temp.next = new_node # Link the last node to the new node # Function to display the list def display(self): temp = self.head while temp: print(temp.data, end=" -> ") temp = temp.next print("None") # Indicating the end of the list # Example Usage sll = SinglyLinkedList() sll.insert_at_end(10) sll.insert_at_end(20) sll.insert_at_end(30) sll.display() |
Output:
10 -> 20 -> 30 -> None
Doubly Linked List (DLL)
A linked list with two pointers in each node is called a doubly linked list:
The next node is indicated with one.
One that points to the node before it.
Characteristics
Each node contains data, a next pointer, and a previous pointer.
The head points to the first node, and the tail points to the last node.
The previous pointer of the first node and the next pointer of the last node are set to NULL.
Python Implementation of Doubly Linked List
class Node: def init(self, data): self.data = data self.prev = None # Pointer to the previous node self.next = None # Pointer to the next node class DoublyLinkedList: def init(self): self.head = None def insert_at_end(self, data): new_node = Node(data) if not self.head: self.head = new_node return temp = self.head while temp.next: temp = temp.next temp.next = new_node new_node.prev = temp # Link the new node to the previous node def display_forward(self): temp = self.head while temp: print(temp.data, end=" ⇄ ") temp = temp.next print("None") # Example Usage dll = DoublyLinkedList() dll.insert_at_end(10) dll.insert_at_end(20) dll.insert_at_end(30) dll.display_forward() |
Output:
10 ⇄ 20 ⇄ 30 ⇄ None
Circular Linked List (CLL)
A circular linked list is one in which a circular loop is formed by the last node pointing back to the initial node.
The image below is an example of a singly circular linked list:
The image below is an example of a doubly circular linked list:
Characteristics
NULL is absent from every node. Rather, the first node is referenced by the pointer of the last node.
Either a doubly circular linked list or a singly circular linked list can be used.
Python Implementation of Circular Linked List
class Node: def init(self, data): self.data = data self.next = None # Pointer to the next node class CircularLinkedList: def init(self): self.head = None def insert_at_end(self, data): new_node = Node(data) if not self.head: self.head = new_node new_node.next = self.head return temp = self.head while temp.next != self.head: temp = temp.next temp.next = new_node new_node.next = self.head def display(self): if not self.head: return temp = self.head while True: print(temp.data, end=" → ") temp = temp.next if temp == self.head: break print("(Back to head)") # Example Usage cll = CircularLinkedList() cll.insert_at_end(10) cll.insert_at_end(20) cll.insert_at_end(30) cll.display() |
Output:
10 → 20 → 30 → (Back to head)
Conclusion
Linked lists offer effective insertion and deletion processes as well as flexibility in memory management. Applications like memory management, scheduling, and dynamic data storage make extensive use of them.
Are you prepared to learn more about programming? Take advantage of Our Comprehensive Data Structures & Analytics Course to learn more!
Gain knowledge from professionals in the field through practical projects and real-world applications. Learn about trees, graphs, linked lists, and more to become an expert problem solver. Take your programming career to the next level by enrolling today!
Comments