Linked List in Data Structure

One interesting aspect of linked lists is their dynamic nature, allowing for efficient data manipulation. Unlike arrays, where elements are stored in contiguous memory locations, linked lists use nodes that are scattered in memory. This flexibility makes it easy to insert or delete elements anywhere in the list without the need to shift or resize the entire structure.

Table of Contents

• What is a Linked List in Data Structure?
• Linked List vs. Array
• Components of a Linked List
• Types of Linked Lists
• Basic Operations on Linked Lists
• Advanced Operations on Linked Lists
• Comparing Different Types of Linked Lists in Data Structure
• Conclusion
• FAQs

Watch the video below to understand linked lists in data structures

What is a Linked List in Data Structure?

A linked list is a fundamental data structure used in computer science for organizing and managing data. Unlike arrays, which store elements in contiguous memory locations, a linked list comprises nodes connected through pointers. Each node contains data and a reference to the next node in the sequence.

Structure of a Linked List

Consider a simple example: a chain of linked paper clips. Each paper clip represents a node, and the linking mechanism is the pointer. The first paper clip holds the initial data, while each subsequent paper clip points to the next one.

How It Works

A linked list starts with a head node, representing the beginning of the list.

• Nodes are dynamically allocated in memory as data is added. Each node contains information and a pointer to the next node.
• The pointers link nodes sequentially. The last node’s pointer typically points to null, signifying the end of the list.
• To access elements, the list is traversed by following the pointers from the head to the desired node.
• Adding or removing elements involves adjusting pointers, allowing for efficient operations without moving entire blocks of memory.

The below diagram is a linked list with nodes A, B, C, and D.

Here, each arrow represents a pointer, indicating the sequence of nodes.

Linked List vs. Array

The table below lists the differences between linked lists and arrays. It showcases scenarios where one may be more suitable than the other based on specific requirements.

Components of a Linked List

Understanding the components of a linked list is the key to unraveling the power and versatility embedded in linked list data structures.

a) Nodes
In a linked list, a node is the fundamental building block that encapsulates data and facilitates the structure of the list. Each node comprises two essential components:

• Data Field
  • The data field is where the actual information is stored. It could be any data type depending on the application—integer, character, object, etc.
  • For instance, in a singly linked list representing a sequence of numbers, the data field of each node would store a numerical value.
• Pointer Field
  • The pointer field is crucial, as it holds the memory address of the next node in the linked list.
  • This pointer enables linkage between nodes, creating a sequential flow of data. In a doubly linked list, there may be two pointers—one pointing to the next node and another to the previous one.

b) Pointers
Pointers are variables that store the memory address of another variable. In the context of linked lists, pointers play a pivotal role in establishing the connections between nodes. There are two primary types of pointers in linked lists:

• Head Pointer
  • The head pointer points to the first node in the linked list. It serves as the entry point, allowing traversal through the entire list by following subsequent pointers.
  • Initializing the head pointer is the starting point for creating and navigating a linked list.
• Next (and Previous) Pointers
  • The next pointer in a node points to the memory location of the next node in the sequence. It is what enables the linked structure.
  • In a doubly linked list, there might be an additional previous pointer pointing to the node preceding the current one.

Types of Linked Lists

Each type of linked list has its strengths and weaknesses, making it suitable for different scenarios. The choice depends on the specific requirements of the task at hand, balancing factors like memory efficiency, traversal needs, and the complexity of operations. Let us now discuss the different types of linked lists.

Singly Linked Lists

A singly linked list is a linear data structure where elements are stored in nodes, and each node points to the next one in the sequence. Each node contains two fields: data and a reference (or pointer) to the next node. The last node points to null, indicating the end. Traversal begins at the head node and moves through each subsequent node. Accessing elements involves iterating through the list, making it suitable for forward-only navigation.

Structure

class Node:
 def __init__(self, data):
 self.data = data
 self.next = None
class SinglyLinkedList:
 def __init__(self):
 self.head = None

