Linked List in Data Structures and Algorithms
This blog delves deeper into the implementation of linked lists, their relevance to data structures, and how they are applied in real-world scenarios.
·
Join the DZone community and get the full member experience.
Join For FreeIn the previous blog, we looked into different types of linear data structures. A linked list is also one of them. The program for linked lists seems to be lengthy, but once we are aware of the concept, It's easy to implement it. Linked lists are unlike stack and queues as it stores a pointer pointing to the address. For example, while we are listening to music on Spotify, we can create our song playlist and can play a song from both starting and end of the list. These music players are implemented using a linked list.
In this blog, we further discuss linked list implementation, how it is related to data structures, and its real-time applications.
What Is a Linked List?
A linked list is a linear data structure that includes a sequence of nodes connected. Here, a node contains two fields, i.e., data stored at that particular address and the pointer, which contains the address of the next node in the memory. We use dynamic memory allocation here instead of arrays, as its size is modifiable during the runtime.
Here we can see the first node is pointing toward the second node, the second node points third node, and so on. The head always points to the first node; for any operations, the head node changes accordingly. The last node has no node to point and contains a NULL value.
Let's now see how we can implement a single linked list using c.
We can perform various operations on a single linked list, and they are:
1. Adding Node at the Front
To add the node at the front, first, create a dynamic memory and allocate the value to the new node. Then point the new node toward the head, and store the new node's address in the head. In this way, we can add the node at the front.
void ins_beg(){
struct node *newnode = (struct node*)malloc(sizeof(struct node));
// allocate memory to new node.
newnode->data=item; // store value in data.
newnode->next=head; // store address of head in next
head = newnode;
}2. Deleting Node at the Front
To delete the node from the front, we have to store the 2nd node's address in the head.
void del_beg(){
struct node *newnode;
newnode = head;
head= newnode->next;
free(newnode); // free the node using free()
}3. Adding Node at the End
It is similar to adding a node at the front, but we have to point the last node to the new node and store the value. The new node inserted at the end contains a NULL value in the address node.
void ins_end(){
// allocate memory for new node.
temp = head;
while(temp->next !=NULL)
{
temp = temp->next;
}
// traverse till you reach the last node.
temp -> next = newnode;
newnode-> next = NULL; // NULL
}
4. Deleting Node at the End
To delete a node at the end, we must traverse the list and reach the end. We will use a pointer pointing toward the last 2nd node. Then free the last node.
id del_end(){
temp = head;
while(temp !=0)
{
temp = temp->next; // traverse till the end
}
ptr1 = temp; // ptr1 points the last 2nd node
temp = ptr1->next;
ptr1->next = NULL;
free(temp);
}5. Searching
We use it for searching for an element from the list.
void search(){
struct node *temp;
temp = head;
while(temp != NULL){
if(temp->data == key){
//found
}
else
{
//not found
}
temp = temp->next;
}
}We can create many other operations using a linked list.
Now, let's see the implementation of singly linked lists using the c program:
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node* next;
};
struct node *head;
void ins_beg();
void ins_end();
void del_beg();
void del_end();
void display();
int search();
void main(){
int choice=0;
while(choice!=7)
{
printf("enter choice:\n");
printf("\n1.ins_beg\n2.ins_end\n3.del_beg\n4.del_end\n5.display\n6.search\n7.exit");
scanf("%d", &choice);
switch(choice)
{
case 1:
ins_beg();
break;
case 2:
ins_end();
break;
case 3:
del_beg();
break;
case 4:
del_end();
break;
case 5:
display();
break;
case 6:
search();
break;
case 7:
printf("exiting...\n");
break;
default:
printf("unknown choice\n");
}
}
}
void ins_beg(){
int item;
struct node *newnode;
newnode = (struct node*)malloc(sizeof(struct node));
printf("enter item:");
scanf("%d", &item);
newnode->data=item;
newnode->next=head;
head = newnode;
printf("Inserted\n");
}
void ins_end(){
struct node *temp,*newnode;
int item;
newnode= (struct node*)malloc(sizeof(struct node));
printf("enter item");
scanf("%d", &item);
newnode->data = item;
if(head==NULL)
{
newnode->next =NULL;
head = newnode;
printf("inserted");
}
else
{
temp = head;
while(temp->next !=NULL)
{
temp = temp->next;
}
temp -> next = newnode;
newnode-> next = NULL;
printf("inserted");
}
}
void del_beg(){
struct node *newnode;
if(head == NULL)
printf("empty\n");
else
{
newnode = head;
head= newnode->next;
free(newnode);
printf("deleted\n");
}
}
void del_end(){
struct node *temp,*ptr1;
temp = head;
if(head==NULL)
{
free(head);
printf("deleted");
}
else{
while(temp !=0)
{
temp = temp->next;
}
ptr1 = temp;
temp = ptr1->next;
ptr1->next = NULL;
free(temp);
printf("deleted");
}
}
void display(){
struct node *newnode;
newnode = head;
if(newnode==NULL)
printf("empty");
else
{
printf("values are:\n");
while(newnode!=NULL)
{
printf("%d", newnode->data);
newnode = newnode ->next;
}
}
}
int search()
{
struct node *ptr;
int item,flag;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("Found");
flag= 1;
}
else
{
flag=2;
}
ptr = ptr -> next;
}
if(flag==2)
{
printf(" not found\n");
}
}
}The output for the program is as follows:
Till now, we discussed the implementation of a linked list. But where do we use it??
Applications of Linked Lists
- Play Next Track: The pointer to the next node makes it easy to start the next track when a track is over.
- Forward: Linked lists have a pointer that points toward the next node; it is easy to implement skip-forward functionality. We can also implement skip backward using a doubly linked list which we'll see in the next blog.
Conclusion
This blog gives us insight into the usage of a single linked list and its implementation. We can further learn about double-linked lists and circular-linked lists. I hope you enjoyed reading this blog. Please do like and comment on your views on today's topic. Happy learning!!
Do check my previous blogs on data structures, System integration using APIs:
Opinions expressed by DZone contributors are their own.
Comments