List

Kashiram Pokharel
Introduction
• A list is a collection of homogeneous set of elements located in
sequential memory block.
• A list can be implemented statically or dynamically using array or
pointer.
Static (array) data structure:
• It is the simplest implementation scheme to keep the element of list in an array and each
element can be accessed using an index.
• In this implementation, size of the list or memory needed for implementation is reserved at
program compile time.
• Once the memory is reserved, it cannot be changed during program execution and hence the
named static.
• static means the size of data type is fixed.
• Memory size allocated to 'data' is fixed.
• Advantage:
• It is easy to implement list using this implementation using others.
• Sequential as well as random access is possible.
• Dis advantage:
• Memory is reserved in program compiled time. Once the size is fixed , it cannot be grow or shrink
• Elements of list are always stored in contiguous memory location .SO we cannot implement the list
even if there are sufficient memory blocks which are not contiguous.
• We cannot access the elements which we add beyond the end of array
• We must guess the expected maximum size of memory in advance
Dynamic data structure:
• There are many situation where the number of items to be stored is not known
before execution. In this case we use dynamic data structure.
• Data Structure is allowed to grow and shrink as the demand for storage arises.
• Programmer should set a maximum size of data to help avoid memory collision.
• Disadvantage- Because the memory allocation is dynamic, it is possible for the
structure to overflow, should it exceeds its allowed limit. For empty -It should
maybe underflow and it is quite harder to program.
• The implementation technique in which the memory for data structure used in
program is allocated during program run time and which overcomes all the
drawback of static implementation is called DMA.
• The size of list can grow or shrink as per requirement.
• Memory is allocated during program run time
• No need to guess the expected maximum size of list in advance
• Operations like insertion or deletion can be conducted in efficient manner i.e no need to
perform the shift operation.
• Elements are stored in random memory locations
Linked list:
• A linked list is a sequence of elements arranged one after another,
with each element connected to the next element by a “link”.
• A common programming practice is to place each element together
with the link to the next element, the resulting component is called a
node.
• A linked list or one way list is a linear collection of data elements,
called nodes, where the linear order is given by means of “pointers”.
Each node is divided into two parts.
• The first part contains the information of the element / node.
• The second part called the link field contains the address of the next node in
the list.
Operations on linked list:
• The basic operations to be performed on the linked list are as follows:
• Creation: This operation is used to create a linked list
• Insertion: This operation is used to insert a new nose in a kinked list in a Specified position. A
new node may be inserted
• At the beginning of the linked list
• At the end of the linked list
• At the specified position in a linked list
• Deletion: The deletion operation is used to delete a node from the linked list. A node may be
deleted from
• The beginning of the linked list
• the end of the linked list
• The specified position in the linked list.
• Traversing: The list traversing is a process of going through all the nodes of the linked list from
on end to the other end. The traversing may be either forward or backward.
• Searching or find: This operation is used to find an element in a linked list. In the desired
element is found then we say operation is successful otherwise unsuccessful.
• Concatenation: It is the process of appending second list to the end of the first list.
Type of linked list:
• The different types of list are as follows:
• Singly Linked List
• Linear singly Linked List
• Circular singly linked List
• Doubly Linked List
• Linear Doubly Linked List
• Circular doubly Linked List
Linear singly linked list:
• Singly Linked List is a sequential storage techniques introduced to
fulfill the drawbacks of stacks and queues.
• Each element in a linked list is called a node. A single node
contains data and a pointer to the next node which helps in
maintaining the structure of the list.
• A singly linked list is a type of linked list that is unidirectional, that is,
it can be traversed in only one direction from head to the last node
(tail).
• The problem with this list is that we cannot access the predecessor of
node from the current node.
Circular singly linked list:

