Linked List
What is a Linked List?
A linked list is a linear data structure in which each element is a separate object that is connected to the next element by means of a pointer. The elements in a linked list can grow or shrink in size dynamically. Linked lists are often used to implement data structures such as stacks, queues, and associative arrays.
Linked lists are made up of nodes, which are structures that contain data and a reference (or pointer) to the next node in the list. The head and tail of a list are the first and last nodes, respectively. Each node in the list is connected to the next node by its reference. In order to traverse the list, you start at the head node and follow the references to each successive node until you reach the tail node.
The pointer will store the address of the next node.
When insertion and deletion operations are frequent, linked lists are typically favoured over arrays because they are quicker and simpler to operate.
However, linked lists require more memory than arrays since each node requires storage space for both its data and its reference. Additionally, linked lists are not always as efficient as arrays when searching for elements.
Types of Linked Lists
There are four key types of linked lists:
- Singly-linked lists:
A singly linked list is a type of data structure in which each node contains a pointer to the next node in the sequence, as well as data. This type of linked list is linear in nature, as each node is only connected to the next node in the sequence.
- Doubly linked lists: A doubly linked list is a type of data structure in which each node contains a pointer to the previous node in the sequence and the next node in the sequence, as well as data. This type of linked list is more versatile than a singly linked list, as it allows for traversal in both directions.
- Circular linked lists: A circular linked list is a type of data structure in which the last node in the sequence points back to the first node in the sequence, thus creating a loop. This type of linked list can be used for applications where an algorithm needs to traverse the entire list before stopping.
- Circular doubly linked lists: A circular two-way linked list, commonly referred to as a doubly circular linked list, is a more complex form of a linked list that has a pointer to both the next and previous node in the sequence. Similar to the distinction between a singly linked list and a circular linked list, there is no difference between a doubly linked list and a circular doubly list. The previous field of the first node of the circular doubly linked list does not contain null.
Implementing a Linked List in C++
/* defining structure of a Node.
Each node has
1. Integer variable to store the data.
2. Pointer variable, to store the address of next node.
*/
struct Node {
int data;
Node *next;
Node(int x) {
data = x;
next = NULL;
}
};
int main(){
Node *head;
head = new Node(3); // creating a Node with data as '3'
// LinkedList is [3]-> NULL
Node *p;
p = head; // pointer p is pointing to head node
/* LINKED LIST CREATION */
for(int i=0;i<3;i++){
p->next = new Node(i+4); // creating a new node and assigning it to p's next.
p = p->next; // p will now point to next element
}
// LL now is [3]->[4]->[5]->[6]->NULL
/* TRAVERSAL OPERATION IN LL */
p = head;
// when 'p' reaches NULL, it means end of LL is reached.
int i = 1;
while(p != NULL)
{
cout<<"For node "<<i<<" data is = "<< p->data <<endl;
p = p->next; i++;
}
// Also note the size of LL is i-1
cout<<"Size of LL = "<< i-1<<endl;
/* SEARCH OPERATION IN LL */
p = head;
// search for data '5'
while(p != NULL)
{
if(p->data == 5){
cout<<"node found\n";
break; // break as element is found.
}
p = p->next; i++;
}
}
Operations on Linked Lists
Traversal: To traverse means to go through each node one at a time.
/* TRAVERSAL OPERATION IN LL */
p = head;
// when 'p' reaches NULL, it means end of LL is reached.
int i = 1;
while(p != NULL)
{
cout<<"For node "<<i<<" data is = "<< p->data <<endl;
p = p->next; i++;
}
Insertion: The addition of a node at a certain location.
/* INSERTION OPERATION IN LL */
p = head;
// Insert at 3rd location
int pos = 3, i=1;
Node* prev;
if(pos == 1)
{ p = new Node(0);
p->next = head;
//now make this added node as head, because it is in 1st location.
head = p;
}
else{
while(p != NULL)
{
if(i == pos){
// prev is 2nd Node
// p is 3rd Node
prev->next = new Node(0);
prev->next->next = p;
break; // break as node is inserted.
}
prev = p;
p = p->next; i++;
}
}
Removal: To remove a node.
/* Removal OPERATION IN LL */
p = head;
// Removal at 3rd location
int pos = 3, i=1;
Node* prev;
if(pos == 1) // i.e head node is to be removed
{
head = head->next;
//i.e just point to the next node
}
else{
while(p != NULL)
{
if(i == pos){
// prev is 2nd Node
// p is 3rd Node
prev->next = p->next;
// i.e 2nd node will point to 4th node, there by removing 3rd node from LL
break; // break as node is removed.
}
prev = p;
p = p->next; i++;
}
}
Searching: To value-search an element or elements.
/* SEARCH OPERATION IN LL */
p = head;
// search for data '5'
while(p != NULL)
{
if(p->data == 5){
cout<<"node found\n";
break; // break as element is found.
}
p = p->next;
}
Update: To change a node’s state.
Sorting: Putting linked list nodes in a particular order.
merging: the act of joining two linked lists together.
Advantages of Linked Lists
- Ease of Insertion and Deletion: Linked lists are dynamic in nature which allows elements to be added or removed easily at any given point in the list. This is very convenient and saves time when compared to other data structures like arrays which require elements to be shifted accordingly.
- Memory Efficiency: Linked lists use much less memory as compared to other data structures like arrays. This is because linked lists only store the address or reference of the next node instead of storing the entire data of the node.
- Flexibility: Linked lists are very flexible and can be easily manipulated as needed. Elements can be inserted or removed at any position in the list with relative ease.
Disadvantages of Linked Lists
- Random Access is not allowed: Linked lists do not allow random access, meaning that elements cannot be accessed directly as compared to arrays. This makes it difficult to search for a particular element or node.
- Extra Memory Space Required: Linked lists require extra memory space for the address or reference of the next node. This can be a disadvantage in terms of memory efficiency.
- Time Complexity: Linked lists have a time complexity of O(n) for searching, inserting, and deleting elements as compared to arrays which have a time complexity of O(1) for these operations. This means that linked lists are slower than arrays in terms of these operations.
Applications of Linked Lists
Linked Lists are one of the most commonly used and versatile data structures in computer science. They are used in many different applications, from implementing queues and stacks to creating graphs.
- Dynamic Memory Allocation: Linked lists are handy for dynamic memory allocation, which is the process by which computer programs request memory from the operating system during runtime. By using a linked list, memory can be allocated in small chunks as needed, which is more efficient than allocating large chunks of memory at once. Furthermore, since linked lists can be easily traversed, it is easy to find a specific chunk of memory when needed.
- Caches: Linked lists are also used to implement caches. Caches are data structures used to store recently used information so that it can be quickly retrieved when needed. By using a linked list, it is easy to keep track of recently used information and quickly access it.
- Searching and Sorting: Linked lists can also be used to search and sort items. Since linked lists are easily traversed and manipulated, it is easy to search for a particular item in a linked list and sort a linked list by rearranging the nodes.
- Graphs: Linked lists are also used to represent graphs. Graphs are data structures used to represent relationships between different items. By using a linked list, it is easy to store the edges (connections) between different nodes in a graph.
- Queues: Linked lists are also used to implement queues. Queues are data structures used to store items in an order and retrieve them in the same order. By using a linked list, it is easy to add and remove items from the queue in an efficient manner.
- Stacks: Linked lists are also used to implement stacks. Stacks are data structures used to store items in an order and retrieve them in reverse order. By using a linked list, it is easy to push and pop items from the stack in an efficient manner.