UNIT–II: Linked Lists

Singly linked lists: Representation in memory,

Operations: Traversing, Searching, insertion, Deletion from linked list;

Linked representation of Stack

Linked representation of Queue

Doubly linked List

Circular Linked Lists: All operations

Linked List
o Linked List is defined as a collection of dynamically allocated nodes that are randomly
stored in the memory.
o A node contains two fields i.e. data , and the pointer which contains the address of the next
node in the memory.
o The last node of the list contains pointer to the null.

Uses of Linked List

o The list is not required to be contiguously present in the memory. The node can reside
anywhere in the memory and linked together to make a list. This achieves optimized
utilization of space.
o list size is limited to the memory size and doesn't need to be declared in advance.
o Empty node cannot be present in the linked list.
o We can store values of primitive types or objects in the singly linked list.

Limitations of Array
Arrays can be used to store linear data of similar types, but arrays have the following
limitations.
1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in
advance
2) Insertion and deletion operations are expensive because of extra shifting operation.

Advantages of linked list over arrays

1) Dynamic size
2) Ease of insertion/deletion

Drawbacks of linked list

1) 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.
2) Extra memory space for a pointer is required with each element of the list.
Memory 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:
1) data
2) Pointer to the next node
In C, we can represent a node using structures.
struct node
{
int data;
struct node* next;
};

Types of Linked List

There are three common types of Linked List.

1. Singly Linked List

2. Doubly Linked List
3. Circular Linked List
1) Singly Linked List
 Singly linked list can be defined as the collection of dynamically allocated nodes.
 A node in the singly linked list consists of two parts: data part and link part.
 Data part of the node stores actual information that is to be represented by the node
 while the link part of the node stores the address of its immediate successor.

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.

Operations on Singly Linked List

There are various operations which can be performed on singly linked list. A list of all such operations is
given below.

Insertion

The insertion into a singly linked list can be performed at different positions. Based on the position of the
new node being inserted, the insertion is categorized into the following categories.
 SN Operation Description

1 Insertion at It involves inserting any element at the front of the list.

beginning

2 Insertion at It involves insertion at the last of the linked list.

end of the
list

3 Insertion It involves insertion after the specified node of the linked list.
after
specified
node

Deletion and Traversing

The Deletion of a node from a singly linked list can be performed at different positions. Based on the
position of the node being deleted, the operation is categorized into the following categories.

SN Operation Description

1 Deletion at It involves deletion of a node from the beginning of the list.

beginning

2 Deletion at It involves deleting the last node of the list

the end of
the list

3 Deletion It involves deleting the node after the specified node in the list.
after
specified
node

4 Traversing In traversing, we simply visit each node of the list at least once in order to
perform some specific operation on it, for example, printing data part of
each node present in the list.

5 Searching In searching, we match each element of the list with the given element. If
the element is found on any of the location then location of that element
is returned otherwise null is returned. .
C program to implement single linked list operations

#include<stdio.h>

#include<stdlib.h>

struct node

int data;

struct node *next;

}*head= NULL;

void main()

int ch;

void add_begin();

void add_pos();

void add_end();

void del_begin();

void del_pos();

void del_end();

void display();

void search();

clrscr();
 do

printf("\n Single Linked List Operations\n");

printf("1. Add at begin \n");

printf("2. Append \n");

printf("3. Add at specific posotion \n");

printf("4. Delete at begin \n");

printf("5. Delete at end \n");

printf("6. Delete at specific position \n");

printf("7. Display\n");

printf("8. Search \n");

printf("9. Exit \n");

printf("Enter your choice : ");

scanf("%d",&ch);

switch(ch)

case 1: add_begin(); break;

case 2: add_end(); break;

case 3:add_pos(); break;

case 4: del_begin(); break;

case 5: del_end(); break;

case 6: del_pos(); break;

case 7:display(); break;

case 8: search(); break;

case 9: exit(0);

default:

printf("Invalid option\n");

} while(ch<=9);

} // end of main

struct node * create_node()

struct node *temp;

int item;

printf("Enter element:");

scanf("%d",&item);

temp = (struct node*) malloc(sizeof(struct node));