Traversal

def traverse_list(linked_list):
 current = linked_list.head
 while current:
 print(current.data, end=" ")
 current = current.next

Example

# Creating a singly linked list
sll = SinglyLinkedList()
sll.head = Node(1)
second_node = Node(2)
third_node = Node(3)
sll.head.next = second_node
second_node.next = third_node
# Traversing the list
traverse_list(sll)

# Output: 1 2 3

Advantages

• Efficient memory usage, as each node only needs one pointer.
• Simple implementation and memory management.

Drawbacks

• Limited in reverse traversal.
• Inefficient for operations requiring access to previous nodes.

Doubly Linked Lists

A doubly linked list is a type of linked list where each node contains data and two pointers—one pointing to the next node and another to the previous node. Nodes have three fields: data, a pointer to the next node, and a pointer to the previous node. The first node’s previous pointer and the last node’s next pointer point to null. Traversal is bidirectional, allowing both forward and backward movements through the list. This flexibility aids in operations involving adjacent nodes.

Structure

class DoublyNode:
 def __init__(self, data):
 self.data = data
 self.next = None
 self.prev = None
class DoublyLinkedList:
 def __init__(self):
 self.head = None

Traversal

def traverse_doubly_list(linked_list):
 current = linked_list.head
 while current:
 print(current.data, end=" ")
 current = current.next

Example

# Creating a doubly linked list
dll = DoublyLinkedList()
dll.head = DoublyNode(1)
second_node = DoublyNode(2)
third_node = DoublyNode(3)
dll.head.next = second_node
second_node.prev = dll.head
second_node.next = third_node
third_node.prev = second_node
# Traversing the list
traverse_doubly_list(dll)

# Output: 1 2 3

Advantages

• Efficient for reverse traversal.
• Supports operations requiring access to both previous and next nodes.

Drawbacks

• Increased memory overhead due to an additional pointer in each node.
• More complex implementation compared to singly linked lists.

Circular Linked Lists

A circular linked list is a variation where the last node points back to the first, forming a closed loop. Similar to a singly linked list, the last node’s pointer points to the first, creating a circular structure. Traversal continues indefinitely, circling through the list until a specific condition is met.

Structure

class CircularNode:
 def __init__(self, data):
 self.data = data
 self.next = None
class CircularLinkedList:
 def __init__(self):
 self.head = None

Traversal

def traverse_circular_list(linked_list):
 if linked_list.head is not None:
 current = linked_list.head
 while True:
 print(current.data, end=" ")
 current = current.next
 if current == linked_list.head:
 break

Example

# Creating a circular linked list
cll = CircularLinkedList()
cll.head = CircularNode(1)
second_node = CircularNode(2)
third_node = CircularNode(3)
cll.head.next = second_node
second_node.next = third_node
third_node.next = cll.head
# Traversing the list
traverse_circular_list(cll)

# Output: 1 2 3 (looped back to 1)

Basic Operations on Linked Lists

Basic operations on linked lists involve effortless insertion, deletion, and traversal, forming the core of dynamic data organization and manipulation.

a) Insertion: Adding Items to the Linked List

Insertion in a linked list involves adding a new node with a specific value at a desired position. There are different scenarios for insertion:

• Inserting at the Beginning: To add a node at the beginning, you create a new node, set its pointer to the current head, and update the head to the new node.

def insert_at_beginning(head, value):
 new_node = Node(value)
 new_node.next = head
 return new_node

• Inserting at the End: To add a node at the end, traverse the list to find the last node and update its pointer to the new node.

def insert_at_end(head, value):
 new_node = Node(value)
 if not head:
 return new_node
 current = head
 while current.next:
 current = current.next
 current.next = new_node
 return head

• Inserting at a Specific Position: To insert at a particular position, traverse the list to that position and adjust pointers to include the new node.

