Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Shashank Yadav (KIET-Ghaziabad)

9
...

 Each node is divided into two parts: the first part contains the information of the
element, and the second part, called the link field or next-pointer field, contains the
address of the next node in the list
...
1 Dynamic Implementation of Singly Linked List with 5 nodes

 In figure 1, each node is pictured with two parts
...


Start

5

1
2
3
4
5
6
7
8
9
10

INFO

LINK

A

10

B

2

E

0

F

8

Fig
...


 In figure 2, there is array representation of LIST
...
INFO array stores the elements of LIST and LINK
array stores the position of next element
...
In this figure, start has value 5 i
...
it points the 5th
location of Array INFO of linked list
...
e
...
If LINK[k] stores
0 this means INFO[k] is the last element of the LIST
...

o It is relatively expensive to insert and delete elements in an array
...
(For this reason,
arrays are called dense lists and are said to be static data structures
...
1 Dynamic Memory Allocation of Singly Linked List
...
3 Dynamic Implementation of Singly Linked List

9
...
1 Traversing a Singly Linked List:
 Traversing Linked List means to visit and process each node exactly once
...

1
...

2
...
Process (T Data)
b
...

3
...

9
...
2 Searching an element in the List:
Algorithm:
SEARCH_LIST (LIST, START, ITEM)
Where LIST is a singly linked list, START is a pointer variable which points the first
element of the LIST, and ITEM is an element to be searched
...
T= START
2
...
if (T Data = = ITEM) then
i
...
Return
b
...
If(T = = NULL) then
a
...
Return
9
...
3 Inserting into a Singly Linked List:
 We can insert a node into a linked list by three ways
...

Insert node at First position
...

Insert node at Last position
...

Insert node after a given node
...

1
...
If (N= =NULL) then
a
...
)
b
...
NData= ITEM
4
...
START= N
6
...

1
...
If (N= =NULL) then
a
...
Return
3
...
NNext= NULL
5
...
START= N
b
...
T= START
7
...
T= TNext
8
...
Return
INSERT_AFTER(LIST, START, ITEM, KEY)
Where LIST is a singly linked list, START is pointer variable which stores the
address of first element, ITEM is an element to be inserted, KEY is an element after which
new element ITEM will be inserted
...
Make a new node N
2
...
Write (Memory is not available)
b
...
NData= ITEM
4
...
T= START
6
...
if (TData = = KEY) then
i
...
TNext= N
44 | P a g e

Shashank Yadav (KIET-Ghaziabad)

iii
...
T= TNext
7
...
Write (KEY is not present in the LIST)
8
...
1
...

