• Articles
• Tutorials
• Interview Questions
• Webinars

# 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.

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.

Enroll in this Full Stack Developer Course and start your journey now!

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.

Also, check our blog on Linkedlist in Java

## 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:

• 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.

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.

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 = Noneclass 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
second_node = Node(2)
third_node = Node(3)
second_node.next = third_node
# Traversing the list
traverse_list(sll)```

# Output: 1 2 3

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

Drawbacks

• Limited in reverse traversal.

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
def __init__(self):

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 listdll = DoublyLinkedList()dll.head = DoublyNode(1)second_node = DoublyNode(2)third_node = DoublyNode(3)dll.head.next = second_nodesecond_node.prev = dll.headsecond_node.next = third_nodethird_node.prev = second_node# Traversing the listtraverse_doubly_list(dll)`

# Output: 1 2 3

• Efficient for reverse traversal.

Drawbacks

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

Get a comprehensive understanding of Recursion in Data Structure with our in-depth blog post!

Get 100% Hike!

Master Most in Demand Skills Now !

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 = Noneclass 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 listcll = CircularLinkedList()cll.head = CircularNode(1)second_node = CircularNode(2)third_node = CircularNode(3)cll.head.next = second_nodesecond_node.next = third_nodethird_node.next = cll.head# Traversing the listtraverse_circular_list(cll)`

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

Get a comprehensive understanding of Hashing in Data Structure with our in-depth blog!

## 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.

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:

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.

Read the Top 50 Data Structures Interview Questions to ace your next interview!

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.

If you have any doubts or queries, do drop them on our Community Page!

## FAQs

### What makes linked lists preferable over arrays?

Linked lists excel in scenarios requiring dynamic memory allocation, frequent insertions, and deletions, offering flexibility and efficient use of memory.

### How do I choose between singly and doubly linked lists?

Choose a singly linked list for simple and forward traversals. Opt for a doubly linked list when bidirectional traversal or frequent insertions and deletions are essential.

### When should I use a circular linked list?

Circular linked lists are ideal for scenarios requiring continuous navigation, such as periodic tasks or operations that need to loop through the elements seamlessly.

### Can linked lists be used for large datasets?

While linked lists offer dynamic memory allocation, their pointers can introduce overhead. For large datasets with fixed sizes, arrays might be more efficient in terms of memory usage.

Course Schedule

Name Date Details
Python Course 22 Jun 2024(Sat-Sun) Weekend Batch
View Details
Python Course 29 Jun 2024(Sat-Sun) Weekend Batch
View Details
Python Course 06 Jul 2024(Sat-Sun) Weekend Batch
View Details