Linked Lists in Data Structure
Linked lists are crucial data structures that organise data components linearly. Linked lists allow elements to be combined via “links” or references, unlike arrays. Non-contiguous storage lets data be saved in any memory address, which is significant.
Every item in a linked list belongs to a node. A typical node contains a reference (or pointer) to the next node in the sequence and the data element (also called the “value” or “item”). A linked list ends with a null reference at the last node. Linked list implementations, which preserve head and tail pointers to the list’s initial and last nodes, can speed up some operations.
Types of Linked Lists
There are numerous types of linked lists, and each one has unique capabilities.
Singly Linked List: Each node in a singly linked list has its own data and a single reference (next) that points solely to the node after it in the list. This is the most basic kind of list. Navigation is only forward.
Doubly Linked List: A doubly linked list has two link fields in each node one that points to the node after it and another (prior or prev) that points to the node before it. This addresses the unidirectional character of singly linked lists. This makes it possible to traverse both forward and backward.
Circular Linked List: The next reference of the tail node in a circular linked list points back to the head node, creating an endless cycle. For data sets that are cyclical and lack a distinct beginning or finish, this structure is helpful.
Advantages and Disadvantages
Advantages of Linked Lists
Dynamic Sizing: Linked lists can grow or shrink dynamically as needed and don’t have a set size. By doing this, array-based structures can avoid the costly process of copying and resizing elements.
Efficient Insertions and Deletions: Unlike arrays, where moving one element in the middle necessitates moving succeeding members, linked lists particularly doubly linked lists with direct node references can execute insertions and removals in O(1) time. All it takes to do this is to alter a few references or pointers. If you know the reference to the node, doubly linked lists can provide O(1)-time updates even at random locations.
Disadvantages of Linked Lists
Slow Searching/Access by Index: Accessing an element by its numerical index or finding a specific element in a linked list is typically slow, taking O(N) time. You have to start at the beginning of the list and “link hop” through each element until you find the one you want.
Memory Overhead: In a linked list, each node needs additional memory to hold the reference or references to other nodes, but in a basic array, this is not necessary.
Inefficient Deletion from Tail: Deleting the final node in a singly linked list is inefficient because it necessitates going through the entire list from the head to find the second-to-last node, which is an O(N) operation in the absence of a pointer to the node that comes before it. Lists with two links get around this restriction.
Core Operations
Traversal: In traversal, every node in the list is visited. Start at the head and go through the points to find a None reference in a singly linked list. Forward and backward traversal of a doubly linked list are possible.
Insertion:
- You must first create a new node and set its next pointer to the list’s head to modify its head. An O(1) operation is this one.
- After creating a new node and setting its next pointer to None, change the list’s tail to point to the new node by setting the current tail’s next pointer to the new node. If one maintains a tail reference, this also takes O(1) time.
Deletion:
- To point to the next node of the current head, update the list’s head from the head. An O(1) operation is this one.
- Deleting a node from the middle or tail of singly linked lists is inefficient since it necessitates locating the predecessor node, which may require traversing from the head (O(N) time). If the node reference is provided, doubly linked lists allow for O(1) deletion by giving a prior pointer.
- You must begin at the head of the list and work your way through it, comparing the data from each node with the desired value until you find it or reach the end of the list. O(N) describes this operation.
Code Example (Singly Linked List)
This simple Python implementation of a singly linked list demonstrates the Node and LinkedList classes using standard functions like appending elements to the end, displaying the list, and element search:
# Node Class: Represents an individual element in the linked list
class Node:
def _init_(self, data):
# Stores the actual data value of the node
self.data = data
# Stores the reference (pointer) to the next node in the sequence
self.next = None
# LinkedList Class: Represents the entire linked list structure
class LinkedList:
def _init_(self):
# Reference to the first node in the list. Initially None for an empty list
self.head = None
# Reference to the last node in the list. Useful for O(1) insertion at the end
self.last_node = None
# Method to add a new element to the end of the linked list
def append(self, data):
new_node = Node(data)
if self.last_node is None:
self.head = new_node
self.last_node = new_node
else: # If the list is not empty
self.last_node.next = new_node
self.last_node = new_node
# Method to display all elements in the linked list
def display(self):
current = self.head
if current is None:
print("List is empty.")
return
print("The linked list: ", end='')
while current is not None:
print(current.data, end=' ')
current = current.next
print()
# Method to search for an element in the linked list
def search(self, data):
current_node = self.head
while current_node:
if current_node.data == data:
return True
else:
current_node = current_node.next
return False
# Example Usage:
my_list = LinkedList()
n_elements = int(input('How many elements would you like to add? '))
for i in range(n_elements):
item_data = int(input(f'Enter data item {i+1}: '))
my_list.append(item_data)
my_list.display()
# Demonstrate search operation
search_val_1 = 6
print(f"Searching for {search_val_1}: {my_list.search(search_val_1)}")
search_val_2 = 10
print(f"Searching for {search_val_2}: {my_list.search(search_val_2)}")Output:
How many elements would you like to add? 5
Enter data item 1: 6
Enter data item 2: 7
Enter data item 3: 8
Enter data item 4: 9
Enter data item 5: 4
The linked list: 6 7 8 9 4
Searching for 6: True
Searching for 10: FalseApplications of Linked Lists
Linked lists serve as a foundational framework for implementing other abstract data types and are employed in a variety of real-world situations due to their versatility:
Stacks: The head of the list acts as the “top” of the stack for O(1) push and pop operations, demonstrating how well linked lists may implement stacks.
Queues: Moreover, they are capable of implementing queues, where the head serves as the “front” and the tail as the “back” for O(1) enqueue and dequeue computations. Queues are a special case for circularly linked lists.
Double-Ended Queues (Deques): Given that deques permit insertions and deletions from both ends in O(1) time, they are a perfect fit for doubly linked lists.
Graphs: Graphs are represented by linked lists, more especially adjacency lists, in which every vertex has a list of its incident edges or neighbouring vertices.
Maintaining Access Frequency: They can be applied to data structures such as “favourites lists” that must control access frequency.
Text Editors: The idea of positional insertion and deletion in linked lists can be used to mimic text editor operations where updates take place in relation to a cursor.
Web Browser History/Music Playlists: Double linked lists are perfect for adding features like browser history or music playlists because they can be navigated both forward and backward.