Data Structure and Algorithms - Linked List

In a game of Treasure Hunt, you start by looking for the first clue. When you find it, instead of having the
treasure, it has the location of the next clue and so on. You keep following the clues until you get to the
treasure.

A linked list is similar. It is a series of connected "nodes" that contains the "address" of the next node. Each
node can store a data point which may be a number, a string or any other type of data.

Linked List vs. Array

Array is a datatype which is widely implemented as a default type, in almost all the modern programming
languages, and is used to store data of similar type.

But there are many use cases, like the one where we don't know the quantity of data to be stored, for which
advanced data structures are required, and one such data structure is linked list.

ARRAY LINKED LIST

Insertions and deletions are difficult. Insertions and deletions can be done easily.
It needs movements of elements for insertion and It does not need movement of nodes for insertion and
deletions. deletion.
In it space is wasted. In it space is not wasted.
It is more expensive. It is less expensive.
It requires less space as only information is stored. It requires more space as pointers are also stored along
with information.
Its size is fixed. Its size is not fixed.
It cannot be extended or reduced according to It can be extended or reduced according to
requirements. requirements.
Same amount of time is required to access each Different amount of time is required to access each
element. element.
Elements are stored in consecutive memory Elements may or may not be stored in consecutive
locations. memory locations.
If have to go to a particular element then we can If we have to go to a particular node then we have to go
reach their directly. through all those nodes that come before that node.

Below we have a pictorial representation showing how consecutive memory locations are allocated for array,
while in case of linked list random memory locations are assigned to nodes, but each node is connected to its
next node using pointer.

On the left, we have Array and on the right, we have Linked List.

Why we need pointers in Linked List?

In case of array, memory is allocated in contiguous manner, hence array elements get stored in consecutive
memory locations. So when you have to access any array element, all we have to do is use the array index, for
example arr[4] will directly access the 5th memory location, returning the data stored there.

But in case of linked list, data elements are allocated memory at runtime; hence the memory location can be
anywhere. Therefore to be able to access every node of the linked list, address of every node is stored in the
previous node, hence forming a link between every node.

We need this additional pointer because without it, the data stored at random memory locations will be lost.
We need to store somewhere all the memory locations where elements are getting stored.

Yes, this requires an additional memory space with each node, which means an additional space of O(n) for
every n node linked list.

Introduction

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The
elements in a linked list are linked using pointers as shown in the below image:

In simple words, a linked list consists of nodes where each node contains a data field and a reference (link) to
the next node in the list.

A linked list is a sequence of data structures, which are connected together via links.

Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked
list is the second most-used data structure after array. Following are the important terms to understand the
concept of Linked List.

Link − Each link of a linked list can store a data called an element.

Next − Each link of a linked list contains a link to the next link called Next.

LinkedList − A Linked List contains the connection link to the first link called First.

Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a
contiguous location; the elements are linked using pointers.

Why Linked List?

Arrays can be used to store linear data of similar types, but arrays have the following limitations.

 The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also,
generally, the allocated memory is equal to the upper limit irrespective of the usage.

 Inserting a new element in an array of elements is expensive because the room has to be created for the
new elements and to create room existing elements have to be shifted.

For example, in a system, if we maintain a sorted list of IDs in an array id[].

id[] = [1000, 1010, 1050, 2000, 2040].

 And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements
after 1000 (excluding 1000). Deletion is also expensive with arrays until unless some special techniques are
used. For example, to delete 1010 in id[], everything after 1010 has to be moved.

Why use linked list over array?

Till now, we were using array data structure to organize the group of elements that are to be stored individually
in the memory. However, Array has several advantages and disadvantages which must be known in order to
decide the data structure which will be used throughout the program.

Array contains following limitations:

1. The size of array must be known in advance before using it in the program.

2. Increasing size of the array is a time taking process. It is almost impossible to expand the size of the
array at run time.

3. All the elements in the array need to be contiguously stored in the memory. Inserting any element in the
array needs shifting of all its predecessors.

Linked list is the data structure which can overcome all the limitations of an array. Using linked list is useful
because,

1. It allocates the memory dynamically. All the nodes of linked list are non-contiguously stored in the
memory and linked together with the help of pointers.

2. Sizing is no longer a problem since we do not need to define its size at the time of declaration. List
grows as per the program's demand and limited to the available memory space.

Points to be noted for linked list

 The nodes in a linked list are not stored contiguously in the memory.
 You don’t have to shift any element in the list.
 Memory for each node can be allocated dynamically whenever the need arises.
 The size of a linked list can grow or shrink dynamically.

Drawbacks of Linked List:

 Random access is not allowed. We have to access elements sequentially starting from the first node. So we
cannot do binary search with linked lists efficiently with its default implementation.
 Extra memory space for a pointer is required with each element of the list.
 Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not
there in case of linked lists.

Linked List Representation

A linked list is represented by a pointer to the first node of the linked list. The first node is called the head. If the
linked list is empty, then the value of the head is NULL. Each node in a list consists of at least two parts:

 Data
 Pointer (Or Reference) to the next node

Self-referential structure

In C, we can represent a node using structures.

