Applications, Advantages and Disadvantages of Linked List
Last Updated :
05 Apr, 2023
- A Linked List is a linear data structure that is used to store a collection of data with the help of nodes. A linked list is made up of two items that are data and a reference to the next node. A reference to the next node is given with the help of pointers and data is the value of a node. Each node contains data and links to the other nodes. It is an ordered collection of data elements called a node and the linear order is maintained by pointers. It has an upper hand over the array as the number of nodes i.e. the size of the linked list is not fixed and can grow and shrink as and when required, unlike arrays. Some of the features of the linked list are as follows:
- The consecutive elements are connected by pointers.
- The size of a linked list is not fixed.
- The last node of the linked list points to null.
- Memory is not wasted but extra memory is consumed as it also uses pointers to keep track of the next successive node.
- The entry point of a linked list is known as the head.
The various types of linked lists are as follows:
- Singly Linked List: It is the most basic linked list in which traversal is unidirectional i.e. from the head node to the last node.
Example:
C++
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
class SinglyLinkedList {
public:
Node* head;
SinglyLinkedList() {
this->head = nullptr;
}
void add_node(int data) {
Node* new_node = new Node(data);
new_node->next = this->head;
this->head = new_node;
}
};
|
Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def add_node(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
|
Java
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
class SinglyLinkedList {
Node head;
SinglyLinkedList() {
head = null;
}
void add_node(int data) {
Node new_node = new Node(data);
new_node.next = head;
head = new_node;
}
}
|
C#
using System;
public class Node {
public int data;
public Node next;
public Node(int d) {
data = d;
next = null;
}
}
public class SinglyLinkedList {
public Node head;
public SinglyLinkedList() {
head = null;
}
public void add_node(int data) {
Node new_node = new Node(data);
new_node.next = head;
head = new_node;
}
}
|
Javascript
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.head = null;
}
add_node(data) {
let new_node = new Node(data);
new_node.next = this.head;
this.head = new_node;
}
}
|
- Doubly Linked List: In this linked list, traversal can be done in both ways, and hence it requires an extra pointer.
Example:
C
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
struct DoublyLinkedList {
struct Node* head;
};
void addNode(struct DoublyLinkedList* list, int data) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = list->head;
newNode->prev = NULL;
if (list->head != NULL) {
list->head->prev = newNode;
}
list->head = newNode;
}
|
C++
class Node {
public:
int data;
Node* next;
Node* prev;
Node(int d) : data(d), next(nullptr), prev(nullptr) {}
};
class DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() : head(nullptr) {}
void add_node(int data) {
Node* new_node = new Node(data);
new_node->next = head;
if (head != nullptr) {
head->prev = new_node;
}
head = new_node;
}
};
|
Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def add_node(self, data):
new_node = Node(data)
new_node.next = self.head
if self.head is not None:
self.head.prev = new_node
self.head = new_node
|
Java
public class Node {
public int data;
public Node next;
public Node prev;
public Node(int d) {
data = d;
next = null;
prev = null;
}
}
public class DoublyLinkedList {
public Node head;
public DoublyLinkedList() {
head = null;
}
public void addNode(int data) {
Node newNode = new Node(data);
newNode.next = head;
if (head != null) {
head.prev = newNode;
}
head = newNode;
}
}
|
C#
public class Node {
public int data;
public Node next;
public Node prev;
public Node(int d) {
data = d;
next = null;
prev = null;
}
}
public class DoublyLinkedList {
public Node head;
public DoublyLinkedList() {
head = null;
}
public void AddNode(int data) {
Node newNode = new Node(data);
newNode.next = head;
if (head != null) {
head.prev = newNode;
}
head = newNode;
}
}
|
Javascript
class Node {
constructor(d) {
this.data = d;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
}
addNode(data) {
const newNode = new Node(data);
newNode.next = this.head;
if (this.head !== null) {
this.head.prev = newNode;
}
this.head = newNode;
}
}
|
- Circular Linked List: This linked list is unidirectional but in this list, the last node points to the first i.e. the head node and hence it becomes circular in nature.
Example:
C
struct Node {
int data;
struct Node* next;
};
struct CircularLinkedList {
struct Node* head;
};
void add_node(struct CircularLinkedList* list, int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = NULL;
if (list->head == NULL) {
list->head = new_node;
new_node->next = new_node;
return;
}
struct Node* current = list->head;
while (current->next != list->head) {
current = current->next;
}
current->next = new_node;
new_node->next = list->head;
}
|
C++
class Node {
public:
int data;
Node* next;
Node(int d) : data(d), next(nullptr) {}
};
class CircularLinkedList {
public:
Node* head;
CircularLinkedList() : head(nullptr) {}
void add_node(int data) {
Node* new_node = new Node(data);
if (head == nullptr) {
head = new_node;
new_node->next = head;
return;
}
Node* current = head;
while (current->next != head) {
current = current->next;
}
current->next = new_node;
new_node->next = head;
}
};
|
Java
class Node {
public int data;
public Node next;
public Node(int d) {
data = d;
next = null;
}
}
class CircularLinkedList {
public Node head;
public CircularLinkedList() {
head = null;
}
public void add_node(int data) {
Node new_node = new Node(data);
if (head == null) {
head = new_node;
new_node.next = head;
return;
}
Node current = head;
while (current.next != head) {
current = current.next;
}
current.next = new_node;
new_node.next = head;
}
}
|
Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def add_node(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
new_node.next = self.head
return
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head
|
Javascript
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class CircularLinkedList {
constructor() {
this.head = null;
}
add_node(data) {
const new_node = new Node(data);
if (this.head === null) {
this.head = new_node;
new_node.next = this.head;
return;
}
let current = this.head;
while (current.next !== this.head) {
current = current.next;
}
current.next = new_node;
new_node.next = this.head;
}
}
|
C#
public class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
public class CircularLinkedList
{
public Node head;
public CircularLinkedList()
{
head = null;
}
public void add_node(int data)
{
Node new_node = new Node(data);
if (head == null)
{
head = new_node;
new_node.next = head;
return;
}
Node current = head;
while (current.next != head)
{
current = current.next;
}
current.next = new_node;
new_node.next = head;
}
}
|
- Circular Doubly Linked List: The circular doubly linked list is a combination of the doubly linked list and the circular linked list. It means that this linked list is bidirectional and contains two pointers and the last pointer points to the first pointer.
Linked Lists are most commonly used for:
Applications of Linked Lists:
- Linked Lists are used to implement stacks and queues.
- It is used for the various representations of trees and graphs.
- It is used in dynamic memory allocation( linked list of free blocks).
- It is used for representing sparse matrices.
- It is used for the manipulation of polynomials.
- It is also used for performing arithmetic operations on long integers.
- It is used for finding paths in networks.
- In operating systems, they can be used in Memory management, process scheduling and file system.
- Linked lists can be used to improve the performance of algorithms that need to frequently insert or delete items from large collections of data.
- Implementing algorithms such as the LRU cache, which uses a linked list to keep track of the most recently used items in a cache.
Applications of Linked Lists in real world:
- The list of songs in the music player are linked to the previous and next songs.
- In a web browser, previous and next web page URLs are linked through the previous and next buttons.
- In image viewer, the previous and next images are linked with the help of the previous and next buttons.
- Switching between two applications is carried out by using “alt+tab” in windows and “cmd+tab” in mac book. It requires the functionality of circular linked list.
- In mobile phones, we save the contacts of the people. The newly entered contact details will be placed at the correct alphabetical order. This can be achieved by linked list to set contact at correct alphabetical position.
- The modifications that we make in documents are actually created as nodes in doubly linked list. We can simply use the undo option by pressing Ctrl+Z to modify the contents. It is done by the functionality of linked list.
Advantages of Linked Lists:
Linked lists are a popular data structure in computer science, and have a number of advantages over other data structures, such as arrays. Some of the key advantages of linked lists are:
- Dynamic size: Linked lists do not have a fixed size, so you can add or remove elements as needed, without having to worry about the size of the list. This makes linked lists a great choice when you need to work with a collection of items whose size can change dynamically.
- Efficient Insertion and Deletion: Inserting or deleting elements in a linked list is fast and efficient, as you only need to modify the reference of the next node, which is an O(1) operation.
- Memory Efficiency: Linked lists use only as much memory as they need, so they are more efficient with memory compared to arrays, which have a fixed size and can waste memory if not all elements are used.
- Easy to Implement: Linked lists are relatively simple to implement and understand compared to other data structures like trees and graphs.
- Flexibility: Linked lists can be used to implement various abstract data types, such as stacks, queues, and associative arrays.
- Easy to navigate: Linked lists can be easily traversed, making it easier to find specific elements or perform operations on the list.
In conclusion, linked lists are a powerful and flexible data structure that have a number of advantages over other data structures, making them a great choice for solving many data structure and algorithm problems.
Disadvantages of Linked Lists:
Linked lists are a popular data structure in computer science, but like any other data structure, they have certain disadvantages as well. Some of the key disadvantages of linked lists are:
- Slow Access Time: Accessing elements in a linked list can be slow, as you need to traverse the linked list to find the element you are looking for, which is an O(n) operation. This makes linked lists a poor choice for situations where you need to access elements quickly.
- Pointers: Linked lists use pointers to reference the next node, which can make them more complex to understand and use compared to arrays. This complexity can make linked lists more difficult to debug and maintain.
- Higher overhead: Linked lists have a higher overhead compared to arrays, as each node in a linked list requires extra memory to store the reference to the next node.
- Cache Inefficiency: Linked lists are cache-inefficient because the memory is not contiguous. This means that when you traverse a linked list, you are not likely to get the data you need in the cache, leading to cache misses and slow performance.
- Extra memory required: Linked lists require an extra pointer for each node, which takes up extra memory. This can be a problem when you are working with large data sets, as the extra memory required for the pointers can quickly add up.
In conclusion, linked lists are a powerful and flexible data structure, but they have certain disadvantages that need to be taken into consideration when deciding whether to use them or not. For example, if you need fast access time, arrays might be a better choice, but if you need to insert or delete elements frequently, linked lists might be the better choice.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...