def insert_at_position(head, value, position):
 new_node = Node(value)
 if position == 0:
 new_node.next = head
 return new_node
 current = head
 for _ in range(position - 1):
 if not current:
 return head
 current = current.next
 new_node.next = current.next
 current.next = new_node
 return head

b) Deletion: Deleting an Existing Item from the Linked List

Deletion involves removing a node with a specific value or from a particular position:

• Deleting by Value: Traverse the list, find the node with the desired value, and adjust pointers to skip the node.

def delete_by_value(head, value):
 current = head
 if current and current.data == value:
 return current.next
 while current.next:
 if current.next.data == value:
 current.next = current.next.next
 return head
 current = current.next
 return head

• Deleting at a Specific Position: Traverse the list to the position, and adjust pointers to skip the node.

def delete_at_position(head, position):
 current = head
 if position == 0:
 return current.next
 for _ in range(position - 1):
 if not current:
 return head
 current = current.next
 if not current or not current.next:
 return head
 current.next = current.next.next
 return head

c) Traversal: Accessing Each Element of the Linked List

Traversal is the process of visiting each node in the linked list and performing some operation:

def traverse_linked_list(head):
 current = head
 while current:
 # Perform operation on current node (print, process, etc.)
 print(current.data, end=” “)
 current = current.next

In this function, “head” is the starting point of the linked list. We traverse through the list, accessing and processing each element until we reach the end.

These basic operations form the foundation of linked list manipulations, enabling the dynamic and flexible handling of data within a linked list structure.

Advanced Operations on Linked Lists

There are a lot of advanced operations that can be applied to linked lists. Some of these have been discussed below. 

a) Searching – Finding a Node in the Linked List

Searching in a linked list involves traversing through nodes until the desired node is found. Starting from the head node, each subsequent node is checked until the target data is located or the end of the list (null pointer) is reached.

Algorithm

• Begin at the head node.
• Check if the current node’s data matches the target.
• If a match is found, return the node; otherwise, move to the next node.
• Repeat until the target is found or the end of the list is reached.

Complexity

• The time complexity for searching in a linked list is O(n), where n is the number of nodes.
• In the worst-case scenario, the search operation may need to traverse the entire list.

b) Sorting – Sorting the Nodes in the Linked List

Sorting a linked list involves rearranging the nodes in a specific order, commonly in ascending or descending order based on node data. One common algorithm for sorting linked lists is the Merge Sort.

Algorithm (Merge Sort)

• If the list has zero or one node, it is already sorted.
• Divide the unsorted list into two halves.
• Recursively sort each half.
• Merge the sorted halves to produce a single sorted list.

Complexity

Merge Sort applied to linked lists has a time complexity of O(n log n), making it efficient for large datasets. The space complexity is O(n) due to the need for additional memory during the merging step.

c) Merging – Merge Two Sorted Lists

Merging two sorted linked lists involves combining them into a single sorted list while maintaining the order of elements. This operation is crucial in scenarios where multiple sorted lists need to be merged into one.

Algorithm

• Compare the first nodes of both lists.
• Append the smaller node to the merged list.
• Move to the next node in the list from which the smaller node was taken.
• Repeat until one of the lists is exhausted.
• Append the remaining nodes from the non-empty list to the merged list.

Complexity

• Merging two sorted lists has a time complexity of O(n), where n is the total number of nodes in both lists. 
• This linear complexity arises from the need to compare and merge each node exactly once.

Comparing Different Types of Linked Lists in Data Structure

Understanding the differences between the different types of linked lists is crucial. Each type comes with its own advantages and challenges. Let us have a look at how some of the features differentiate them.

Conclusion

Linked lists prove to be versatile data structures, with distinct types catering to diverse needs. Whether it’s the simplicity of a singly linked list, the bidirectional flexibility of a doubly linked list, or the circular continuity of a circularly linked list, each serves specific purposes. Mastering linked list operations, from basic insertions to advanced searches, enhances data manipulation skills. As you delve into data structures, remember that the choice of a linked list type depends on the nature of your data and the operations you intend to perform.

FAQs