Last Updated on October 11, 2022 by Ria Pathak
The linked list is one of the most important concepts in data structures and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.
What is a Linked List?
A linked list is a linear Data Structure, consisting of a group of nodes stored at random addresses. In a linked list the elements are linked using pointers.
Every node stores the data and address of the next node. Every node consists of 2 parts:
Data: The Data which is stored at a particular address.
Reference: The address of the next node of the linked list.
Linked List Representation
Linked list can be represented as the connection of nodes in which each node points to the next node of the list. Below is the representation of the linked list
Till now, we have discussed the array data structure to organize the group of elements that are to be stored individually in the memory. However, Array has several advantages and disadvantages that must be known to decide the data structure that will be used throughout the program.
Types of Linked Lists
There are three common types of linked list .
- Singly Linked List
- Doubly Linked List
- Circular Linked List
Singly Linked List
A singly list is a linked list that is unidirectional, i.e. it can be traversed in only one direction starting from the head of the linked list to the end node (tail). In a Singly Linked List, every node contains:
A data field.
An address field points to the next node.
struct Node {
int data;
struct Node* next;
};
class Node{
public:
int data;
Node* next;
};
class Node
{
int data;
Node next;
}
class Node:
def __init__(self, next=None, data=None):
self.data = data
self.next = next
Doubly Linked List
A doubly linked list is a type of linked list in which a pointer of the previous node as well as the next node in the sequence. A doubly linked list consists of three parts: node data, pointer to the previous node, pointer to the next node.
In a Doubly Linked List, a particular node contains:
A data field.
Two address fields next and prev, next points to the immediate next node in the linked list, and prev points to the immediate previous node in the linked list.
struct Node {
int data;
struct DLLNode* next;
struct DLLNode* prev;
};
class DLLNode{
public:
int data;
DLLNode* next;
DLLNode* prev;
};
class DLLNode
{
int data;
DLLNode prev;
DLLNode next;
}
class DDLNode:
def __init__(self, next=None, prev=None, data=None):
self.data = data
self.prev = prev
self.next = next
Circular Linked List
In a Circular Linked List, instead of pointing to NULL, the last node points to the head of the linked list. Hence, the name circular linked list. The main advantage of a circular linked list is that we can consider any node as the starting node and traverse the list.
struct Node {
int data;
struct Node* next;
};
class Node{
public:
int data;
Node* next;
};
class Node
{
int data;
Node next;
}
class Node:
def __init__(self, next=None, data=None):
self.data = data
self.next = next
Now, you might have the question, why should we use linked lists over arrays?
Why Linked List?
Although using arrays, we can store the same types of data; we can access elements directly using the index; however, they have the following drawbacks.
1. The arrays have a fixed size: As a result, we must know the maximum amount of elements ahead of time. In addition, regardless of use, the allocated memory is always equal to the maximum limit.
2. Inserting a new element into an array at some middle position is costly since space must be made for the new elements, and old elements must be shifted to make room.
3. Also deleting an element from an array is costly as it too requires shifting of array elements.
Basic Operations of Linked List:
-
Insertion: This operation is used to add an element to the linked list.
-
Insertion of a node of a linked list can be on three positions i.e. Insertion at the beginning, Insertion at the end, and Insertion in the middle of the list.
-
Deletion: Deletion operations are used to remove an element from the beginning of the linked list. You can also do delextion in the linked list in three ways either from the end, beginning, or from a specific position.
-
Search: A search operation is used to search an element using the given key.The search operation is done to find a particular element in the linked list. If the element is found in any location, then it returns. Else, it will return null.
-
Display: Display operation is used to display the linked list.display() will display the nodes present in the list.
Complexity of Linked list
Now, let’s see the time and space complexity of the linked list for the operations search, insert, and delete.
Time Complexity
| Operations | Average case time complexity | Worst-case time complexity |
|---|---|---|
| Insertion | O(1) | O(1) |
| Deletion | O(1) | O(1) |
| Search | O(n) | O(n) |
Where ‘n’ is the number of nodes in the given tree.
Space Complexity
| Operations | Space complexity |
|---|---|
| Insertion | O(n) |
| Deletion | O(n) |
| Search | O(n) |
The space complexity of the linked list is O(n).
Advantages of Linked List
- Dynamic Data Structure: Linked List being a dynamic data structure can shrink and grow at the runtime by deallocating or allocating memory. So, there is no need for initial size.
- No Memory Wastage: As the size of a linked list can grow or shrink at runtime, there is no memory wastage. Only the required memory is allocated.
- Implementation: Some very helpful data structures like queues and stacks can easily be implemented using a Linked List.
- Insertion and Deletion Operation: In a Linked List, insertion and deletion operations are quite easy, as there is no need to shift every element after insertion or deletion. Only the address present in the pointers needs to be updated.
Disadvantages of Linked List
- Memory Usage: The memory required by a linked list is more than the memory required by an array, as there is also a pointer filed along with the data field in the linked list. The pointer field requires memory to store the address of the next node.
- Random Access: To access nodes at index x in a linked list, we have to traverse through all the nodes before it. In the case of an array, we can directly access an element at index x using arr[x].
- Reverse Traversal: In a singly linked list, reverse traversal is not possible, as every node stores only the address of the next node. But in the case of a doubly-linked list, reverse traversal is possible, but it consumes more memory, as we have to allocate extra memory to store the previous pointer.
Applications of the linked list:
- A linked list is used to implement the stacks and queues.
- A linked list is also used in implementation of the adjacency matrix graph.
- A linked list is used for the dynamic memory location.
- A linked list makes the multiplication of the polynomial operations easy.
Read more about Linked List:
- Advantage and Disadvantage of Linked List over Array.
- Adding two polynomials using Linked List.
- Add two numbers represented by linked lists.
- Method to print the reverse of a linked list.
- How to arrange consonants and vowels nodes in a linked list.
- Bubble Sort for Linked List by Swapping Nodes.
- Bubble Sort on Doubly Linked List.
- Convert a given Binary Tree to Doubly Linked List.
- How to implement a stack using a singly linked list.
- Insertion Sort for Doubly Linked List.
- Insertion Sort for Singly Linked List.
So, in this article, we gave you a brief introduction to Linked Lists. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.