1
...
START= STARTNext
b
...
P= START
3
...
while (T != NULL) do
a
...
P Next = T Next
ii
...
P= T
c
...
If (T= = NULL)
a
...
Return
9
...
5 C program for implementing Singly Linked List (InsertFirst, InsertLast,
InsertAfter, Deletion, Search, Traverse)
...
h>
#include ...
Insert First \n2
...
Insert After\n");
printf("4
...
Search\n6
...
Exit\n");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\nEnter one number ");
scanf("%d",&item);
InsertFirst(item);
break;
case 2: printf("\nEnter one number ");
scanf("%d",&item);
InsertLast(item);
break;
case 3: printf("\nEnter one number ");
scanf("%d",&item);
printf("\nEnter the element after which you want to insert the
node");
scanf("%d",&key);
InsertAfter(item,key);
break;
case 4: printf("\nEnter number which do you want to delete ");
scanf("%d",&item);
Delete(item);
break;
case 5: printf("\nEnter number which do you want to search ");
scanf("%d",&item);
Search(item);
break;
case 6: Traverse();
}
}while(choice!=7);
}
void InsertFirst(int item)
{
node *n;
n=(node*)malloc(sizeof(node));
n->data=item;
n->next=start;
46 | P a g e

Shashank Yadav (KIET-Ghaziabad)

start=n;
printf("\n%d has been inserted",item);
}
void InsertLast(int item)
{
node *n, *t;
n=(node*)malloc(sizeof(node));
n->data=item;
n->next=NULL;
if(start==NULL)
{
start=n;
printf("\n%d has been inserted",item);
}
else
{
t=start;
while(t->next!=NULL)
{
t=t->next;
}
t->next=n;
printf("\n%d has been inserted",item);
}
}
void InsertAfter(int item, int key)
{
node *n,*t;
n=(node*)malloc(sizeof(node));
n->data=item;
n->next=NULL;
t=start;
while(t!=NULL)
{
if(t->data==key)
{
n->next=t->next;
t->next=n;
printf("\n%d has been inserted",item);
break;
}
t=t->next;
}
if(t==NULL)
47 | P a g e

Shashank Yadav (KIET-Ghaziabad)

printf("\n%d is not present in the list",key);
}
void Delete(int item)
{
node *t, *p;
if(start->data==item)
{
t=start;
start=start->next;
free(t);
printf("%d has been deleted",item);
}
else
{
p=start;
t=start->next;
while(t!=NULL)
{
if(t->data==item)
{
p->next=t->next;
free(t);
printf("%d has been deleted",item);
break;
}
p=t;
t=t->next;
}
if(t==NULL)
printf("\n%d is not present in the list",item);
}
}
void Search(int item)
{
node *t;
t=start;
while(t!=NULL)
{
if(t->data==item)
{
printf("\n%d is present in the list",item);
break;
}
t=t->next;
}
if(t==NULL)
48 | P a g e

Shashank Yadav (KIET-Ghaziabad)

printf("\n%d is not present in the list",item);
}
void Traverse()
{
node *t;
t=start;
if(t==NULL)
{
printf("\nList is Empty");
}
else
{
printf("\nLinked list\n");
while(t!=NULL)
{
printf("%d\t",t->data);
t=t->next;
}
}
}
9
...
6 C functions for counting nodes in the singly linked list, inserting new node before a
given node, Reverse the list
...
1
...

void SortedList(int item)
{
node *n, *t, *p;
n=(node*)malloc(sizeof(node));
n->data=item;
n->next=NULL;
if(start==NULL)
50 | P a g e

Shashank Yadav (KIET-Ghaziabad)

{
start=n;
}
else if(start->data > item)
{
n->next=start;
start=n;
}
else if(start->next==NULL)
{
start->next=n;
}
else
{
p=start;
t=start->next;
while(t!=NULL)
{
if(t->data > item)
{
n->next=t;
p->next=n;
break;
}
p=t;
t=t->next;
}
if(t==NULL)
p->next=n;
}
printf("\n%d has been inserted",item);
}

9
...

START

/

NULL

Address of Previous Node

Data

NULL
Address of Next Node

Fig
...
2
...

Algorithm:
TRAVERSE_LIST (LIST, START)
Where LIST is a doubly linked list, and START is a pointer variable which points the
first element of the LIST
...
T= START
//T is a temporary pointer variable, which points the first
element of the list
...
while(T!= NULL) do
a
...
T= Tnext
//now T points the next node of the list
...
Return
...
2
...

1
...
while(T!=NULL) do
a
...
Print (ITEM is present in the list)
ii
...
T= Tnext
3
...
Print (ITEM is not present in the list)
4
...
2
...

i
...

ii
...

iii
...