• A circular singly linked list is one which has no end .A singly linked list
can be made a circular linked list by simply inserting the address of
the very first node in the link field of the last node.
Linear doubly linked list
• A doubly linked list is one in which predecessor and successor nodes
are linked together by multiple links which helps in accessing both the
successor node (next node) and predecessor node (previous node)
from any arbitrary node with in the list.
• Therefore doubly linked list consists of three fields: “Info” field that
contains the information stored in the node, and “left” and “right”
fields that contain pointers to the nodes on either side. It helps to
traverse the list in the forward direction and backward direction.
Circular doubly linked list:

• The circular doubly linked list is one which has both the successor
pointer and predecessor pointer in circular manner.
• 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.
Singly linked list:
Creating an empty linked list:
struct Node
{
int info;
struct Node *link; // pointer to node.
};
typedef struct Node NODE;
void EmptyList(NODE *start)
{
start=NULL;
}
Inserting node:
• To insert an element or a node in a linked list, the following three
things to be done:
• Allocating a node
• Assigning a data to info field of the node
• Adjusting a pointer and a new node may be inserted
• At the beginning of the linked list
• At the end of the linked list
• At the specified position in a linked list
An algorithm to insert a node at the beginning of
the singly linked list:
let *start be the pointer to first node in the current list
1. Create a new node using malloc function
Temp =(NODE*)malloc(sizeof(NODE));
2. Assign data to the info field of new node
Temp ->info=newItem;
3. Set next of new node to start
Temp->link=start;
4. Set the head pointer to the new node
start=Temp;
5. End
An algorithm to insert a node at the end of the
singly linked list:
• let *start be the pointer to first node in the current list and Temp be the new
inserting node.
1. Create a new node using malloc function
Temp=( NODE *)malloc (sizeof(NODE));
2. Assign data to the info field of new node
Temp ->info=value;
3. Set link of new node to NULL
Temp ->link=NULL;
if list is empty then set temp as a starting node
if (start ==NULL)then
Set start = Temp and exit.
5. Set Temp1=start;
6 while(temp1->link!=NULL)
Temp1=temp1-> link; //increment temp
7. Set temp1-> link=Temp;
8. End
An algorithm to insert a node at the specified
position in a singly linked list:
let *start be the pointer to first node in the current list
1. Create a new node using malloc function
Temp=(NODE*)malloc(sizeof(NODE));
2. Assign data to the info field of new node
Temp ->info=data;
3. Enter position of a node at which you want to insert a new node. Let this position is
pos.
4. Set temp1=start;
5. Check list underflow
if (start ==NULL)then
printf(“void insertion”); and exit(1).
6. Traverse up to pos-1 position
for(i=1; i<pos-1; i++)
Temp1=Temp1->link;
7. Set Temp->next=temp1->next;
set temp1->next =Temp.
8. End
Delete operation in singly linear linked list:
• A node of linked can be deleted from
• From the beginning
• From the end
• From the specified position.
An algorithm to deleting the first node of the
singly linked list:
let *start be the pointer to first node in the current list
1. If(start==NULL) then
Print list underflow and exit
2. Store the address of first node in a temporary variable temp.
Temp=start;
3. Set start to link of start.
Start=start->link;
4. Free the memory reserved by temp variable.
free(temp);
5. End
An algorithm to deleting the last node of the singly
linked list:
let *start be the pointer to first node in the current linked list
1. Check list underflow condition
If(start==NULL) then //if list is empty
print “Void deletion” and exit

2. else if(start->link==NULL) then //if list has only one node