temp->data = item;

temp->next=NULL; \
 return temp;

void add_begin()

int item;

struct node *temp;

temp = create_node(); // newly created node

if( head == NULL) // when list is empty

head = temp;

else // when list is not empty

temp->next = head;

head = temp;

void add_end()
{

int item;

struct node *temp,*right;

temp = create_node(); // newly created node

if( head == NULL) // when list is empty

head = temp;

else // when list is not empty

{ right=head; // start from head node

while(right->next!=NULL) // traverse to last node

right=right->next;

right->next = temp; // attach last node with newly created node

void add_pos()

int item,pos,i;
 struct node *temp,*right,*left;

temp = create_node();

printf("Enter the position:");

scanf("%d",&pos);

left=right = head; // traverse from head node

for(i=1; i<pos; i++) // traverse upto required position

left = right;

right = right->next;

left->next= temp;

temp->next=right;

void del_begin()

struct node *temp;

if(head == NULL)

printf("list is empty \n");

else
 {

temp=head;

head=head->next;

free(temp);

void del_end()

struct node *right;

if(head == NULL)

printf("list is empty \n");

else

right=head;

while(right->next->next!=NULL)

right=right->next;

free(right->next);

right->next=NULL;
 }

void del_pos()

struct node *left,*right,*temp;

int pos,i;

if(head == NULL)

printf("list is empty \n");

else

printf("Enter the position:");

scanf("%d",&pos);

left=right = head;

for(i=1; i<pos; i++)

left = right;

right = right->next;

}
 left->next= right->next;;

free(right);

void display()

struct node *right;

right = head;

if(head == NULL)

printf("list is empty \n");

else

printf("Elements of the linked list are: \n");

while(right != NULL)

printf("%d \t",right->data);

right = right->next;

}
}

void search()

int key;

struct node *right;

if(head == NULL)

printf("list is empty \n");

else

printf("Enter Key element");

scanf(“%d”,&key);

right = head; //start from head node

while(right != NULL) // traverse up to last node

if (key == right->data)

printf(“Element found”);

berak;

right = right->next;
 }

if(right==NULL)

printf(“Element not found”);

2) Doubly linked list

Doubly linked list is a type of linked list in which a node contains a pointer to the previous as well as the
next node in the sequence.

Therefore, in a doubly linked list, a node consists of three parts: pointer to the previous node , node data,
pointer to the next node in sequence.

Memory representation of a node

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

Operations
 SN Operation Description

1 Insertion at Adding the node into the linked list at beginning.

beginning

2 Insertion at end Adding the node into the linked list to the end.

3 Insertion after Adding the node into the linked list after the specified node.
specified node

4 Deletion at Removing the node from beginning of the list

beginning

5 Deletion at the end Removing the node from end of the list.

6 Deletion of the Removing the node which is present just after the node containing
node having given the given data.
data

7 Searching Comparing each node data with the item to be searched and
return the location of the item in the list if the item found else
return null.

8 Display Visiting each node of the list to display elements

Advantages of Doubly linked list

 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 direction is
required.

Disadvantages of Doubly linked list

 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
 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. backand forward button.
 It is also used by various application 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.
 A stack, hash table, and binary tree can be implemented using a doubly linked list.

Doubly Linked List Insertion

Insertion before the head

In this case, new node is inserted before the head node.

• Update head node's left pointer to point to the new node and make new node as head.

Insertion at the End

In this case, traverse the list till the end and insert the new node.

• New node right pointer points to NULL and left pointer points to the end of the list
 • Update right of pointer of last node to point to new node

Insertion at the Middle

Traverse the list till the position node and insert the new node.

• New node right pointer points to the next node of the position node where we want to
insert the new node. Also, new node left pointer points to the position node.

• Position node right pointer points to the new node and the next node of position nodes
left pointer points to new node

Doubly Linked List Deletion

Deleting the first node

In this case, first node (current node head) is removed from the list. It can be done in two

steps:
 • Create a temporary node which will point to same node as that of the head.

• Now, move the head node's pointer to the next node and change the head's left pointer
to NULL. Then, dispose the temporary node.

Deleting the last node