Algorithm:
INSERT_FIRST(LIST, START, ITEM)
Where LIST is a doubly linked list, START is a pointer variable which stores the
address of first element, and ITEM is an element to be inserted
...
Make a new node N
2
...
Write(Memory is not available
...
Return
3
...
NData= ITEM
5
...
If(START==NULL)
a
...
Return
7
...
NNext= START
9
...
Return
INSERT_LAST(LIST, START, ITEM)
Where LIST is a doubly linked list, START is pointer variable which stores the
address of first element, and ITEM is an element to be inserted
...
Make a new node N
2
...
Write(Memory is not available)
b
...
NPrev= NULL
4
...
NNext= NULL
6
...
START= N
b
...
T= START
8
...
T= TNext
9
...
N Prev= T
11
...

1
...
If (N= = NULL) then
a
...
Return
3
...
NData= ITEM
5
...
T= START
7
...
if (TData = = KEY) then
i
...
NNext= TNext
iii
...
TNext= N
53 | P a g e

Shashank Yadav (KIET-Ghaziabad)

v
...
T= TNext
8
...
Write (KEY is not present in the LIST)
9
...
2
...

1
...
START= STARTNext
b
...
Return
2
...
while (T != NULL) do
a
...
TPrevNext= TNext
ii
...
Return
b
...
If (T= = NULL)
a
...
Return
9
...
5 C program for implementing Doubly Linked List (InsertFirst, InsertLast,
InsertAfter, Deletion, Search, Traverse)
...
h>
#include ...
Insert First \n2
...
Insert After\n");
printf("4
...
Search\n6
...
Exit\n");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\nEnter one number ");
scanf("%d",&item);
InsertFirst(item);
break;
case 2: printf("\nEnter one number ");
scanf("%d",&item);
InsertLast(item);
break;
case 3: printf("\nEnter one number ");
scanf("%d",&item);
printf("\nEnter the element after which you want to insert the
node");
scanf("%d",&key);
InsertAfter(item,key);
break;
case 4: printf("\nEnter number which do you want to delete ");
scanf("%d",&item);
Delete(item);
break;
case 5: printf("\nEnter number which do you want to search ");
scanf("%d",&item);
Search(item);
break;
case 6: Traverse();
}
}while(choice!=7);
}
void InsertFirst(int item)
{
node *n;
n=(node*)malloc(sizeof(node));
n->prev=NULL;
55 | P a g e

Shashank Yadav (KIET-Ghaziabad)

n->data=item;
n->next=NULL;
if(start==NULL)
{
start=n;
}
else
{
start->prev=n;
n->next=start;
start=n;
}
printf("\n%d has been inserted",item);
}
void InsertLast(int item)
{
node *n, *t;
n=(node*)malloc(sizeof(node));
n->prev=NULL;
n->data=item;
n->next=NULL;
if(start==NULL)
{
start=n;
printf("\n%d has been inserted",item);
}
else
{
t=start;
while(t->next!=NULL)
{
t=t->next;
}
t->next=n;
n->prev=t;
printf("\n%d has been inserted",item);
}
}
void InsertAfter(int item, int key)
{
node *n,*t;
n=(node*)malloc(sizeof(node));
n->prev=NULL;
n->data=item;
n->next=NULL;

56 | P a g e

Shashank Yadav (KIET-Ghaziabad)

t=start;
while(t!=NULL)
{
if(t->data==key)
{
n->prev=t;
n->next=t->next;
t->next->prev=n;
t->next=n;
printf("\n%d has been inserted",item);
break;
}
else
t=t->next;
}
if(t==NULL)
printf("\n%d is not present in the list",key);
}

void Delete(int item)
{
node *t;
if(start->data==item)
{
start=start->next;
start->prev=NULL;
printf("%d has been deleted",item);
}
else
{
t=start->next;
while(t!=NULL)
{
if(t->data==item)
{
t->prev->next=t->next;
t->next->prev=t->prev;
free(t);
printf("%d has been deleted",item);
break;
}
else
{
t=t->next;
}
}
if(t==NULL)
57 | P a g e

Shashank Yadav (KIET-Ghaziabad)

printf("\n%d is not present in the list",item);
}
}
void Search(int item)
{
node *t;
t=start;
while(t!=NULL)
{
if(t->data= =item)
{
printf("\n%d is present in the list",item);
break;
}
t=t->next;
}
if(t==NULL)
printf("\n%d is not present in the list",item);
}
void Traverse()
{
node *t;
t=start;
if(t==NULL)
{
printf("\nList is Empty");
}
else
{
printf("\nLinked list\n");
while(t!=NULL)
{
printf("%d\t",t->data);
t=t->next;
}
}
}

