Linked List Algorithm

Introduction to Linked List Algorithm

Linked list algorithm is a data structure algorithm that is linear in nature and does not store the data in the sequential memory locations. Instead, data of the linked list can be present in the completely scattered format in the memory. In linked list each node consists of two things – one is the data that needs to be stored in that element of the list and the other one is the address of the next node which is linked to the current node. There are two pointers that help us maintaining transactions and pointing to the exact element to which we wish to. After array. The linked list is the second most data structure used to a large extent.

In this article, we will study the general visual representation of the structure of linked list to understand its internal storage mechanism and algorithm working, operations on it, and the implementation with the help of an example that will demonstrate the usage in C programming language.

Structure of Linked List

A linked list consists of one or more nodes also called links. Each link is a pair of two things one is the data part which holds the value of the element which needs to be stored in the linked list while the second part is the next which stores the address of the next link or node to which it pints too. The starting node or link is known as the head. The last node has its next part pointing to the null as there is no further node to be pointed which marks the end of the linked list as shown in the below figure.

As shown above, each node contains the data field and the reference field. A linked list can contain any number of nodes depending on the data which we need to store and the memory capacity that is available. One of the advantages of the structure of the linked list is that it does not require the availability of the sequential empty space in the memory as required for arrays. The nodes of the linked list can be stored anywhere wherever there is empty space available in the memory.

Operations to be carried by linked list algorithm

We can perform the following operations on the linked list algorithm:

Insert – We can add the new elements to store the additional data in the list in the beginning of the list.
Delete – We can remove the beginning existing element of the linked list.
Show – We can retrieve all the data of the linked list at once to observe the current status and contents of the list.
While carrying on any of the above operations, it involves manipulating all the references and the pointers of the start and the next as the data node needs to be removed from the linking framework of the linked list. You can understand the actual manipulation to be carried out for each of the individual operations to be carried out by studying the below program in C language.

Implementation of linked list Algorithm

The linked list algorithm is used programmatically by following certain logics and operations for manipulating the pointers. In order to understand this, let us take an example of the linked list algorithm in C programming language which allows the usage of pointers for referencing the addresses of memory locations. The steps and actions performed at each of the procedures in the linked list algorithm are mentioned in the comments.

#include <stdio.h>
#include <stdlib.h>
struct DataNode {
int item;
struct DataNode* next;
};
void insertFromStart(struct DataNode** reference, int data) {
// Memory allocation of the data node of the linked list
struct DataNode* new_DataNode = (struct DataNode*)malloc(sizeof(struct DataNode));
// Add a new element in the linked list
new_DataNode->item = data;
new_DataNode->next = (*reference);
// Change the head referenceerence to new data node in the linked list
(*reference) = new_DataNode;
}
// Add a new data node after the other
void insertAfterCurrentDataNode(struct DataNode* DataNode, int data) {
if (DataNode == NULL) {
printf("the given previousious DataNode cannot be NULL");
return;
}
struct DataNode* new_DataNode = (struct DataNode*)malloc(sizeof(struct DataNode));
new_DataNode->item = data;
new_DataNode->next = DataNode->next;
DataNode->next = new_DataNode;
}
void insertFromLast(struct DataNode** reference, int data) {
struct DataNode* new_DataNode = (struct DataNode*)malloc(sizeof(struct DataNode));
struct DataNode* last = *reference;
new_DataNode->item = data;
new_DataNode->next = NULL;
if (*reference == NULL) {
*reference = new_DataNode;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_DataNode;
return;
}
void deleteDataNode(struct DataNode** reference, int key) {
struct DataNode *temporary = *reference, *previous;
if (temporary != NULL && temporary->item == key) {
*reference = temporary->next;
free(temporary);
return;
}
// Search for the key of the element which is to be removed
while (temporary != NULL && temporary->item != key) {
previous = temporary;
temporary = temporary->next;
}
// if the key of element is not present
if (temporary == NULL) return;
// remove the linkage of the data node from the list
previous->next = temporary->next;
free(temporary);
}
// Display the contents of the linked list
void showData(struct DataNode* DataNode) {
while (DataNode != NULL) {
printf(" %d ", DataNode->item);
DataNode = DataNode->next;
}
}
// The main controller of the program
int main() {
struct DataNode* head = NULL;
insertFromLast(&head, 1);
insertFromStart(&head, 2);
insertFromStart(&head, 3);
insertFromLast(&head, 4);
insertAfterCurrentDataNode(head->next, 5);
printf("Contents of the linked list right now : ");
showData(head);
printf("\nContents of the linked list after deleting an element from it : ");
deleteDataNode(&head, 3);
showData(head);
}

The output of the above program is as shown below –

Advantages and Disadvantages of Linked List Algorithm

Advantages	Disadvantages
Runtime allocation of the memory helps to increase and decrease the size of data structure easily that leads to the dynamic data structure.	Extra memory usage is involved because along with the data field the references also need to be stored which adds to consumption.
Adding and removing the item from the list is very easy as it involves only changing the references.	Traversing the nodes becomes time-consuming.
Memory is not at all wasted because no sequential memory locations are reserved for the data structure. Each element can be stored at any location.	In doubly linked list the reverse traversing is easy as the references to previous data nodes are also done. But in the case of a singly linked list reverse traversing is very tough especially if the number of nodes stored in the list is huge.
Implementation of a linked list can be easily done by using stack and queues.

Conclusion

The linked lists are used to store the data and is one of the linear data structures. It maintains the references on the next data node and can also contain the reference for previous data nodes in case of a doubly linked list. Linked list the second most used data structure after array.

Recommended Articles

This is a guide to Linked List Algorithm. Here we discuss the Introduction, Structure, operations, Advantages, and Disadvantages of Linked List Algorithm. You may also have a look at the following articles to learn more –

1. Pseudocode Algorithm
2. Pattern Recognition Algorithms
3. Page Replacement Algorithms
4. Bubble Sort Algorithm