It is sometimes desirable to include within a structure one member that is a pointer to the parent structure type.
Hence, a structure which contains a reference to itself is called self-referential structure. In general terms, this
can be expressed as:

struct Node {
member 1;
member 2;
.....
struct Node* name;
};

// A linked list node

struct Node {
int data; //int info
struct Node* next;
};

This is a structure of type node. The structure contains two members: a info integer member, and a pointer to a
structure of the same type (i.e., a pointer to a structure of type node), called next. Therefore, this is a self-
referential structure.

Linked list can be visualized as a chain of nodes, where every node points to the next node.

As per the above illustration, following are the important points to be considered.

 Linked List contains a link element called first.

 Each link carries a data field(s) and a link field called next.
 Each link is linked with its next link using its next link.
 Last link carries a link as null to mark the end of the list.

Linked list as an ADT

A linked list of n-nodes with n-elements of type T is a sequence of elements of T together with the operations:

 Create(): Create or make a node

 Insert(x): Insert x to linked list
 Delete(): If linked list is not empty then delete given node.
 Traverse(): Display all of the nodes of given linked list.
 IsEmpty(): Determine whether linked list is empty or not. Return true if it is empty; return false otherwise.
 Find() or Search(): Find out given node from linked list.
 Count(): Count number of nodes of given linked list
 Free(): Release memory space of given node of linked list.

First Simple Linked List in C

Let us create a simple linked list with 3 nodes.

// A simple C program to introduce

// a linked list
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

// Program to create a simple linked

// list with 3 nodes
int main()
{
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;

// allocate 3 nodes in the heap

head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
 /* Three blocks have been allocated dynamically.
We have pointers to these three blocks as head,
second and third
head second third
| | |
| | |
+---+-----+ +----+----+ +----+----+
| # | # | | # | # | | # | # |
+---+-----+ +----+----+ +----+----+

# represents any random value.

Data is random because we haven’t assigned
anything yet */

head->data = 1; // assign data in first node

head->next = second; // Link first node with
// the second node

/* data has been assigned to the data part of the first

block (block pointed by the head). And next
pointer of first block points to second.
So they both are linked.

head second third

| | |
| | |
+---+---+ +----+----+ +-----+----+
| 1 | o----->| # | # | | # | # |
+---+---+ +----+----+ +-----+----+
*/

// assign data to second node

second->data = 2;

// Link second node with the third node

second->next = third;

/* data has been assigned to the data part of the second

block (block pointed by second). And next
pointer of the second block points to the third
block. So all three blocks are linked.

head second third

| | |
| | |
+---+---+ +---+---+ +----+----+
| 1 | o----->| 2 | o-----> | # | # |
+---+---+ +---+---+ +----+----+ */

third->data = 3; // assign data to third node

third->next = NULL;

/* data has been assigned to data part of third

block (block pointed by third). And next pointer
of the third block is made NULL to indicate
that the linked list is terminated here.

We have the linked list ready.

head
|
|
+---+---+ +---+---+ +----+------+
| 1 | o----->| 2 | o-----> | 3 | NULL |
+---+---+ +---+---+ +----+------+
 Note that only head is sufficient to represent
the whole list. We can traverse the complete
list by following next pointers. */

return 0;
}

Linked List Traversal

Traversing a linked list means accessing the nodes of the list in order to perform some processing on them.

In the previous program, we have created a simple linked list with three nodes. Let us traverse the created list
and print the data of each node. For traversal, let us write a general-purpose function printList() that prints any
given list.

// A simple C program for traversal of a linked list

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

// This function prints contents of linked list starting from

// the given node
void printList(struct Node* n)
{
while (n != NULL) {
printf(" %d ", n->data);
n = n->next;
}
}

int main()
{
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;

// allocate 3 nodes in the heap

head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));

head->data = 1; // assign data in first node

head->next = second; // Link first node with second

second->data = 2; // assign data to second node

second->next = third;

third->data = 3; // assign data to third node

third->next = NULL;

printList(head);

return 0;
}

Output: 1 2 3

Advantages of Linked Lists

 They are a dynamic in nature which allocates the memory when required.
 Insertion and deletion operations can be easily implemented.
  Stacks and queues can be easily executed.
 Linked List reduces the access time.

Disadvantages of Linked Lists

 The memory is wasted as pointers require extra memory for storage.

 No element can be accessed randomly; it has to access each node sequentially.
 Reverse Traversing is difficult in linked list.

Applications of Linked Lists

 Linked lists are used to implement stacks, queues, graphs, etc.

 Linked lists let you insert elements at the beginning and end of the list.
 In Linked Lists we don't need to know the size in advance.

Basic Operations

Following are the basic operations supported by a list.

Insertion − Adds an element at the beginning of the list.

Deletion − Deletes an element at the beginning of the list.
Display − Displays the complete list.
Search − Searches an element using the given key.
Delete − Deletes an element using the given key.

What is a Node?

A Node in a linked list holds the data value and the pointer which points to the location of the next node in the
linked list.

In the picture above we have a linked list, containing 4 nodes, each node has some data (A, B, C and D) and a
pointer which stores the location of the next node.