58 | P a g e

Shashank Yadav (KIET-Ghaziabad)

9
...

12

15

13

19

25

START
Data

Address of Next Node

Address of First Node

Fig
...
3
...

Algorithm:
TRAVERSE_LIST (LIST, START)
Where LIST is a circular linked list and START is a pointer variable which points the
first element of the LIST
...
T= START
//T is a temporary pointer variable, which points the first
element of the list
...
do
3
...
Process (T Data)
b
...

4
...
Return
...
3
...

1
...
do
3
...
if (T Data == ITEM) then
i
...
Return
b
...
}while(T!=START)
5
...
3
...

i
...

59 | P a g e

Shashank Yadav (KIET-Ghaziabad)

ii
...


Insert node at Last position
...


Algorithm:
INSERT_FIRST(LIST, START, ITEM)
Where LIST is a circular linked list, START is a pointer variable which stores the
address of first element, and ITEM is an element to be inserted
...
Make a new node N
2
...
Write(Memory is not available)
b
...
NData= ITEM
4
...
START=N
b
...
Return
5
...
while(TNext != START)
a
...
TNext= N
8
...
START=N
10
...

1
...
If(N= = NULL) then
a
...
Return
3
...
NNext= NULL
5
...
START=N
b
...
Return
6
...
while(TNext!=START)
a
...
TNext= N
9
...
Return
INSERT_AFTER(LIST, START, ITEM, KEY)

60 | P a g e

Shashank Yadav (KIET-Ghaziabad)

Where LIST is a circular linked list, START is pointer variable which stores the
address of first element, ITEM is an element to be inserted, KEY is an element after which
new element ITEM will be inserted
...
Make a new node N
2
...
Write (Memory is not available)
b
...
NData= item
4
...
T= START
6
...
{
a
...
NNext= TNext
ii
...
Return
b
...
}while(T!=START)
9
...
Return
9
...
4 Deleting node from Circular Linked List:
Algorithm
DELETE(LIST, START, ITEM)
Where LIST is a circular linked list, START is a pointer variable which points the
first element of the LIST, ITEM is an element to be deleted
...
If(STARTData = = ITEM) then
a
...
If(START= = STARTNext) then
i
...
Return
c
...
t= tNext
d
...
tNext= start
f
...
P= START
3
...
while(T!=START)
a
...
PNext= TNext
ii
...
P=T
c
...
If(T= =START) then
a
...
Return
9
...
5 C program for implementing Circular Linked List (InsertFirst, InsertLast,
InsertAfter, Deletion, Search, Traverse)
...
h>
#include ...
Insert First \n2
...
Insert After\n");
printf("4
...
Search\n6
...
Exit\n");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\nEnter one number ");
scanf("%d",&item);
InsertFirst(item);
break;
case 2: printf("\nEnter one number ");
scanf("%d",&item);
InsertLast(item);
break;
case 3: printf("\nEnter one number ");
scanf("%d",&item);
printf("\nEnter the element after which you want to insert the
node ");
62 | P a g e

Shashank Yadav (KIET-Ghaziabad)

scanf("%d",&key);
InsertAfter(item,key);
break;
case 4: printf("\nEnter number which do you want to delete ");
scanf("%d",&item);
Delete(item);
break;
case 5: printf("\nEnter number which do you want to search ");
scanf("%d",&item);
Search(item);
break;
case 6: Traverse();
}
}while(choice!=7);
}
void InsertFirst(int item)
{
node *n, *t;
n=(node*)malloc(sizeof(node));
n->data=item;
if(start==NULL)
{
start=n;
n->next=start;
printf("\n%d has been inserted",item);
}
else
{
t=start;
while(t->next!=start)
{
t=t->next;
}
t->next=n;
n->next=start;
start=n;
printf("\n%d has been inserted",item);
}
}
void InsertLast(int item)
{
node *n, *t;
n=(node*)malloc(sizeof(node));
n->data=item;
n->next=NULL;
63 | P a g e

Shashank Yadav (KIET-Ghaziabad)

if(start==NULL)
{
start=n;
n->next=start;
printf("\n%d has been inserted",item);
}
else
{
t=start;
while(t->next!=start)
{
t=t->next;
}
t->next=n;
n->next=start;
printf("\n%d has been inserted",item);
}
}
void InsertAfter(int item, int key)
{
node *n,*t;
n=(node*)malloc(sizeof(node));
n->data=item;
n->next=NULL;
t=start;
do
{
if(t->data==key)
{
n->next=t->next;
t->next=n;
printf("\n%d has been inserted",item);
return;
}
t=t->next;
}while(t!=start);
printf("\n%d is not present in the list",key);
}
void Delete(int item)
{
node *t, *p;
if(start->data==item)
{
p=start;
64 | P a g e

Shashank Yadav (KIET-Ghaziabad)

t=start;
if(start==start->next)
{
free(t);
start=NULL;
printf("\n%d has been deleted",item);
}
else
{
while(t->next!=start)
{
t=t->next;
}
start=start->next;
t->next=start;
free(p);
printf("%d has been deleted",item);
}
}
else
{
p=start;
t=start->next;
while(t!=start)
{
if(t->data==item)
{
p->next=t->next;
free(t);
printf("%d has been deleted",item);
break;
}
else
{
p=t;
t=t->next;
}
}
if(t==start)
printf("\n%d is not present in the list",item);
}
}
void Search(int item)
{
node *t;
t=start;
do
65 | P a g e

Shashank Yadav (KIET-Ghaziabad)

{
if(t->data==item)
{
printf("\n%d is present in the list",item);
return;
}
t=t->next;
}while(t!=start);
printf("\n%d is not present in the list",item);
}
void Traverse()
{
node *t;
t=start;
if(t==NULL)
{
printf("\nList is Empty");
}
else
{
printf("\nLinked list\n");
do
{
printf("%d\t",t->data);
t=t->next;
}while(t!=start);
}
}

