# Linked List in Data Structures - Types of Linked Lists & Its Applications

29 Apr 2024
Beginner
3.51K Views
Learn via Video Course & by Doing Hands-on Labs

## Linked Lists in Data Structures: An Overview

Linked List in data structures is a non-primitive, linear, and dynamic data structure. It is a chain of nodes where each node is a different element. In this DSA tutorial, we will see the linked list data structure in detail i.e. its features, working, implementation, etc. To further enhance your understanding and application of linked list concepts, consider enrolling in the Dsa Course, where you can gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

## What is a Linked List in Data Structures?

A Linked List is a linear data structure consisting of a series of connected nodes that are randomly stored in the memory. Here, each node consists of two parts, the first part is the `data `and the second part contains the `pointer` to the address of the next node.

The first node of a linked list is called the `Head`, and it acts as an access point. The `head` pointer points to the first element of the linked list. The last node is called the `Tail`, and it marks the end of a linked list by pointing to a `NULL` value. After arrays, linked lists are the second most used data structure.

### Representation of Linked Lists in Data Structures

A linked list can be represented as the connection of nodes in which each node points to the next node of the list.

## Types of Linked Lists in Data Structures

1. Singly-linked list: Here, each node has `data` and a `pointer` that contains a reference to the next node in the list. This means that we can traverse in only one direction, from the `head` to the `tail`. It is the most common linked list.
2. Doubly linked list: In this type of linked list, each interconnected node contains three fields that contain references to both the next and previous nodes in the list along with the data. This allows traversal in both directions, making it easier to insert or delete nodes at any point in the list.
3. Circular linked list: Here, the last node in the list contains a reference to the first node instead of `NULL`, creating a loop. This means that traversal can continue indefinitely, until the program crashes.

## How to declare/create a Singly-Linked List in Data Structures?

We now very well know that a node in a linked list contains two parts, a `data` item and the `address` of another node. So, both parts are of different types, i.e., one is a simple variable, while another is the pointer variable. We can declare the linked list by using the user-defined data type `structure`.
``````struct node
{
int data;
struct node *next;
};
``````

Here, we have created a `structure` named `node` that contains two variables, `data` of integer type, and a pointer, `next` that contains the address of the next node.

If you are still not thorough with `pointers` and user-defined data types like `structures`, refer to Data Types in C++ and Pointers in C++.

## Standard Operations on Linked Lists in Data Structures

### Traversal

We can access each element of the linked list starting from the `head` node. Just keep moving a `temp` node to the next one and display its contents. When `temp` is `NULL`, it means we have reached the end of the linked list so we get out of the `while` loop.

### Insertion

We can insert elements to either the beginning, middle, or end of the linked list. Inserting a new node at any given position is done by manipulating at most two `next` pointers, the `prevNode` and the `newNode`.

Set `newNode's` next pointer to the `prevNode's` next pointer and set `prevNode's` next pointer to the `newNode` where `prevNode` denotes a pointer to the node after which `newNode` is to be inserted. However, to access any given position, we have to traverse starting from the `head` till the `prevNode`.

The order of execution matters in case of insertion. If we interchange the steps i.e. first set `prevNode's` next pointer to the `newNode` then we lose the reference to the remaining of the linked list previously occurring after the `prevNode`.

### Deletion

Same as insertion, you can delete either from the beginning, end, or a particular position. Deleting a node located at a specified index is done by manipulating at most two `next` pointers, the `prevNode`, and the `targetNode`.

Set `prevNode's` next pointer to the `targetNode's` next pointer and set `targetNode's` next pointer to `NULL` where `prevNode` denotes a pointer to the node after which `targetNode` is to be deleted.