Set temp=start;
print deleted item as, printf(“%d” ,start->info);
start=NULL;
free(temp);
3. else
set temp=start;
while(temp->link !=NULL)
set loc= temp
set temp=temp->link;
End of while
4. free(temp);
Set loc-> link =NULL;
5. End
An algorithm to delete a node at the specified
position in a singly linked list:
let *start be the pointer to first node in the current list
1. Check list underflow condition
if start ==NULL
` print “list underflow” and exit
2. Enter position of a node at which you want to delete a new node. Let this position
is pos.
3. Set temp= start
declare a pointer of a structure let it be *p
4. for(i=1; i<pos-1; i++)
temp=temp->link;
5. Set p=temp->link;
6. print deleted item is temp->link->info // p->info.
7. Set temp->link=temp->link->link; //temp->link=p->link.
8. free(p);
9. End
Traversing the Linked List:
• In linked list start is a pointer which points to the first element of the list for
processing next element we assign the address of the next element to the
pointer.
• This algorithm traverses LIST, applying an operation PROCESS to each Node /
element of the LIST. start points to the first node of the LIST. Pointer variable
Temp point to the node currently being processed.

1. Set Temp = start. [Initializes pointer Temp.]

2. Repeat Steps 3 and 4 while Temp ≠ NULL.
3. Apply PROCESS to Temp -> INFO.
4. Set Temp = Temp -> Link[Temp now points to the next node.]
[End of Step-2 loop.]
5. End.
Searching:
• for searching the element first traverse the linked list and with traversing
compare the information part of such element with the given element it .

1. Set Temp = start. [Initializes pointer Temp.]

2. Steps 3 and 4 while Temp ≠ NULL.
3. If Temp -> INFO= = searched_item
Return ;
4. Set Temp = Temp -> Link [Temp now points to the next node.]
[End of Step-2 loop.]
5. End.
Linked list implementation of stack
• Instead of using array, we can also use linked list to implement
stack. Linked list allocates the memory dynamically.
• However, time complexity in both the scenario is same for all
the operations i.e. push, pop and peek.
• In linked list implementation of stack, the nodes are
maintained non-contiguously in the memory. Each node
contains a pointer to its immediate successor node in the
stack. Stack is said to be overflow if the space left in the
memory heap is not enough to create a node.
Push():
• Adding a node to the stack is referred to as push operation. Pushing an element to a stack in
linked list implementation is different from that of an array implementation. In order to push
an element onto the stack, the following steps are involved.
let *top be the top of the stack or pointer to the first node of the list.
1. Create a new node
node *temp;
temp=( NodeType *)malloc(sizeof(node));
2. Check for empty stack for insert
if(top==NULL)
{
temp->info=item;
temp->link=NULL;
top=temp;
}
3. otherwise

temp->info=item;
temp->link=top;
top=temp;
4. End
Pop function:
let *top be the top of the stack or pointer to the first node of the list.
1. Check stack underflow condition
NodeType *temp;
if(top==NULL)
{
printf("Stack contain no elements:\n");
return;
}
2. Otherwise set
temp=top;
3. Point top to next node
top=top->link;
4. Print the information of deleted node and free the memory
printf("\ndeleted item is %d\t",temp->info);
free(temp);
Linked list implementation of queue
• The array implementation cannot be used for the large scale applications where the
queues are implemented. One of the alternative of array implementation is linked list
implementation of queue.
• The storage requirement of linked representation of a queue with n elements is o(n)
while the time requirement for operations is o(1).
• In a linked queue, each node of the queue consists of two parts i.e. data part and the link
part. Each element of the queue points to its immediate next element in the memory.
• In the linked queue, there are two pointers maintained in the memory i.e. front pointer
and rear pointer. The front pointer contains the address of the starting element of the
queue while the rear pointer contains the address of the last element of the queue.
• Insertion and deletions are performed at rear and front end respectively. If front and rear
both are NULL, it indicates that the queue is empty.
• The linked representation of queue is shown in the following figure.
 Insert operation:
• let *rear and *front are pointers to the first node of the list initially and insertion of node in linked list done at the rear part and
deletion of node from the linked list done from front part.
1. allocate the memory for the new node temp
temp=( NodeType *)malloc(sizeof(NodeType));
2. insert data to the info part of temp
set tempinfo=data
set temp->link=NULL
3. insert element into an empty queue. The new element will be added as the only element of the queue and the next pointer of
front and rear pointer both, will point to NULL.
if(front == NULL)
{
SET FRONT = REAR = temp
}
Otherwise.
4. if the queue contains more than one element then we need to update the end pointer rear so that the next pointer of rear
will point to the new node temp
SET REAR -> link = Temp
SET REAR = Temp
5. end
Delete Operation
1. check list underflow condition
If (front = = NULL)
Printf(“queue underflow”);
2. assign the front node to temp and print it as deleted node
Temp = front;
Printf(“Deleted element is %d”, tempinfo);
4. set link part of front to front
Front = front link;
4. Free temp
Free (temp);
Circular singly linked list:
• A linked list in which the address field of last node contains the address of
the very first node is called circular linked list.
• It is the linked list in which the address field of last node does not point to
null i.e. to the beginning of the list. If we begin at a given node and travels
the entire list, we end up at the starting point. Since, it has no end, we
must establish the first and last node by convention.

• In a circular singly linked list, the last node of the list contains a pointer to
the first node of the list. We traverse a circular singly linked list until we
reach the same node where we started. The circular singly liked list has no
beginning and no ending. There is no null value present in the next part of
any of the nodes.
Representation of circular linked list:
we declare the structure for the circular linked list in the same way as
declared it for the linear linked list.
struct node
{
int info;
struct node *link;
};
typedef struct node NODE;
NODE *start=NULL:
NODE *last=NULL:
Algorithms to insert a node in a circular linked list:
-Algorithm to insert a node at the beginning of a circular linked list:
1. Create a new node as
temp=(NODE*)malloc(sizeof(NODE));
2. Insert a value into newly allocated memory
set temp->info=item
3. If list is empty i.e start==NULL then
set temp->link=temp
set start=temp
set last =temp
4. Otherwise,
set temp->link=start
set start=temp
set last->link=temp
5. End
Algorithm to insert a node at the end of a circular linked list:
1. Create a new node as
temp=(NodeType*)malloc(sizeof(NodeType));
2. Insert a value into newly allocated memory
set temp->info=item
3. If list is empty then start==NULL then
set temp->link=temp
set start=temp
set last temp
4. else
set last->link=temp
set last=temp
set last->link=start
5. End
Algorithm to insert a node at any intermediate
location

************same as singly linked list*************

Algorithms to delete a node from beginning of
circular linked list:
from the beginning
1. Check list underflow conditions.
if start==NULL then
Print “empty list” and exit
2. else
set temp=start
set start=start->link
print the deleted element=temp->info
set last->link=start;
free(temp)
3. End
Algorithm to delete a node from the end of a
circular linked list:
1. if start==NULL then
“empty list” and exit
2. else if start==last //for only one node
set temp=start
print deleted element=temp->info
free(temp)
start=last=NULL
3. otherwise
set temp=start //for traverse up to second last node.
while( temp->link!=last)
set temp=temp-> link

set temp1=temp-> link

set last=temp
set last-> link =start
print the deleted element=hold->info
free(temp1)
4. End
Algorithm to delete a node from intermediate
position of a circular linked list:

***same as linear linked list***

Doubly linked list
• In single linked list we can traverse only in one direction because each
node has address of next node only. Suppose we are in the middle of
linked list & we want to operation with just previous node, then we
have no way to go in previous node. And we’ll again traverse from
starting node which is time consuming.
• To overcome this problem we use double linked list.
• Doubly linked list is a type of linked list in which each node apart from
storing its data, it has two links. The first link points to the previous
node in the list and the second link points to the next node in the list.
The first node of the list has its previous link pointing to NULL
similarly the last node of the list has its next node pointing to NULL.
 Representation of doubly linked list:
struct node
{
int info;
struct node *prev;
struct node *next;
};

typedef struct node NodeType;

NodeType *start=NULL;

Here, struct node * previous is pointer to structure which will contain the address
of previous node & struct node * next will contain the address of next node in list.
Thus we can travel in both the direction.
Algorithm to insert a node at the beginning of a
doubly linked list:
1. Allocate memory for the new node as,
temp=(NODE*)malloc(sizeof(NODE))
2. Assign value to info field of a new node
set temp->info=item
set temp->prev=null
3. set temp->next=start
4. set start->prev=temp
5. set start=temp
6. End
Algorithm to insert a node at the end of a doubly
linked list:
1. Allocate memory for the new node as,
temp=(NodeType*)malloc(sizeof(NodeType))
2. Assign value to info field of a new node
set temp->info=item
3. set temp->next=NULL
4. if start==NULL //for empty list
set temp->prev=NULL;
set start=temp;
5. if start!=NULL
set temp1=start
while(temp1->next!=NULL)
temp1=temp1->next;
6. set temp1->next=temp;
set temp->prev=temp1
7. End
Algorithm to insert a node at the intermediate
position of a doubly linked list:

***do yourself***
Algorithm to delete a node from beginning of a
doubly linked list:
1. if start==NULL then
print “empty list” and exit
2. else
set temp=start
set start=start->next
set start->prev=NULL;
free(temp)
3. 3. End
Algorithm to delete a node from end of a doubly
linked list:
1. if start==NULL then
print “empty list” and exit
2. else if(start->next==NULL) then
set temp=start
set start=NULL
free(temp)
3. else
set temp1=start;
while(temp1->next->next !=NULL)
temp1=temp1->next

set temp=temp1->next
set temp1->next=NULL
free(temp)
4. End
Algorithm to delete a node from intermediate
position of a doubly linked list:
• Check list underflow condition
1. if start==NULL then
print “empty list” and exit
2. Check for single node
If(startnext==NULL)
Set temp=start
Set start=NULL
Free(temp)
3. Enter position of node you want to delete, Let it will be pos.
Now traverse upto pos
Temp1=start
For(i=1;i<pos;i++)
Temp1=temp1link

4. Set (temp1prev)next=temp1next
5. Set (temp1next)prev=temp1prev
6. Free(temp1)
Circular doubly linked list:
• Circular doubly linked list is one which has the successor and predecessor pointer in
circular manner.
• It is a doubly linked list where the next link of last node points to the first node and
previous link of first node points to last node of the list.
• The main objective of considering circular doubly linked list is to simplify the
insertion and deletion operations performed on doubly linked list.
• Representation
C representation of doubly circular linked list:
struct node
{
int info;
struct node *prev;
struct node *next;
};
typedef struct node NodeType;
NodeType *start=NULL
Algorithm to insert a node at the beginning of a
circular doubly linked list:
Allocate memory for the new node as,
temp=(NodeType*)malloc(sizeof(NodeType))
2. Assign value to info field of a new node
set temp->info=item

3. set temp1=start->next
4. set start->next=temp1
5. set temp->prev=start
6. set temp->next=temp1
7. set temp1->prev=temp
8. End
Algorithm to insert a node at the end of a circular
doubly linked list:
1. Allocate memory for the new node as,
newnode=(NodeType*)malloc(sizeof(NodeType))
2. Assign value to info field of a new node
set newnode->info=item
3. set temp=head->prev
4. set temp->next=newnode
5. set newnode->prev=temp
6. set newnode->next=head
7. set head->prev=newnode
8. End
Algorithm to insert a node at the intermediate
position of doubly linked list:

***same as doubly linked list***

Algorithm to delete a node from the beginning of a
circular doubly linked list:
if head->next==NULL then
print “empty list” and exit
else
set temp=head->next;
set head->next=temp->next
set temp->next=head
free(temp)
End
Algorithm to delete a node from the end of a
circular doubly linked list:
• check list underflow condition
if head->next==NULL then
print “empty list” and exit
• else
set temp=head->prev;
set head->left=temp->left
free(temp)
• End
Algorithm to delete a node from the intermediate
position of circular doubly linked list:

***same as doubly linked list***

****************Thank YOU***************