EDUCBA

EDUCBA

MENUMENU
  • Blog
  • Free Courses
  • All Courses
  • All in One Bundle
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Linked List Algorithm

Linked List Algorithm

Updated March 6, 2023

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.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

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.

Linked List Algorithm

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 –

Linked List Algorithm 1

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
All in One Excel VBA Bundle
500+ Hours of HD Videos
15 Learning Paths
120+ Courses
Verifiable Certificate of Completion
Lifetime Access
Financial Analyst Masters Training Program
2000+ Hours of HD Videos
43 Learning Paths
550+ Courses
Verifiable Certificate of Completion
Lifetime Access
All in One Data Science Bundle
2000+ Hour of HD Videos
80 Learning Paths
400+ Courses
Verifiable Certificate of Completion
Lifetime Access
All in One Software Development Bundle
5000+ Hours of HD Videos
149 Learning Paths
1050+ Courses
Verifiable Certificate of Completion
Lifetime Access
Primary Sidebar
All in One Data Science Bundle2000+ Hour of HD Videos | 80 Learning Paths | 400+ Courses | Verifiable Certificate of Completion | Lifetime Access
Financial Analyst Masters Training Program2000+ Hours of HD Videos | 43 Learning Paths | 550+ Courses | Verifiable Certificate of Completion | Lifetime Access
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2023 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

By continuing above step, you agree to our Terms of Use and Privacy Policy.
*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more