You must be wondering why we need to store the location of the next node. Well, because the memory
locations allocated to these nodes are not contiguous hence each node should know where the next node is
stored.

As the node is a combination of multiple information, hence we will be defining a class for Node which will have
a variable to store data and another variable to store the pointer. In C language, we create a structure using
the struct keyword.

class Node
{
public:
// our linked list will only hold int data
int data;
//pointer to the next node
node* next;
 // default constructor
Node()
{
data = 0;
next = NULL;
}

// parameterised constructor
Node(int x)
{
data = x;
next = NULL;
}
}

We can also make the Node class properties data and next as private, in that case we will need to add the
getter and setter methods to access them(don't know what getter and setter methods are: Inline Functions in
C++ ). You can add the getter and setter functions to the Node class like this:

class Node
{
// our linked list will only hold int data
int data;
//pointer to the next node
node* next;

// default constructor same as above

// parameterised constructor same as above

/* getters and setters */

// get the value of data
int getData()
{
return data;
}

// to set the value for data

void setData(int x)
{
[Link] = x;
}
// get the value of next pointer
node* getNext()
{
return next;
}
// to set the value for pointer
void setNext(node *n)
{
[Link] = n;
}
}

The Node class basically creates a node for the data to be included into the Linked List. Once the object for the
class Node is created, we use various functions to fit in that node into the Linked List.

Types of Linked Lists

There are 3 different implementations of Linked List available, they are:

Singly Linked List

Singly linked list is a basic linked list type. Singly linked list is a collection of nodes linked together in a
sequential way where each node of singly linked list contains a data field and an address field which contains
the reference of the next node. Singly linked list can contain multiple data fields but should contain at least
single address field pointing to its connected next node.
To perform any operation on a linked list we must keep track/reference of the first node which may be referred
by head pointer variable. In singly linked list address field of last node must contain a NULL value specifying end
of the list.

One way chain or singly linked list can be traversed only in one direction. In other words, we can say that each
node contains only next pointer, therefore we cannot traverse the list in the reverse direction.

Consider an example where the marks obtained by the student in three subjects are stored in a linked list as
shown in the figure.

In the above figure, the arrow represents the links. The data part of every node contains the marks obtained by
the student in the different subject. The last node in the list is identified by the null pointer which is present in
the address part of the last node. We can have as many elements we require, in the data part of the list.

Node is represented as:

struct node {
int data;
struct node *next;
}

A three-member singly linked list can be created as:

/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */

one->data = 1;
two->data = 2;
three->data = 3;

/* Connect nodes */
one->next = two;
two->next = three;
three->next = NULL;

/* Save address of first node in head */

head = one;

Structure of a node of singly linked list

We can define a node as follows

struct Node
{
 int info;
struct Node *next;
};
typedef struct Node NodeType;
NodeType *first; //first is a pointer type structure variable that points to first node
NodeType *last; //last is a pointer type structure variable that points to last node.

 An algorithm to insert a node at the beginning of the singly linked list.

Let ‘first’ and ‘last’ are the pointer to first and last nodes in the current list respectively.

1. Start
2. Create a new node using malloc function as,
Newnode = (Nodetype*) malloc (sizeof(NodeType));
3. Read the data item to be inserted as ‘el’.
4. Assign data to the info field of new node
[Link] = el;
5. Set next of new node to first
[Link] = first;
6. Set the first pointer to new node
first = Newnode;
7. End

 An algorithm to insert a node at the end of singly linked list.

Let ‘first’ and ‘last’ are the pointer to the first and last nodes in the current list respectively.

1. Start
2. Create a new node using malloc function as;
Newnode = (NodeType*) malloc (sizeof(NodeType));
3. Read the data item to be inserted as ‘el’;
4. Assign data to the info field of new node
Newnode->info = el;
5. Set next of new node to null;
Newnode->next = null;
6. If (first == NULL) then,
Set, first = last = Newnode and exit;
7. else
Set, last->next = Newnode
last = Newnode

8. End

 An algorithm to insert a node at the specified position in a singly linked list.

Let ‘first’ and ‘last’ be the pointer to the first and last nodes in the current list respectively.

1. Start
2. Create a node using malloc function as;
Newnode = (NodeType*) malloc (sizeof(NodeType));
3. Assign data to the info field of new node
Newnode->info = el;
4. Enter the position of a node of which you want to insert a new node. Let it be pos.
5. Set, temp = first;
6. If (first == NULL) then,
Print “void insertion” and exit;
7. for (i=1; i<pos-1; i++)
temp = temp->next;
8. Set, Newnode->next = temp->next;
9. Set, temp->next = Newnode
10. End

 An algorithm to insert a node after the given node in singly linked list

Let ‘first’ and ‘last’ be the pointer to first node and last node in the current linked list respectively and *p be
the pointer to the node after which we want to insert a new node.
 1. Start
2. Create a new node using malloc function
Newnode = (NodeType*) malloc (sizeof(NodeType));
3. Read data item to be inserted say ‘item’
4. Assign data to the info field of new node as,
Newnode->info = item;
5. Set next of new node to next of p as,
Newnode->next = p->next;
6. Set next of p to Newnode
p->next = Newnode
7. End

 An algorithm to delete the first node from the singly linked list.