This operation is a bit trickier, because the algorithm has to find a node, which is previous to

the tail. This can be done in three steps.

• Traverse the list and while traversing maintain the previous node address also. Ny the
time we reach the end of list, we will have two pointers, one pointing to the NULL
(tail) and other pointing to the node before tail node.

• Update tail node's previous node's next pointer with NULL

• Dispose the tail node

Deleting an Intermediate Node

In this case, node to be removed is always located between two nodes. Head and tail links are
not updated in this case. Such a removal can be done in two steps:
• As similar to previous case, maintain previous node also while traversing the list.
Once we found the node to be deleted, change the previous node's next pointer to the
next node of the node to be deleted.

• Dispose the current node to be deleted.

Implementation of double linked list

// Double linked list program

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

struct node

struct node *prev;

int data;

struct node *next;

} *head = NULL;

void main()

int ch;

void add_begin();

void add_pos();

void add_end();

void del_begin();

void del_pos();

void del_end();

void display();

void search();

clrscr();

do {

printf("\n Double linked list operations\n");

printf("1. add at begin\n");

printf("2. append\n");
 printf("3. add at specific position\n");

printf("4. delete at begin\n");

printf("5. delete at end\n");

printf("6. delete at specific position\n");

printf("7. display\n");

printf("8. search\n");

printf("9. exit\n");

printf("Enter your choice: ");

scanf("%d", &ch);

switch(ch)

case 1: add_begin(); break;

case 2: add_end(); break;

case 3: add_pos(); break;

case 4: del_begin(); break;

case 5: del_end(); break;

case 6: del_pos(); break;

case 7: display(); break;

case 8: search(); break;

case 9: exit(0);

default:

printf("Invalid option\n");

} while(ch <= 8);

} // end of main function

struct node* create_node()

struct node* temp;

int item;

printf("Enter element: ");

scanf("%d", &item);

temp = (struct node*) malloc(sizeof(struct node));

temp->prev = NULL;

temp->data = item;

temp->next = NULL;

return temp;

void add_begin()

int item;

struct node *temp;

temp = create_node();

if (head == NULL)

head = temp;

else

temp->next = head;

head->prev = temp;

head = temp;

}
void add_end()

int item;

struct node *temp, *right;

temp = create_node();

if (head == NULL)

head = temp;

else

right = head;

while (right->next != NULL)

right = right->next;

right->next = temp;

temp->prev = right;

void add_pos()

int item, pos, i;

struct node *temp, *right, *left;

temp = create_node();

printf("Enter the position: ");

scanf("%d", &pos);

left = right = head;

 for (i = 1; i < pos; i++)

left = right;

right = right->next;

left->next = temp;

temp->prev = left;

temp->next = right;

right->prev = temp;

void del_begin()

struct node *temp;

if (head == NULL)

printf("List is empty\n");

else

temp = head;

head = head->next;

free(temp);

head->prev = NULL;

}
void del_end()

struct node *right;

if (head == NULL)

printf("List is empty\n");

else

right = head;

while (right->next->next != NULL)

right = right->next;

free(right->next);

right->next = NULL;

void del_pos()

struct node *left, *right;

int pos, i;

if (head == NULL)

printf("List is empty\n");

else

printf("Enter the position: ");

scanf("%d", &pos);

left = right = head;

 for (i = 1; i < pos; i++)

left = right;

right = right->next;

left ->next=right->next;

right->next->prev = left;

free(right);

void display()

struct node *right, *last;

right = head;

if (head == NULL)

printf("List is empty\n");

else

right = head;

printf("Elements in forward direction\n");

while (right != NULL)

printf("%d\t", right->data);

last = right;

right = right->next;

}
 printf("Elements in reverse direction\n");

while (last != NULL)

printf("%d\t", last->data);

last = last->prev;

void search()

int key, flag = 0;

struct node *right;

right = head;

if (head == NULL)

printf("List is empty\n");

else

printf("Enter key element: ");

scanf("%d", &key);

right = head;

while (right != NULL)

If(key==right->data)

flag=1;

break;

}
 else

right=right->next;

If(flag==1)

Printf(“element found”);

else

Printf(“element not found”);