9
...

12

13

15

19

TOP

Fig
...
h>
#include ...
Push\n2
...
Traverse\n4
...
5 Queue implementation by Linked List
12

13

15

19

25

FRONT
REAR

Fig
...
h>
#include ...
Insert\n2
...
Traverse\n4
...
6 Dqueue implementation by Linked List
#include ...
h>
#include ...
Front Insert\n2
...
Front Delete\n");
printf("4
...
Traverse\n6
...
7 Priority Queue implementation by Linked List
...
h>
#include ...
h>
typedef
struct node
{
int data;
73 | P a g e

Shashank Yadav (KIET-Ghaziabad)

int pr;
struct node *next;
}node;
node *start;
void QInsert(int,int);
void QDelete();
void QTraverse();
void main()
{
int choice, item, p;
clrscr();
do
{
printf("\n\nEnter choice for Priority Queue\n");
printf("1
...
Delete\n3
...
Exit\n");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\nEnter one number ");
scanf("%d",&item);
printf("\nEnter priority of number ");
scanf("%d",&p);
QInsert(item,p);
break;
case 2: QDelete();
break;
case 3: QTraverse();
}
}while(choice!=4);
}
void QInsert(int item, int priority)
{
node *n, *t, *p;
n=(node*)malloc(sizeof(node));
n->data=item;
n->pr=priority;
n->next=NULL;
if(start==NULL)
{
start=n;
}
else if(start->pr> priority)
{
n->next=start;
74 | P a g e

Shashank Yadav (KIET-Ghaziabad)

start=n;
}
else if(start->next==NULL)
{
start->next=n;
}
else
{
p=start;
t=start->next;
while(t!=NULL)
{
if(t->pr > priority)
{
n->next=t;
p->next=n;
break;
}
p=t;
t=t->next;
}
if(t==NULL)
p->next=n;
}
printf("\n%d has been inserted",item);
}
void QDelete()
{
node *t;
t=start;
if(t==NULL)
printf("\nPriority Queue is Empty");
else
{
start=start->next;
printf("\n%d has been deleted",t->data);
free(t);
}
}
void QTraverse()
{
node *t;
t=start;
if(t==NULL)
printf("\nPriority Queue is empty");
else
{
printf("\nPriority Queue is\n");
75 | P a g e

Shashank Yadav (KIET-Ghaziabad)

while(t!=NULL)
{
printf("%d-%d\t",t->data,t->pr);
t=t->next;
}
}
}