Let ‘first’ and ‘last’ are the pointer to the first and last nodes in the current list respectively.

1. Start
2. If (first == NULL)
Print “void deletion” and exit
3. Else if(first == last)
Print deleted item as, [Link];
first = last = null
4. Store the address of first node in a temporary variable temp.
Set, temp = first;
5. Set first to next of first.
Set, first = first->next;
6. Free the memory reserved by temp variable.
free(temp);
7. End

 An algorithm to delete the last node from the singly linked list.

Let ‘first’ and ‘last’ are the pointer to first node and last node in the current list respectively.

1. Start
2. If (first == NULL) then, //if list is empty
Print “void Selection” and exit
3. Else if (first == last) then // if list has only one node
Print deleted item as, [Link];
Set, first = last = null;
4. Else
Set temp = first;
while(temp->next != last)
Set temp = temp->next;
Set, temp->next = null;
Set, last = temp;
5. End

 An algorithm to delete a node at the specified position in a singly linked list.

Let ‘first’ and ‘last’ are the pointer to first node and last node in the current respectively.

1. Start
2. Read position of a node which to be deleted let it be ‘pos’.
3. If first == NULL then,
Print “void deletion and exit.
Otherwise,
4. Enter the position of a node at which you want to delete a new node. Let this position be ‘pos’.
5. Set, temp = first
6. for(i=1; i<pos-1; i++)
Set, temp = temp->next;
7. Print deleted item is [Link];
8. Set, loc = temp->next;
9. Set, temp->next = loc->next;
10. End

 An algorithm to delete a node after the given node in singly linked list
 Let ‘first’ and ‘last’ be the pointer to first node and last node in the current list and *p be the pointer to the
node after which we want to delete a new node.

1. If(p == NULL or p->next == NULL) then

Print “deletion not possible and exit”
2. Set loc = p->next;
3. Set p->next = loc->next;
4. Free(loc)
5. End

 Algorithm to print the number of nodes in a linked list

 Searching an item in a linked list;

To search an item from a given linked list we need to find the node that contain this data item. If we find
such a node then searching is successful otherwise searching is unsuccessful. Let *first be the pointer to first
node in the current list.

void searchItem(int key)

{
NodeType * temp;
if(first == NULL)
{
printf("Empty linked list");
exit(0);
}
else
{
temp = first;
while(tmep != NULL)
{
if(temp->info == key)
{
printf("Search successful");
break;
}
temp = temp->next;
}
if(temp == NULL)
{
printf("Unsuccessful search");
}
}
}

Singly Linked List Complete Program

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;

void beginsert ();

void lastinsert ();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\[Link] in beginning\n
[Link] at last\n
[Link] at any random location\n
[Link] from Beginning\n
[Link] from last\n
[Link] node after specified location\n
[Link] for an element\n
[Link]\n
[Link]\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
break;
case 2:
lastinsert();
break;
case 3:
randominsert();
break;
case 4:
begin_delete();
break;
case 5:
last_delete();
break;
case 6:
random_delete();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void beginsert()
{
struct node *ptr;
int item;
 ptr = (struct node *) malloc(sizeof(struct node *));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value\n");
scanf("%d",&item);
ptr->data = item;
ptr->next = head;
head = ptr;
printf("\nNode inserted");
}

}
void lastinsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
ptr -> next = NULL;
head = ptr;
printf("\nNode inserted");
}
else
{
temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
printf("\nNode inserted");

}
}
}
void randominsert()
{
int i,loc,item;
struct node *ptr, *temp;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter element value");
scanf("%d",&item);
ptr->data = item;
printf("\nEnter the location after which you want to insert ");
scanf("\n%d",&loc);
temp=head;
 for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\ncan't insert\n");
return;
}
}
ptr ->next = temp ->next;
temp ->next = ptr;
printf("\nNode inserted");
}
}
void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nList is empty\n");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\nNode deleted from the begining ...\n");
}
}
void last_delete()
{
struct node *ptr,*ptr1;
if(head == NULL)
{
printf("\nlist is empty");
}
else if(head -> next == NULL)
{
head = NULL;
free(head);
printf("\nOnly node of the list deleted ...\n");
}
else
{
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\nDeleted Node from the last ...\n");
}
}
void random_delete()
{
struct node *ptr,*ptr1;
int loc,i;
printf("\n Enter the location of the node after which you want to perform deletion \n");
scanf("%d",&loc);
ptr=head;
for(i=0;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;
 if(ptr == NULL)
{
printf("\nCan't delete");
return;
}
}
ptr1 ->next = ptr ->next;
free(ptr);
printf("\nDeleted node %d ",loc+1);
}
void search()
{
struct node *ptr;
int item,i=0,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("item found at location %d ",i+1);
flag=0;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("Item not found\n");
}
}
}