Just like insertion, the order is important here also. It's important to realize that setting `targetNode's` next pointer to `NULL` as the first step would cost us the reference to the remaining of the linked list (if the `targetNode` wasn't the `Tail`).

### Search

It is performed to search for an element from the list using the given key.

The following are the steps to search for an element

• Make `head` as the current node.
• Run a loop until the current node is `NULL` because the last element points to `NULL`.
• In each iteration, check if the `key` of the node is equal to the item. If the `key` matches the item, return true otherwise return false.

Read More - Data Structure Interview Questions for Freshers

## Implementation of Linked Lists in Different Programming Languages

``````
class Node:
def __init__(self, data=0, next_node=None):
self.data = data
self.next = next_node

def __init__(self):

def traversal(self):
while itr:
print(itr.data)
itr = itr.next

def insertion(self, prev_node, new_node):
new_node.next = prev_node.next
prev_node.next = new_node

def deletion(self, prev_node, target_node):
prev_node.next = target_node.next

def search(self, key):
while itr:
if itr.data == key:
return True
itr = itr.next

second = Node(2)
third = Node(3)

second.next = third

# Print the initial linked list

# Insert a new node (4) after the second node
new_node = Node(4)

# Print the linked list after insertion

# Delete the second node

# Print the linked list after deletion

# Search for a key (3) in the linked list
key = 3
``````
``````
class Node {
int data;
Node next;

Node() {
this.data = 0;
this.next = null;
}

Node(int x) {
this.data = x;
this.next = null;
}

Node(int x, Node next) {
this.data = x;
this.next = next;
}
}

// Constructor for creating a linked list
}

void traversal() {
while (itr != null) {
System.out.println(itr.data);
itr = itr.next;
}
}

// 'newNode' - pointer to the node to be inserted
// 'prevNode' - pointer to the node after which insertion occurs
void insertion(Node prevNode, Node newNode) {
newNode.next = prevNode.next;
prevNode.next = newNode;
}

// 'targetNode' - pointer to the node to be deleted
// 'prevNode' - pointer to the node after which deletion occurs
void deletion(Node prevNode, Node targetNode) {
prevNode.next = targetNode.next;
}

boolean search(int key) {
while (itr != null) {
if (itr.data == key)
return true;
itr = itr.next;
}
}

public static void main(String[] args) {

// Example usage:
Node second = new Node(2);
Node third = new Node(3);

second.next = third;

// Print the initial linked list
list.traversal();

// Insert a new node (4) after the second node
Node newNode = new Node(4);
list.insertion(second, newNode);

// Print the linked list after insertion
list.traversal();

// Delete the second node

// Print the linked list after deletion
list.traversal();

// Search for a key (3) in the linked list
int key = 3;
System.out.println("\nKey " + key + " is " + (list.search(key) ? "found" : "not found") + " in the linked list.");
}
}
``````
``````
#include <iostream>
using namespace std;

struct Node {
int data;
Node* next;

Node() : data(0), next(nullptr) {}
Node(int x) : data(x), next(nullptr) {}
Node(int x, Node* next) : data(x), next(next) {}
};

public:
Node* head; // pointer to the first node of the linked list

// constructor for creating a linked list

void traversal() {
while (itr != nullptr) {
cout << itr->data << endl;
itr = itr->next;
}
}

// 'newNode' - pointer to the node to be inserted
// 'prevNode' - pointer to the node after which insertion occurs
void insertion(Node* prevNode, Node* newNode) {
newNode->next = prevNode->next;
prevNode->next = newNode;
}

// 'targetNode' - pointer to the node to be deleted
// 'prevNode' - pointer to the node after which deletion occurs
void deletion(Node* prevNode, Node* targetNode) {
prevNode->next = targetNode->next;
delete targetNode;
}

bool search(int key) {
while (itr != nullptr) {
if (itr->data == key)
return true;
itr = itr->next;
}
}
};

int main() {

Node* second = new Node(2);
Node* third = new Node(3);

second->next = third;

// Print the initial linked list
cout << "Initial Linked List:" << endl;
list.traversal();

// Insert a new node (4) after the second node
Node* newNode = new Node(4);
list.insertion(second, newNode);

// Print the linked list after insertion
cout << "\nLinked List after Insertion:" << endl;
list.traversal();

// Delete the second node

// Print the linked list after deletion
cout << "\nLinked List after Deletion:" << endl;
list.traversal();

// Search for a key (3) in the linked list
int key = 3;
cout << "\nKey " << key << " is "

return 0;
}
``````

#### Output

``````Initial Linked List:
1
2
3

1
2
4
3

1
4
3

Key 3 is found in the linked list.   ``````

## Complexity Analysis of Linked List Operations

• Time Complexity Operations Best Case Average Case Worst case Traversal `O(n)` `O(n)` `O(n)` Insertion `O(1)` `O(1)` `O(n)` Deletion `O(1)` `O(1)` `O(n)` Search `O(1)` `O(n)` `O(n)`
• Space Complexity: The space complexity of the linked list for all operations is `O(n)`.

### Arrays vs Linked Lists in terms of Time Complexity

 Operations Array Linked List Random Access `O(1)` `O(n)` Insertion and Deletion at the beginning `O(n)` `O(1)` Insertion and Deletion at the end `O(1)` `O(n)` Insertion and Deletion from any random location `O(n)` `O(n)`

## Differences between Arrays and Linked Lists

After seeing the above comparisons in general and in terms of time complexity, we observe that a linked list is not superior to an array or vice-versa. These data structures complement each other and sometimes become superior to the other in certain use cases.

Linked lists are commonly used in computer programming for their ability to efficiently store and manipulate collections of data. Here are some common applications of linked lists:

1. Implementing data structures: Linked lists are commonly used to implement data structures like stacks, queues, graphs, and hash tables.
2. Dynamic Memory allocation:A linked list of free memory blocks is maintained, and new memory is allocated by removing blocks from the free list.
3. File systems: Linked lists are used in file systems to represent directories and files.
4. Music and video players: The list of songs in the music player is linked to the previous and next songs. Linked lists maintain playlists.
6. Games: Linked lists are used to represent game boards where each element in the list represents a cell on the board.

1. Dynamic: Linked lists can be resized during runtime, which means that anyone can add or remove elements from the list without worrying about the size limitations of the underlying data structure.
2. Efficient insertion and deletion: Adding or removing elements to and from a linked list is very easy because the user only needs to update the address of the `pointer` of the node as the nodes are stored in random locations.
3. Flexibility: Linked lists can be used to implement a variety of advanced data structures, such as `stacks`, `queues`, and `hash tables`. This flexibility makes linked lists a versatile tool for many programming tasks.
4. Memory efficiency:Memory consumption of a linked list is efficient as its size can grow or shrink dynamically according to our requirements, which means effective memory utilization hence, no memory wastage.
5. Easy implementation: Implementing a linked list is relatively easy, as the developer only needs to define a node structure and a few functions to manipulate the links between nodes.

1. Memory Consumption: The use of `pointers` is more in linked lists hence, complex and requires more memory.
2. Traversal: Unlike arrays, linked lists do not allow direct access to individual nodes. Traversing a linked list requires iterating through all the nodes from the beginning of the list until the desired node is found. This can be inefficient and slow, especially for large linked lists. Traversing in reverse order is not possible in singly linked lists.
3. No Random Access: Linked lists do not support random access, i.e., accessing a specific node directly without traversing the list. This can be a significant disadvantage for some applications that require fast access to individual elements.
4. Cache Misses: Linked lists can suffer from cache misses, i.e., when the CPU needs to access data that is not in the cache. This can slow down the execution of programs that frequently access data from linked lists.
5. Search: Linked lists are not efficient for searching large amounts of data, which can be better handled by other data structures such as trees or `hash tables`.
##### Summary

So, here we saw every aspect of a linked list in data structures. You might have got at least some idea regarding linked lists and their applications. I know it's quite difficult to understand the whole topic in a single go. Therefore, refer to it again and again till you get thorough with the linked list in data structures. To test your knowledge of linked lists, enroll in our Data Structures Certification training.

## FAQs

### Q1. What is a Linked List?

A Linked List is a linear data structure consisting of a series of connected nodes that are randomly stored in the memory. Here, each node consists of two parts, the first part is the data and the second part contains the pointer to the address of the next node.

### Q3. Which data structures can be implemented by linked lists?

Linked lists are commonly used to implement data structures like stacks, queues, graphs, and hash tables.
Share Article

### Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
 Angular Certification Course May 25 SAT, SUN Filling Fast 06:00PM to 08:00PM (IST) Full Stack .Net Certification Training May 26 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST) ASP.NET Core Certification Training May 26 SAT, SUN Filling Fast 08:30PM to 10:30PM (IST) Advanced Full-Stack .NET Developer Certification Training May 26 SAT, SUN Filling Fast 08:30PM to 10:30PM (IST) Data Structures and Algorithms Training Jun 04 TUE, FRI Filling Fast 08:30PM to 10:00PM (IST) Azure DevOps Certification Training Course Jun 09 SUN Filling Fast 04:30PM to 06:30PM (IST) ASP.NET Core Certification Training Jun 21 MON, WED, FRI Filling Fast 07:00AM to 08:30AM (IST) Azure Developer Certification Training Jun 23 SAT, SUN Filling Fast 10:00AM to 12:00PM (IST)

Can't find convenient schedule? Let us know

Similar Articles