Linked Lists
Linked List is a linear data structure like stack and array. Unlike arrays, linked list elements are not stored at contiguous locations in memory. Each element (say a node) in a linked list has two parts - one is the data part that stores the input data and the other is the next part which is basically a pointer variable that stores the memory address of the next element. All the elements in a linked list are linked using pointers. An individual without the working knowledge of pointers and memory allocation in C must not begin learning linked lists.
Why Linked Lists? #
In array, elements are stored in contiguous blocks of memory. This spacial locality in memory greatly benefits from modern CPU caching methods. Array provides faster, random access \(O(1)\) to any of its elements using sub-scripted variable \((a[ i ])\).
//total 5 array elements
int array[5] = {9,6,1,3,2};
//access and print each element
for(i=0; i<5; i++)
printf("%d ", a[i]);
It is simple and easy to use. As array size is static, when it comes to dynamic allocation, array fails to make you comfortable. Insertion and deletion of elements in an array is expensive, it needs copying and shifting of existing elements every time.
Then, there are linked lists. They are of dynamic size and hence don’t waste memory but takes some extra memory for pointers. Insertion and deletion can be carried out easily. They can grow in size until system memory exhausts. But, they don’t allow random access to elements rather allows sequential access \(O(n)\). Sequential access is like - a roll of paper where all prior material must be unrolled in order to get to the sheet you want.
As both of them are used to store collections of data, we generally prefer using Linked Lists when we need ease in inserting and deleting elements, and when run time efficiency is much more important then using arrays is obvious.
Linked list has mainly two operations - insertion (inserting data) and deletion (deleting data). The first node is called head and the last node is called tail.
Commonly, linked lists are of three types:-
- Singly Linked List - Unidirectional, each node has a pointer to its successor, tail points to NULL.
- Doubly Linked List - Bidirectional, each node has pointer both to predecessor and successor, tail points to NULL.
- Circular Linked List - Tail points to head. It inherits properties from the other two linked lists to form singly circular and doubly circular linked list.
Singly linked list in C #
#include<stdio.h>
#include<stdlib.h>
typedef struct node //globally declared structure
{
int data;
struct node *next; //self-referencing pointer, to know more refer C programming book by D. Ritchie
}node;
void main()
{
int choice, data, reply, position;
node *head;
head=NULL; //Empty Linked List created
do
{
printf("\n1. Insert an element.");
printf("\n2. Delete an element.");
printf("\n3. Display the contents of the Linked List.");
printf("\n4. Delete the whole list.");
printf("\n5. Exit.");
printf("\nEnter your choice:- ");
scanf("%d", &choice);
switch(choice)
{
case 1:
{
printf("\nEnter the position:- ");
scanf("%d", &position);
printf("\nEnter the data:- ");
scanf("%d", &data);
reply=insertnode(&head, position, data); //to update head's value in both functions, pass it by reference
if(reply==1)
printf("\nValue Inserted.\n");
else
printf("\nMemory allocation failed!\nTry again!\n");
break;
}
case 2:
{
printf("\nEnter the position of node to delete:- ");
scanf("%d", &position);
reply=deletenode(&head, position);
if(reply==0)
printf("\nThe List is empty.\n");
else if(reply==1)
printf("\nDeleted.\n");
else
printf("\nThe entered position doesn't exist.\n");
break;
}
case 3:
{
display(head);
break;
}
case 4:
{
deletelist(&head);
break;
}
case 5:
exit(0);
default:
{
printf("\nInvalid Input. Try Again.\n");
break;
}
}
}while(1);
}
int insertnode(node **head, int position, int data)
{
int k=1;
node *p, *q, *newnode;
newnode=(node*)malloc(sizeof(node)); //to create a memory block for a new node
if(!newnode) //if malloc fails
return 0;
newnode->data=data; //storing the input data in the new node of the LL
p=*head; //here * is used as value at operator. head is copied to p
//Inserting at the beginning
if(position==1||p==NULL)
{
newnode->next=p; //p contains the address of head. Now, newnode->next stores the address of head
*head=newnode; //after insertion is done, new node is the head of the LL
return 1; //show value inserted
}
else
{
//Traverse LL until the position where we want to insert
while((p!=NULL)&&(k<position))
{
k++; //just a counter, counting nodes in LL
q=p; //q is position node it is updated as p is traversing the nodes in LL
p=p->next; //fetching the next pointer and storing it in p
}
q->next=newnode;
newnode->next=p;
return 1; //show value inserted
}
}
int deletenode(node **head, int position)
{
int k=1;
node *p, *q;
if(*head==NULL) //when list is empty
return 0;
p=*head;
//From beginning
if(position==1)
{
*head=(*head)->next; //updating next node as head
free(p);
return 1;
}
else
{
//Traverse the list until the position from which we want to delete
while((p!=NULL)&&(k<position))
{
k++;
q=p;
p=p->next;
}
if(p==NULL) //At the end
return -1; //position does not exist
else //From middle
{
q->next=p->next;
free(p);
return 1;
}
}
}
void display(node *node)
{
int i=1;
if(node==NULL)
printf("\nThe List is empty.\n");
else
{
while(node!=NULL)
{
printf("Element %d - %d\n", i++, node->data);
node=node->next;
}
}
}
void deletelist(node **head)
{
node *temp, *p;
p=*head;
if(*head==NULL)
printf("\nThe list is empty.\n");
else
{
while(p!=NULL)
{
temp=p->next;
free(p);
p=temp;
}
*head=NULL; //will affect the real head in the caller as head was called by reference
printf("\nThe Linked List has been deleted.\n");
}
}
Doubly linked list in C #
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *prev;
struct node *next;
}node;
void main()
{
int choice, data, position, reply;
node *head;
head=NULL; //Empty Doubly LL created
do
{
printf("\n1. Insert an element.");
printf("\n2. Delete an element.");
printf("\n3. Display the contents of the Linked List.");
printf("\n4. Delete the whole list.");
printf("\n5. Exit.");
printf("\nEnter your choice:- ");
scanf("%d", &choice);
switch(choice)
{
case 1:
{
printf("\nEnter the position:- ");
scanf("%d", &position);
printf("\nEnter the data:- ");
scanf("%d", &data);
reply=insertnode(&head, position, data); //to update head's value in both functions, pass it by reference
if(reply==1)
printf("\nValue Inserted.\n");
else
printf("\nMemory allocation failed!\nTry again!\n");
break;
}
case 2:
{
printf("\nEnter the position of node to delete:- ");
scanf("%d", &position);
reply=deletenode(&head, position);
if(reply==0)
printf("\nThe List is empty.\n");
else if(reply==1)
printf("\nDeleted.\n");
else
printf("\nThe entered position doesn't exist.\n");
break;
}
case 3:
{
display(head);
break;
}
case 4:
{
deletelist(&head);
break;
}
case 5:
exit(0);
default:
{
printf("\nInvalid Input. Try Again.\n");
break;
}
}
}while(1);
}
int insertnode(node **head, int position, int data)
{
int k=1;
node *p, *q, *newnode;
newnode=(node*)malloc(sizeof(node)); //to create a memory block for a new node
if(!newnode) //if malloc fails
return 0;
newnode->data=data; //storing the input data in the new node of the LL
//Insertion at the beginning
if(position==1||*head==NULL)
{
newnode->prev=0;
newnode->next=*head;
if(*head) //if head is not NULL
(*head)->prev=newnode;
*head=newnode; //after insertion is done, new node is the head of the LL
return 1; //show value inserted
}
else
{
p=*head; //p is current node. here * is used as value at operator. head is copied to p
//Traverse LL until the position where we want to insert
while((p!=NULL)&&(k<position))
{
k++;
q=p;
p=p->next;
}
newnode->prev=q;
newnode->next=p;
q->next=newnode;
if(p) //if p is not NULL
p->prev=newnode;
return 1;
}
}
int deletenode(node **head, int position)
{
int k=1;
node *p, *q, *temp;
if(*head==NULL) //when list is empty
return 0;
if(position==1)
{
p=*head;
*head=(*head)->next;
if(*head) //if head is not NULL
(*head)->prev=NULL;
free(p);
return 1;
}
else
{
p=*head;
//Traverse the list until the position from which we want to delete
while(p!=NULL && k<position)
{
k++;
q=p;
p=p->next;
}
if(p==NULL) //At the end
return -1; //position does not exist
else //From middle
{
temp=p;
q->next=p->next;
if(p->next)
p->next->prev=q; //the prev part of p->next must point to the previous node
free(temp);
return 1;
}
}
}
void display(node *node)
{
int i=1;
if(node==NULL)
printf("\nThe List is empty.\n");
else
{
while(node!=NULL)
{
printf("Element %d - %d\n", i++, node->data);
node=node->next;
}
}
}
void deletelist(node **head)
{
node *temp, *p;
p=*head;
if(*head==NULL)
printf("\nThe list is empty.\n");
else
{
while(p!=NULL)
{
temp=p->next;
free(p);
p=temp;
}
*head=NULL; //will affect the real head in the caller as head was called by reference
printf("\nThe Linked List has been deleted.\n");
}
}