Contents
Linked List ............................................................................................................................................. 2
Algorithm for creating a linked list .................................................................................................... 3
Algorithm to display (Traversal) linked list....................................................................................... 3
Algorithm for Insertion in Linked List .............................................................................................. 3
Algorithm for Deletion in Linked List ............................................................................................... 4
Algorithm to merge Linked List ........................................................................................................ 5
Circular Linked List ............................................................................................................................... 6
Algorithm for Creating a Circular Linked List: ................................................................................. 6
Algorithm for traversal in Circular Linked List:................................................................................ 6
Algorithm for Insertion in Circular Linked List ................................................................................ 7
Algorithm for Deletion in Circular Linked List ................................................................................. 7
Algorithm for Merge in Circular Linked List .................................................................................... 8
Doubly Linked List ................................................................................................................................ 8
Algorithm for Creating a Doubly Linked List: .................................................................................. 8
Algorithm for Traversal a Doubly Linked List: ................................................................................. 9
Algorithm for Insertion in Doubly Linked List ................................................................................. 9
Algorithm for Deletion in Doubly Linked List ................................................................................ 10
Algorithm to merge Doubly Linked List ......................................................................................... 11
Stack implementation using Linked List ............................................................................................. 11
Algorithm for Push .......................................................................................................................... 12
Algorithm for Pop ............................................................................................................................ 12
Queue implementation using Linked List ............................................................................................ 12
Algorithm for Enqueue .................................................................................................................... 12
Algorithm for Dequeue .................................................................................................................... 13
Adding two polynomials using Linked List ........................................................................................ 13
Pravin Sangroula [IOE Purwanchal Campus][pravin.sangraula@purc.tu.edu.np] Page 1
Linked List
• A linked list data structure includes a series of connected nodes. Here, each node stores the
data and the address of the next node.
• 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.
• A linked list consists of nodes where each node contains a data field and a reference (link) to
the next node in the list.
• We give the address of the first node a special name called Head.
• Also, the last node in the linked list can be identified because its next portion points to null.
• Representation in C
struct node
{
int info;
struct node *next;
};
struct node *ptr,*newptr;
struct node *head;
Let, getnode() be a function that allocates memory for a node, assign data to the node’s info, makes
node’s next pointer null and returns the address of the node.
struct node* getnode()
Sample code for getnode() in C:
{
struct node* np;
np=(struct node*)malloc(sizeof(struct node));
printf(“Enter a data”);
scanf(“%d”,&np->info);
np->next=NULL;
return np;
}
Pravin Sangroula [IOE Purwanchal Campus][pravin.sangraula@purc.tu.edu.np] Page 2
Algorithm for creating a linked list
1. Start
2. newptr=getnode()
3. if(head=NULL)
head=newptr
otherwise,
last->next=newptr
4. last=newptr
5. Repeat from step 2 if user wants to add another node.
6. Stop
Algorithm to display (Traversal) linked list
1. Start
2. ptr=head
3. while(ptr≠NULL)
print “ptr->info”
ptr=ptr->next
4. Stop
Algorithm for Insertion in Linked List
I. Insertion at front
1. Start
2. newptr=getnode()
3. newptr->next=head
4. head=newptr
II. Insertion at last
1. Start
2. newptr=getnode()
3. ptr=head
4. while(ptr->next≠NULL)
ptr=ptr->next
5. ptr->next=newptr
6. Stop
Pravin Sangroula [IOE Purwanchal Campus][pravin.sangraula@purc.tu.edu.np] Page 3
III. Insertion at anywhere
Let key be the data of the node after which we are going to add new item
1. Start
2. newptr=getnode()
3. ptr=head
4. while(ptr->info≠key AND ptr≠NULL)
ptr=ptr->next
5. if(ptr=NULL)
print “Node with key does not exists”
otherwise,
i. newptr->next=ptr->next
ii. ptr->next=newptr
6. Stop
Algorithm for Deletion in Linked List
Let free(ptr) be a function which releases memory occupied by a node pointed by ptr.
I. Deletion at front
1. Start
2. if(head=NULL)
Print “Linked list is empty”
Otherwise,
i. ptr=head
ii. head=head->next
iii. free(ptr)
3. Stop
II. Deletion at last
1. Start
2. if(head=NULL)
Print “Linked list is empty”
Otherwise,
i. ptr=head
ii. while(ptr->next≠NULL)
prevptr=ptr
ptr=ptr->next
Pravin Sangroula [IOE Purwanchal Campus][pravin.sangraula@purc.tu.edu.np] Page 4
iii. prevptr->next=NULL
iv. free(ptr)
3. Stop
III. Deletion at anywhere
Let key be the data of the node which we are going to delete.
1. Start
2. if(head=NULL)
Print “Linked list is empty”
Otherwise,
i. ptr=head
ii. while(ptr->info≠key AND ptr≠NULL)
prevptr=ptr
ptr=ptr->next
iii. if(ptr=NULL)
print “Node with key does not exists”
otherwise,
prevptr->next=ptr->next
free(ptr)
3. Stop
Algorithm to merge Linked List
1. Start
2. ptr=head1
3. while(ptr->next≠NULL)
ptr=ptr->next
4. ptr->next=head2
5. Stop
Pravin Sangroula [IOE Purwanchal Campus][pravin.sangraula@purc.tu.edu.np] Page 5
Circular Linked List
• Circular linked list is a linked list where all nodes are connected to form a circle. There is no
NULL at the end. A circular linked list can be a singly circular linked list or doubly circular
linked list.
Algorithm for Creating a Circular Linked List:
1. Start
2. newptr=getnode()
3. if(nodeptr=NULL)
nodeptr=newptr
otherwise,
last->next=newptr
4. newptr->next=nodeptr
5. last=newptr
6. Repeat from the step 2 if you want to add more node
7. Stop
Algorithm for traversal in Circular Linked List:
1. Start
2. ptr=nodeptr
3. do
print “ptr->info”
ptr=ptr->next
while(ptr≠nodeptr)
4. Stop
Pravin Sangroula [IOE Purwanchal Campus][pravin.sangraula@purc.tu.edu.np] Page 6
Algorithm for Insertion in Circular Linked List
Let key be the data of the node after which we are going to add new item
1. Start
2. newptr=getnode()
3. ptr=nodeptr()
4. do
ptr=ptr->next
while(ptr->info≠key AND ptr≠nodeptr)
5. if(ptr->info≠key)
print “Node with key does not exists”
otherwise,
i. newptr->next=ptr->next
ii. ptr->next=newptr
6. Stop
Algorithm for Deletion in Circular Linked List
Let free(ptr) be a function which releases memory occupied by a node pointed by ptr.
Let key be the data of the node which we are going to delete.
1. Start
2. if(nodeptr=NULL)
print “Linked list is empty”
otherwise,
i. ptr=nodeptr
ii. do
prevptr=ptr
ptr=ptr->next
while(ptr->info≠key AND ptr≠nodeptr)
iii. if(ptr->info≠key)
print “Node with key does not exists”
otherwise,
i. prevptr->next=ptr->next
ii. free(ptr)
3. Stop
Pravin Sangroula [IOE Purwanchal Campus][pravin.sangraula@purc.tu.edu.np] Page 7
Algorithm for Merge in Circular Linked List
1. Start
2. temp=nodeptr2->next
3. nodeptr2->next=nodeptr1->next
4. nodeptr1->next=temp
5. Stop
Doubly Linked List
• A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer,
together with next pointer and data which are there in singly linked list.
• Representation in C
struct node
{
struct node *prev;
int info;
struct node *next;
};
Algorithm for Creating a Doubly Linked List:
1. Start
2. newptr=getnode()
3. if(head=NULL)
head=newptr
otherwise,
last->next=newptr
newptr->prev=last
4. last=newptr
5. Repeat from the step 2 if you want to add more node
6. Stop
Pravin Sangroula [IOE Purwanchal Campus][pravin.sangraula@purc.tu.edu.np] Page 8
Algorithm for Traversal a Doubly Linked List:
1. Start
2. ptr=head
3. while(ptr≠NULL)
print “ptr->info”
ptr=ptr->next
4. Stop
Algorithm for Insertion in Doubly Linked List
I. Insertion at front
1. Start
2. newptr=getnode()
3. newptr->next=head
4. head->prev=newptr
5. head=newptr
II. Insertion at last
1. Start
2. newptr=getnode()
3. ptr=head
4. while(ptr->next≠NULL)
ptr=ptr->next
5. ptr->next=newptr
6. newptr->prev=ptr
7. Stop
III. Insertion at anywhere
Let key be the data of the node after which we are going to add new item
1. Start
2. newptr=getnode()
3. ptr=head
4. while(ptr->info≠key AND ptr≠NULL)
ptr=ptr->next
5. if(ptr=NULL)
print “Node with key does not exists”
Pravin Sangroula [IOE Purwanchal Campus][pravin.sangraula@purc.tu.edu.np] Page 9
otherwise,
i. newptr->next=ptr->next
ii. newptr->prev=ptr
iii. (ptr->next)->prev=newptr
iv. ptr->next=newptr
6. Stop
Algorithm for Deletion in Doubly Linked List
Let free(ptr) be a function which releases memory occupied by a node pointed by ptr.
I. Deletion at front
1. Start
2. if(head=NULL)
Print “Linked list is empty”
Otherwise,
i. ptr=head
ii. head=head->next
iii. free(ptr)
iv. head->prev=NULL
3. Stop
II. Deletion at last
1. Start
2. if(head=NULL)
Print “Linked list is empty”
Otherwise,
i. ptr=head
ii. while(ptr->next≠NULL)
ptr=ptr->next
iii. (ptr->prev)->next=NULL
iv. free(ptr)
3. Stop
Pravin Sangroula [IOE Purwanchal Campus][pravin.sangraula@purc.tu.edu.np] Page 10
III. Deletion at anywhere
Let key be the data of the node which we are going to delete.
1. Start
2. if(head=NULL)
Print “Linked list is empty”
Otherwise,
i. ptr=head
ii. while(ptr->info≠key AND ptr≠NULL)
ptr=ptr->next
iii. if(ptr=NULL)
print “Node with key does not exists”
otherwise,
i. (ptr->prev)->next=ptr->next
ii. (ptr->next)->prev=ptr->prev
iii. free(ptr)
3. Stop
Algorithm to merge Doubly Linked List
1. Start
2. ptr=head1
3. while(ptr->next≠NULL)
ptr=ptr->next
4. ptr->next=head2
5. head2->prev=ptr
6. Stop
Stack implementation using Linked List
• struct node *top;
Pravin Sangroula [IOE Purwanchal Campus][pravin.sangraula@purc.tu.edu.np] Page 11
Algorithm for Push
1. Start
2. newptr=getnode()
3. newptr->next=top
4. top=newptr
5. Stop
Algorithm for Pop
1. Start
2. if(top=NULL)
Print “Stack is Empty”
Otherwise,
i. temp=top
ii. top=top->next
iii. free(temp)
3. Stop
Queue implementation using Linked List
• struct node *front,*rear;
Algorithm for Enqueue
1. Start
2. newptr=getnode()
3. if(rear=NULL)
front=rear=newptr
otherwise,
i. rear->next=newptr
ii. rear=newptr
4. Stop
Pravin Sangroula [IOE Purwanchal Campus][pravin.sangraula@purc.tu.edu.np] Page 12
Algorithm for Dequeue
1. Start
2. if(front=NULL)
Print “Queue is Empty”
Otherwise,
i. temp=front
ii. front=front->next
iii. if(front=NULL)
rear=NULL
iv. free(temp)
3. Stop
Adding two polynomials using Linked List
• Input:
1st number = 5x^2 + 4x^1 + 2x^0
2nd number = 5x^1 + 5x^0
Output:
5x^2 + 9x^1 + 7x^0
Pravin Sangroula [IOE Purwanchal Campus][pravin.sangraula@purc.tu.edu.np] Page 13
Pravin Sangroula [IOE Purwanchal Campus][pravin.sangraula@purc.tu.edu.np] Page 14