void display()
{
struct node *ptr;
ptr = head;
if(ptr == NULL)
{
printf("Nothing to print");
}
else
{
printf("\nprinting values . . . . .\n");
while (ptr!=NULL)
{
printf("\n%d",ptr->data);
ptr = ptr -> next;
}
}
}

Advantages of Singly linked list

There are several points about singly linked list that makes it an important data structure.
  Singly linked list is probably the easiest data structure to implement.
 Insertion and deletion of element can be done easily.
 Insertion and deletion of elements doesn't require movement of all elements when compared to an
array.
 Requires less memory when compared to doubly, circular or doubly circular linked list.
 Can allocate or deallocate memory easily when required during its execution.
 It is one of most efficient data structure to implement when traversing in one direction is required.

Disadvantages of Singly linked list

 It uses more memory when compared to an array.

 Since elements are not stored sequentially hence requires more time to access each elements of list.
 Traversing in reverse is not possible in case of Singly linked list when compared to Doubly linked list.
 Requires O(n) time on appending a new node to end which is relatively very high when compared to
array or other linked list.

Doubly Linked List

Doubly linked list is a collection of nodes linked together in a sequential way. Each node of the list contains two
parts (as in singly linked list) data part and the reference or address part. The basic structure of node is
shown in the below image:

Doubly linked list is almost similar to singly linked list except it

contains two address or reference fields, where one of the address
field contains reference of the next node and other contains
reference of the previous node. First and last node of a linked list
contains a terminator generally a NULL value that determines the
start and end of the list. Doubly linked list is sometimes also referred
as bi-directional linked list since it allows traversal of nodes in
both direction.

Since doubly linked list allows the traversal of nodes in both directions hence we can keep track of both first and

last nodes.

A doubly linked list containing three nodes having numbers from 1 to 3 in their data part, is shown in the
following image.

A node is represented as

struct node {
int data;
struct node *next;
struct node *prev;
}

A three-member doubly linked list can be created as

/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */

one->data = 1;
two->data = 2;
three->data = 3;

/* Connect nodes */
one->next = two;
one->prev = NULL;

two->next = three;
two->prev = one;

three->next = NULL;
three->prev = two;

/* Save address of first node in head */

head = one;

Representation of doubly linked list

struct node
{
int info;
struct node *prev;
struct node *next;
};
typedef struct node NodeType;
NodeType *first = NULL;
NodeType *last = NULL;

 An algorithm to insert a node at the beginning of a doubly linked list

1. Start
2. Create a new node by using malloc function as,
Newnode = (NodeType*) malloc (sizeof(NodeType))
3. Read data item to be inserted say it be ‘el’
4. Set Newnode->info = el;
5. Set Newnode->prev = Newnode->next = null
6. If first == null then
Set, first = last = Newnode
Otherwise,
7. Set Newnode->next = first
8. Set first->prev = Newnode
9. Set first = Newnode
10. Stop

 An algorithm to insert a node at the end of a doubly linked list

1. Start
2. Create a new node by using malloc function as,
Newnode = (Nodetype*) malloc (sizeof(NodeType))
3. Read data item to be inserted say it be ‘el’
4. Set Newnode->info = el;
5. Set Newnode->next = NULL
6. If first == NULL, then
Set, first = last = Newnode
Otherwise,
7. Set last->next = Newnode
8. Set Newnode->prev = last;
9. Set last = Newnode
10. Stop

 An algorithm to insert an element at the specified position of a doubly linked list.

 Let ‘first’ and ‘last’ are the pointer to the first and last nodes in the current DLL.

1. Start
2. Create a new node by using malloc function as,
Newnode = (NodeType*) malloc (sizeof(NodeType));
3. Read the data item to be inserted as el
4. Assign data to the info field of new node
Newnode->info = el;
5. Enter the position of the node at which you want to insert a new node. Let it be ‘pos’
6. Set, temp -> first
7. If(first == NULL) then,
Print ‘void insertion’ and exit
8. for(i=1; i<pos-1; i++)
temp = temp->next
if(temp == NULL)
Print “less than desired no. of elements” and exit
end of if
end of loop
9. Set,
Newnode->next = temp->next
Newnode->prev = temp
temp->next = Newnode
temp = Newnode->next
temp->prev = Newnode
10. Exit

 An algorithm to delete a node from beginning of a doubly linked list.

1. Start
2. If first == NULL then
Print “empty list” and exit
3. Else
Set, temp = first
Set, first = first->next
Set, first->prev = null
free(temp)
4. Stop

 An algorithm to delete a node from end of a doubly linked list

1. Start
2. If first == NULL then
Print “empty list” and exit
3. Else if(first == last) then
Set, first = last = NULL
4. Else
Set, temp = first;
while(temp->next != last)
temp = temp->next
end while
Set temp->next = null
Set, last = temp
5. Stop

 An algorithm to delete a node from specified position of a doubly linked list

1. Start
2. If first == NULL then,
Print ‘void deletion’ and exit
Otherwise,
3. Enter the position of a node to be deleted, let it be ‘pos’
4. Set temp = first
5. for(i=1; i<pos-1; i++)
Set, temp = temp->next
end of loop
6. Set,
ptr = temp->next
 Set, temp->next = ptr->next