9
...

 Polynomials are the expressions containing number of terms with nonzero coefficients
and exponents
...

( )
o
 ai are nonzero coefficients
...
And
such a node contains three fields
...
The linked list representation is

P
5

3

2

Coefficient

2

Exponent

10

Address

9
...
1 C program for adding two polynomials
...
h>
#include ...
h>
typedef
struct node
{
int coeff;
int expo;
struct node *next;
}node;
node *start, *p1, *p2, *p3;

76 | P a g e

1

6

0

NULL

Shashank Yadav (KIET-Ghaziabad)

void Create();
void Add();
void Display(node*);
void main()
{
int choice;
clrscr();
do
{
printf("\n\nEnter choice\n");
printf("1
...
Create second polynomial");
printf("\n3
...
Exit\n");
scanf("%d",&choice);
switch(choice)
{
case 1: Create();
p1=start;
start=NULL;
Display(p1);
break;
case 2: Create();
p2=start;
start=NULL;
Display(p2);
break;
case 3: Add();
Display(p3);
start=NULL;
}
}while(choice!=4);
}
void Create()
{
int term, i;
node *n,*t;
printf("\nHow many terms in the polynomial ");
scanf("%d",&term);
for(i=1;i<=term;i++)
{
n=(node*)malloc(sizeof(node));
n->next=NULL;
printf("\n\nEnter coefficient ");
scanf("%d",&n->coeff);
printf("\nEnter Exponent ");
scanf("%d",&n->expo);
if(start==NULL)
{
77 | P a g e

Shashank Yadav (KIET-Ghaziabad)

start=n;
}
else
{
t=start;
while(t->next!=NULL)
{
t=t->next;
}
t->next=n;
}
printf("\nTerm is inserted");
}
}
void Add()
{
node *n, *t, *p, *q;
t=p1;
p=p2;
while(t!=NULL || p!=NULL)
{
n=(node*)malloc(sizeof(node));
n->next=NULL;
if(t!=NULL && p!=NULL && t->expo==p->expo)
{
n->coeff=t->coeff+ p->coeff;
n->expo=t->expo;
t=t->next;
p=p->next;
}
else if(p==NULL || t->expo> p->expo)
{
n->coeff= t->coeff;
n->expo= t->expo;
t=t->next;
}
else if(t==NULL || t->expo < p->expo)
{
n->coeff= p->coeff;
n->expo= p->expo;
p=p->next;
}
if(start==NULL)
start=n;
else
{
q=start;
78 | P a g e

Shashank Yadav (KIET-Ghaziabad)

while(q->next!=NULL)
{
q=q->next;
}
q->next=n;
}
}
p3=start;
}
void Display(node *t)
{
printf("\n");
while(t!=NULL)
{
printf("%d-%d\t",t->coeff,t->expo);
t=t->next;
}
}

9
...

A = (a0, a1, a2, …, an-1) where ai is either atomic value or a list
...

When ai is a list, it is called sub-list
...

 A= (2, (3, 4), 8) list having length 3, there are two atomic node and a list containing
two atomic nodes

---

Title: LinkList (DSA)
Description: Basic to advance coverage of LINKLISTS concept in DSA and practice questions.

Buy These NotesPreview