Linked lists are one of the most important data structures and these are the ones asked most in an interview. In this article, we are going to look into how types of linked lists.
Data Structure
A data structure is structuring and organizing data in a simple way so that data can be easily manipulated and managed. One example is accessing and inserting data in file systems and databases. The type of data structure to be used depends on various factors, such as the type of data, data access method e.g., serial access or random access, frequency of access, etc.
Linked List
A linked list is a type of data structure consisting of nodes. Each node consists of the
Value – this is the actual data. This can be an integer, float, string or a custom object such as a structure or a class object
Pointer – each node points to the next node within a single linked list object. The final node points to NULL.
A linked list is very similar to an array in the sense that it looks like a series of continuous data storage. However, there are some crucial differences between the two and each has its own advantages over the other.
Memory Allocation
Array
Arrays are allocated a series of memory. For eg., if an integer array has 10 elements and the starting address of an array is 100, then the final element will be stored at address 136.
Linked List
Linked lists elements may not be stored in contiguous memory. The pointer at each node helps to identify the location of the next node.
Size
Array
Due to the contiguous memory allocation, the size of an array must be predetermined. This usually leads to memory wastage as there is an overcompensation to avoid shortage.
Linked List
There is no need to determine the size of a linked list. This not only avoids memory wastage but is very useful when a programmer is unaware of how large the linked list can grow.
Insertion/Deletion
Array
Inserting or deleting an element in an array can be challenging if it is not the last element. Inserting or deleting an element in the middle of an array required moving the elements after that as well. In the worst-case scenario, if an element must be inserted at the beginning of the array then all elements must first be shifted one element to the right and only then can the new element be added. This may seem trivial for small arrays. However, if the array size is very large, this action itself will consume time and resources.
Linked List
Inserting or deleting an element in the middle does not require modifying other elements. A new node needs to be created and the pointer of the previous element needs to be updated. This simplifies the insertion/deletion process and makes the linked list more suitable for scenarios that are frequently updated.
Random Access
Array
When the position of the element is known, a read operation can be performed in O(1) time.
Linked List
Random access is not possible in a linked list. Even if the position is known before-hand the linked list must be traversed until that element. This becomes an issue when the size of the linked list is huge and the element to be found is in the last.
Cache Locality
Array
Arrays have better cache locality since they have contiguous memory locations. Consider an array that is accessed for reading. Once the first element is accessed, the next elements of the array can be cached for future usages, thereby reducing the read time. This saves time and resources
Linked List
Since the elements are randomly stored, it is a challenge to cache the linked list.
| Attribute | Array | Linked List |
| Memory allocation | Contiguous memory allocation | Random |
| Size | Fixed | Random |
| Insert/Delete | Time-consuming and modifying multiple elements | Direct creation/deletion of new element |
| Random access | Possible | Not possible |
| Cache locality | Possible | Not possible |
Table 1: Array vs Linked list
Table 1, provides a summary of the differences between array and linked list
Types Of Linked List
Singly Linked List
The singly-linked list is a simple linked list, where each node points to the next node and the final node points to NULL.
Figure 2: Single Linked List
Below is the code to create a singly linked list and perform insert, delete update and print operations.
#include<iostream>
using namespace std;
class node {
public:
int value;
node *next;
node(int val) {
value = val;
next = 0;
}
};
class singlyll {
node *head;
node *tail;
public:
singlyll() {
head = 0;
tail = 0;
}
void insert_at_head(int val) {
if (head == 0) {
head = tail = new node(val);
} else {
node *tmp = new node(val);
tmp->next = head;
head = tmp;
}
}
void insert_at_tail(int val) {
if (tail == 0) {
head = tail = new node(val);
} else {
tail->next = new node(val);
tail = tail->next;
}
}
void delete_at_head() {
if (head != 0) {
node *tmp = head;
if (head == tail) {
head = tail = 0;
} else {
head = head->next;
}
delete tmp;
}
}
void delete_at_tail() {
node *tmp;
for (tmp = head; tmp->next != tail; tmp = tmp->next);
if (tmp != 0) {
tail = tmp;
tail->next = 0;
tmp = tmp->next;
delete tmp;
}
}
void print() {
for (node *tmp = head; tmp != 0; tmp = tmp->next) {
cout<<tmp->value<<" ";
}
}
};
int main() {
singlyll sll;
sll.insert_at_head(10);
sll.insert_at_head(20);
sll.insert_at_tail(30);
sll.delete_at_head();
sll.delete_at_tail();
sll.print();
}Doubly Linked List
A doubly linked list is the linked list in which each node points to both the next element and the previous element.
Figure 3: Doubly Linked List
Note that the first element has its previous pointer to NULL and the last element has its next pointer to NULL.
Circular Linked List
A circular linked list can be singly or doubly linked list, depending on whether it has a previous pointer or not. But the last element points back to the first element, thereby, creating a circle.
Figure 4: Circular Linked List
If you like the article please share and subscribe. This is all for now in types of linked lists. You can also look into this.