Set ptr->next->prev = temp
free(ptr)
7. Exit

Doubly Linked List Complete Program

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct Node
{
int info;
struct Node *prev;
struct Node *next;
};
typedef struct Node NodeType;
NodeType *first = NULL;
NodeType *last = NULL;

void insertbeg(int el)

{
NodeType *Newnode;
Newnode = (NodeType*)malloc(sizeof(NodeType));
Newnode->info = el;
Newnode->prev = Newnode->next = NULL;
if(first == NULL)
{
first = Newnode;
last = Newnode;
}
else
{
Newnode->next = first;
first->prev = Newnode;
first = Newnode;
}
}

void insertEnd(int el)

{
NodeType *Newnode;
Newnode = (NodeType*) malloc (sizeof(NodeType));
Newnode->info = el;
Newnode->prev = Newnode->next = NULL;
if(first == NULL)
{
first = Newnode;
last = Newnode;
}
else
{
last->next = Newnode;
Newnode->prev = last;
last = Newnode;
}
}

void DeleteFirst()
{
NodeType *temp;
temp = first;
if(first == NULL)
{
printf("Empty linked list");
}
else if(first == last)
 {
first = NULL;
last = NULL;
free(temp);
}
else
{
first = first->next;
free(temp);
}
}

void DeleteLast()
{
NodeType *temp, *hold;
temp = first;
if(last == NULL)
{
printf("Empty linked list");
}
else if(first == last)
{
first = NULL;
last = NULL;
free(temp);
}
else
{
temp = first;
while(temp->next != last)
{
temp = temp->next;
}
hold = temp->next;
temp->next = NULL;
last = temp;
free(hold);
}
}
void Display()
{
NodeType *temp;
temp = first;
if(first == NULL)
{
printf("Empty linked list");
}
else
{
while(temp != last)
{
printf(temp->info);
temp = temp->next;
}
printf(last->info);
}
}

void main()
{
int choice;
int item;
printf("1. Insert at beginning \n");
printf("2. Insert at last \n");
printf("3. Delete first node \n");
printf("4. Delete last node \n");
printf("5. Display \n");
 do
{
printf("Enter your choice \n");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter data item to be inserted: ");
scanf("%d", &item);
insertbeg(item);
break;

case 2:
printf("Enter data item to be inserted: ");
scanf("%d", &item);
insertEnd(item);
break;

case 3:
DeleteFirst();
break;

case 4:
DeleteLast();
break;

case 5:
Display();
break;

default:
printf("Invalid choice. Please enter correct choice");

}
}while(choice < 6);
}

Advantages of Doubly linked list

Doubly linked list is one of the important data structures. Here are various advantages of doubly linked list.

 As like singly linked list it is the easiest data structures to implement.

 Allows traversal of nodes in both direction which is not possible in singly linked list.
 Deletion of nodes is easy when compared to singly linked list, as in singly linked list deletion requires a
pointer to the node and previous node to be deleted which is not in case of doubly linked list we only
need the pointer which is to be deleted.
 Reversing the list is simple and straightforward.
 Can allocate or de-allocate memory easily when required during its execution.
 It is one of most efficient data structure to implement when traversing in both directions is required.

Disadvantages of Doubly linked list

Not many but doubly linked list has few disadvantages also which can be listed below:

 It uses extra memory when compared to array and singly linked list.
 Since elements in memory are stored randomly, hence elements are accessed sequentially no direct
access is allowed.

Applications/Uses of doubly linked list in real life

There are various application of doubly linked list in the real world. Some of them can be listed as:

 Doubly linked list can be used in navigation systems where both front and back navigation is required.
 It is used by browsers to implement backward and forward navigation of visited web pages
i.e. back and forward button.
 It is also used by various applications to implement Undo and Redo functionality.
 It can also be used to represent deck of cards in games.
  It is also used to represent various states of a game.

Circular Linked List

A circular linked list is a list where the link field of last node points to the very first node of the list.

A circular linked list is basically a linear linked list that may be singly or doubly. The only difference is that there
is no any NULL value terminating the list. In fact in the list every node points to the next node and last node
points to the first node, thus forming a circle. Since it forms a circle with no end to stop hence it is called as
circular linked list.

In circular linked list there can be no starting or ending node, whole node can be traversed from any node. In
order to traverse the circular linked list only once we need to traverse entire list until the starting node is not
traversed again.
A circular linked list can be implemented using both singly linked list and doubly linked list. Here is the logical
structure of a circular linked list.

A circular linked list is a variation of linked list in which the last element is linked to the first element. This forms
a circular loop.

A circular linked list can be either singly linked or doubly linked.

 for singly linked list, next pointer of last item points to the first item
 In doubly linked list, prev pointer of first item points to last item as well.

A three-member circular singly linked list can be created as:

/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */

one->data = 1;
two->data = 2;
three->data = 3;

/* Connect nodes */
one->next = two;
two->next = three;
three->next = one;

/* Save address of first node in head */

head = one;

Basic structure of Circular linked list

Representation of circular linked list

We declare the structure for the circular linked list in the same way as declared it for the singly linked list.

struct Node
{
int info;
struct Node *next;
};
typedef struct Node NodeType;
NodeType *first;
NodeType *last;

 An algorithm to insert a node at the beginning of a circular linked list

11. Create a new node by using malloc function as,

Newnode = (NodeType*) malloc (sizeof(NodeType));
12. Read data item to be inserted say it be ‘el’
13. Set Newnode->info = el
14. If first == NULL then
set, Newnode->next = Newnode
set first = Newnode
set last = Newnode
15. else
set Newnode->next = first
set first = Newnode
set last->next = Newnode
16. End

 An algorithm to insert a node at the end of a circular linked list

1. Create a new node by using malloc function as,

Newnode = (NodeType*) malloc (sizeof(NodeType));
2. Read data item to be inserted say it be ‘el’
3. Set Newnode->info = el
4. If first == NULL then
set Newnode->next = Newnode
set first = Newnode
set last = Newnode
5. else
set last->next = Newnode
set last = Newnode
set last->next = first
6. End

 Algorithm to delete a node from the beginning of a circular linked list

1. Start
2. If first == NULL then
Print “empty list” and exit
3. else
Print the deleted element = first->info
set temp = first
set first = first->next
set last->next = first;
free(temp)
4. End

 Algorithm to delete a node from the end of a circular linked list

1. Start
 2. If start == NULL then
Print “empty list” and exit
3. else if first == last
Print deleted element = first->info
Set, first = last = NULL
4. else
set, temp = start
while (temp->next != last)
set temp = temp->next
end while
Print the deleted element = last->info
set last = temp
set last ->next = first
5. End

Circular Linked List Complete Program

#include<stdio.h>
#include<conio.h>

struct Node
{
int info;
struct Node *next;
};
typedef struct Node NodeType;
NodeType *first;
NodeType *last;
first = null;
last = null;

void insertbeg(int item)

{
Newnode = (NodeType*) malloc(sizeof(NodeType));
Newnode->info = item;
if(first == null)
{
Newnode->next = Newnode;
first = Newnode;
last = Newnode;
}
else
{
Newnode->next = first;
first = Newnode;
last->next = Newnode;
}
}
void insertEnd(int item)
{
Newnode = (NodeType*) malloc(sizeof(NodeType));
Newnode->info = item;
if(first == null)
{
first = Newnode;
last = Newnode;
Newnode->next = Newnode;
}
else
{
last->next = Newnode;
last = Newnode;
Newnode->next = first;
}
}
void DeleteFirst()
{
 NodeType *temp;
temp = first;
if(first == null)
{
printf("Empty linked list");
}
else if(first == last)
{
first = null;
last = null;
free(temp);
}
else
{
first = first->next;
last->next = first;
free(temp);
}
}
void DeleteLast()
{
NodeType *temp;
temp = last;
if(last == null)
{
printf("Empty linked list");
}
else if(first == last)
{
first = null;
last = null;
free(temp);
}
else
{
while(temp->next != last)
{
temp = temp->next;
}
temp->next = first;
last = temp;
temp = first;
free(temp);
}
}
void Display()
{
NodeType *temp;
if(first == null)
{
printf("Empty linked list");
}
else
{
temp = first;
while(temp != last)
{
printf(temp->info);
temp = temp->next;
}
printf(last->info);
}
}

int main()
{
int choice;
 int item;
printf("1. Insert at beginning \n");
printf("2. Insert at last \n");
printf("3. Delete first node \n");
printf("4. Delete last node \n");
printf("5. Display \n");
do{
printf("Enter your choice: \n");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter data item to be inserted: ");
scanf("%d", &item);
insertbeg(item);
break;

case 2:
printf("Enter data item to be inserted: ");
scanf("%d", &item);
insertEnd(item);
break;

case 3:
DeleteFirst();
break;

case 4:
DeleteLast();
break;

case 5:
Display();
break;
default:
printf("Invalid choice. Please enter correct choice");
}
}while(choice < 6);
}

Advantages of a Circular linked list

 Entire list can be traversed from any node.

 Circular lists are the required data structure when we want a list to be accessed in a circle or loop.
 Despite of being singly circular linked list we can easily traverse to its previous node, which is not
possible in singly linked list.

Disadvantages of Circular linked list

 Circular list are complex as compared to singly linked lists.

 Reversing of circular list is a complex as compared to singly or doubly lists.
 If not traversed carefully, then we could end up in an infinite loop.
 Like singly and doubly lists circular linked lists also doesn’t supports direct accessing of elements.

Applications/Uses of Circular linked list in real life

 Circular lists are used in applications where the entire list is accessed one-by-one in a loop. Example:
Operating systems may use it to switch between various running applications in a circular loop.
 It is also used by Operating system to share time for different users, generally uses Round-Robin time
sharing mechanism.
 Multiplayer games uses circular list to swap between players in a loop.

Circular Doubly Linked List

Circular doubly linked list is a more complexed type of data structure in which a node contain pointers to its
previous node as well as the next node. Circular doubly linked list doesn't contain NULL in any of the node. The
last node of the list contains the address of the first node of the list. The first node of the list also contain
address of the last node in its previous pointer.

A circular doubly linked list is shown in the following figure.

Due to the fact that a circular doubly linked list contains three parts in its structure therefore, it demands more
space per node and more expensive basic operations. However, a circular doubly linked list provides easy
manipulation of the pointers and the searching becomes twice as efficient.

Representation of circular doubly linked list

struct node
{
int info;
struct node *prev;
struct node *next;
};
typedef struct node NodeType;
NodeType *first = NULL;
NodeType *last = NULL;

 An algorithm to insert a node at the beginning of a circular doubly linked list

1. Start
2. Create a new node by using malloc function as,
Newnode = (NodeType*) malloc (sizeof(NodeType));
3. Read data item to be inserted say it be ‘el’
4. Set Newnode->info = el
5. If first == null then
Set, first = last = Newnode
Set, Newnode->next = Newnode
Set, Newnode->prev = Newnode
Otherwise,
6. Set Newnode->next = first
7. Set, first->prev = Newnode
8. Set first = Newnode
9. Set last->next = first
10. Set first->prev = last
11. Stop

 An algorithm to insert a node at the end of a circular doubly linked list

1. Start
2. Create a new node by using malloc function as,
Newnode = (NodeType*) malloc (sizeof(NodeType));
3. Read data item to be inserted say it be ‘el’
4. Set Newnode->info = el
5. If first == null then
Set, first = last = Newnode
Set, Newnode->next = Newnode
Set, Newnode->prev = Newnode
Otherwise,
6. Newnode->next = first
7. Set, first->prev = Newnode
8. Set last->next = Newnode
9. Set Newnode->prev = last
10. Set last = Newnode
 11. Stop

 An algorithm to delete a node from the beginning of a circular doubly linked list

1. Start
2. If first == null then
Print “Empty linked list” and exit
3. Else if first == last then
Set, temp = first
Set, first = last = null
4. Otherwise,
Set, temp = first
Set, first = first->next
Set, first->prev = last
Set, last->next = first
5. Free(temp)
6. Stop

 An algorithm to delete a node from the end of a circular doubly linked list

1. Start
2. If first == null then
Print “Empty linked list” and exit
3. Else if first == last then
Set, temp = first
Set, first = last = null
4. Otherwise,
Set, temp = first
while(temp->next != last)
Set, temp = temp->next
end while
Set, last = temp
Set, last->next = first
Set, first->prev = last
5. Free(temp)
6. Stop

Circular Doubly Linked List Complete Program

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct Node
{
int info;
struct Node *prev;
struct Node *next;
};
typedef struct Node NodeType;
NodeType *first = NULL;
NodeType *last = NULL;

void insertbeg(int el)

{
NodeType *Newnode;
Newnode = (NodeType*)malloc(sizeof(NodeType));
Newnode->info = el;
if(first == NULL)
{
first = Newnode;
last = Newnode;
Newnode->next = Newnode;
Newnode->prev = Newnode;
}
else
{
Newnode->next = first;
 first->prev = Newnode;
first = Newnode;
last->next = first;
first->prev = last;
}
}

void insertEnd(int el)

{
NodeType *Newnode;
Newnode = (NodeType*) malloc (sizeof(NodeType));
Newnode->info = el;
if(first == NULL)
{
first = Newnode;
last = Newnode;
Newnode->next = Newnode;
Newnode->prev = Newnode;
}
else
{
last->next = Newnode;
Newnode->prev = last;
last = Newnode;
last->next = first;
first->prev = last;
}
}

void DeleteFirst()
{
NodeType *temp;
temp = first;
if(first == NULL)
{
printf("Empty linked list");
}
else if(first == last)
{
first = NULL;
last = NULL;
free(temp);
}
else
{
first = first->next;
last->next = first;
first->prev = last;
free(temp);
}
}

void DeleteLast()
{
NodeType *temp;
temp = first;
if(last == NULL)
{
printf("Empty linked list");
}
else if(first == last)
{
first = NULL;
last = NULL;
free(temp);
}
else
 {
while(temp->next != last)
{
temp = temp->next;
}
last = temp;
last->next = first;
first->prev = last;
free(temp->next);
}
}
void Display()
{
NodeType *temp;
temp = first;
if(first == NULL)
{
printf("Empty linked list");
}
else
{
while(temp != last)
{
printf(temp->info);
temp = temp->next;
}
printf("%d", last->info);
}
}

void main()
{
int choice;
int item;
printf("1. Insert at beginning \n");
printf("2. Insert at last \n");
printf("3. Delete first node \n");
printf("4. Delete last node \n");
printf("5. Display \n");
do
{
printf("Enter your choice \n");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter data item to be inserted: ");
scanf("%d", &item);
insertbeg(item);
break;

case 2:
printf("Enter data item to be inserted: ");
scanf("%d", &item);
insertEnd(item);
break;

case 3:
DeleteFirst();
break;

case 4:
DeleteLast();
break;

case 5:
Display();
 break;

default:
printf("Invalid choice. Please enter correct choice");

}
}while(choice < 6);
}