Unit IV

LINKED LISTS

1
 Objectives

 Recognize need of a data structure, which dynamically can shrink

and grow
 Realization of linked list as dynamic data structure to
understand the well-defined, clear, and simple approach of
program design
 Utilize flexibility of the same easily and effectively to understand
sequential organization of data
 Learn variants of linked list and use them for appropriate
applications
Memory Allocation
 Introduction To Static & Dynamic Memory
Allocation

Sr. No. Static Memory Dynamic Memory

1. Static memory allocation is done Memory allocation is done at run

at compile time time
2. Prior to allocation of memory No need to know amount of
some fixed amount of it must be memory prior to allocation
decided
3. Wastage of memory or shortage No wastage of memory or
of memory shortage of memory
4. Faster Execution than dynamic Slower execution than static
memory memory
5. Ex. Arrays Ex. Linked list
Memory Model

OS Program & Program code

Memory for static variables

Stack can grow in downward direction
Stack memory for local variables

Heap Memory
Heap can grow in upward direction

 C/C++ uses the memory which is divided into 4 parts Program code, static
area, local data and heap
 Static area stores static variables, global data
 The stack is for local variables
 Heap memory is to allocate and de-allocate memory at run time.
 Stack and heap are part of dynamic memory management. These areas can
grow towards each other.
malloc: Allocating a block of memory
General form
int *ptr = (cast-type *) malloc(byte-size);
ptr is a pointer of type cast-type
The malloc() returns a pointer (of cast-type) to an area of memory with size
byte-size. If there is not enough space a NULL pointer is returned.

Example
• x=(int *) malloc(100*sizeof(int));
• cptr=(char *) malloc(10);
• st= (struct *) malloc(sizeof(struct store));

C++ supports malloc function and also has another operator new that 6
perform the task of allocating
Example int *p = new int[10]
calloc: Allocating multiple block of memory
While malloc() allocates a single block of storage space,
calloc() allocates multiple blocks of storage, each of the same
size, and then set all bytes to zero. If there is not enough space
a NULL pointer is returned.

General form
ptr=(cast-type *) calloc(n, element-size);

7
Example ptr = (int*) calloc(5, 5*sizeof(int))
ptr = (float*) calloc(25, sizeof(float));
realloc( ); Altering the size of a block
It is likely that the previous allocated memory is not
sufficient and we need additional space for more elements.
It is also possible that the memory allocated is much
larger than necessary and we want to reduce it.
General form
ptr=realloc(ptr, 100);

• Modifies the size of previously allocated space by malloc() or

calloc()

Example

8
realloc( ); Altering the size of a block

9
free( ); Releasing the used space
“free” method in C is used to dynamically de-
allocate the memory.
The memory allocated using functions malloc() and
calloc() is not de-allocated on their own.
Hence the free() method is used, whenever the dynamic
memory allocation takes place.
It helps to reduce wastage of memory by freeing it.

General form
free(ptr_name);

Example
free(ptr); // available in both C & C++
1
delete ptr; // available in C++ only 0
free( ); Releasing the used space

1
1
 WHAT IS A LINKEDLIST?

 A linked list is a collection of items:

 It can have an arbitrary length
 Objects / elements can be inserted or removed at
arbitrary locations in the list

 A list can be traversed in order one item at a time

Head  Every linked list having two fields

1005 Data next

10 5010 1
8 2010 20 NULL 2
1005 5010 2010
LIST AS AN ADT
 Linked List, a linear collection of data items, called
nodes, where order is given by means of pointers.
 Elements:
 Each node is divided into two parts:
 Data
 Link ( pointing towards the next node)
 (Common) Operations of Linked List
 IsEmpty: determine whether or not the list is empty
 InsertNode: insert a new node at a particular position
 FindNode: find a node with a given value
 DeleteNode: delete a node with a given value
 DisplayList: print all the nodes in the list
1
3
LINKED LIST TERMINOLOGIES
 Traversal of List
 Means to visit every element or node in the list
beginning from first to last.
 Predecessor and Successor

 In the list of elements, for any location n, (n-1) is

predecessor and (n+1) is successor
 In other words, for any location n in the list, the left
element is predecessor and the right element is
successor.
 Also, the first element does not have predecessor
and the last element does not have successor. 6
VARIATIONS OF LINKED LISTS

 Singly linked lists

 Circular linked lists

 Doubly linked lists

 Doubly Circular linked list

1
5
Singly Linked List

16
 Singly LINKED LISTS

A B C 

Head

 A linked list is a series of connected nodes

 Each node contains at least node
 A piece of data (any type) A
 Pointer to the next node in the list
data pointer
 Head: pointer to the first node
 The last node points to NULL

 [Link] 17
LISTS – ANOTHER PERSPECTIVE
A list is a linear collection of varying length of
homogeneous components.

Homogeneous: All components are of the same

type.

Linear: Components are ordered in a line (hence

called Linear linked lists).

18
An Array A Linked List

19
AN INTEGER LINKED LIST

First Node of List Last Node of List

Head
10 13 5 2

data next NULL

20
THE NULL POINTER

NULL is a special pointer value that does not reference

any memory cell.

If a pointer is not currently in use, it should be set to

NULL so that one can determine that it is not pointing
to a valid address:

int *p;
p = NULL;
21
CREATING A LIST NODE
struct Node {
int data; // data in node
Node *next; // Pointer to next node
};

Node *p;
p = new Node;
p - > data = 10;
p - > next = NULL;

p 10
22
CREATING A LIST NODE
class Node {
public:
int data; // data in node
Node *next; // Pointer to next node
};

Node *p;
p = new Node;
p -> data = 10;
p -> next = NULL;
p 10
23
Basic Concepts

JOINING TWO NODES

Node *p, *q;

p = new Node; p 10
p - > data = 10;
p - > next = NULL;

q = new Node;
q - > data = 6; q 6
q - > next = NULL;

p - > next = q;
p 10 6
20

q
Basic Concepts

ACCESSING LIST DATA

Node 1 Node 2

p 10 6

Expression Value
p Pointer to first node (head)
p - > data 10
p - > next Pointer to next node
p - > next - > data 6
p - > next - > next NULL pointer
21
BASIC LINKED LIST OPERATIONS

 Traversing through the list

 Node Insertion
 Insertion at the beginning of the list
 Insertion at the end of the list
 Insertion in between of the list
 Node Deletion
 Deletion at the beginning of the list
 Deletion at the end of the list
 Deletion from in between node of the list

31
NODE INSERTION
 Insertion at the beginning of the list
 Insertion at the end of the list

 Insertion in the in between of the list

36
NODE INSERTION AT THE BEGINNING
Steps:
 Create a node

 Set the node data values

 Connect the pointers

Initial list head 48 17 142 /

Step 1
Step 2

List after Step 3

head 93
NODE INSERTION AT THE BEGINNING

Initial list head 48 17 142 //

Node *ptr;
ptr = new Node; ptr
ptr - > data = 93;
ptr - > next = head; ptr
head = ptr; 93

head

Rearrange:

head 93
NODE INSERTION AT THE BEGINNING

Node * insert_beg(Node *head, int x)

{
Node *ptr;
ptr = new Node;
ptr -> data = X;
ptr -> next = NULL;
if(head = = NULL)
{
return (ptr);
}
ptr -> next = head
head = ptr;
return (head)
}
 NODE INSERTION AT THE END
Steps:
 Create a Node

 Set the node data values

 Connect the pointers

Initial list head 48 17 142 //

Step 1 Step 2

List after Step 3

NODE INSERTION AT THE END

Initial list head 48 17 142 //

Need a pointer at the last
node ptr

Node * ptr;
ptr = head;
while (ptr->next != NULL)
{
ptr = ptr->next;
}
NODE INSERTION AT THE END

Initial list head 48 17 142 //

ptr

Node * p;
p = new Node;
p -> data = 150; 150 //
p -> next = NULL;
p
NODE INSERTION AT THE END

ptr -> next = p;

ptr

head 48 17 142

150 //
p
NODE INSERTION AT THE END

Node * insert_end(Node *head, int x)

{
Node *ptr, *p;
p = new Node;
p -> data = X;
p -> next = NULL;
if(head = = NULL)
{
return (p);
}
ptr = head;
while(ptr -> next != NULL)
ptr = ptr -> next;
ptr -> next = p
return (head)
}
 NODE INSERTION IN-BETWEEN
Steps:
 Create a Node

 Set the node data values Step 1 Step 2

 Break pointer connection

 Re-connect the pointers

Step 3

Step 4
NODE INSERTION IN-BETWEEN

Need a pointer on the node after which a new node is to be

Inserted. For instance, if new node is to be inserted after
the node having value ‘17’, we need a pointer at this node

ptr
How to get pointer on desired node?
NODE INSERTION AT ARBITRARY POSITION
Suppose we want to insert a node after the node having
value ‘x’:

Node * ptr;
ptr = head;
while (ptr->data != x)
{
ptr = ptr->next;
}

ptr
NODE INSERTION AT ARBITRARY POSITION
Node * ptr; Node * p;
ptr = head; p = new Node;
while (ptr->data != x) p -> data = 100;
{ p -> next = NULL;
ptr = ptr->next;
}

ptr

150 //
p
NODE INSERTION AT IN-BETWEEN / ARBITRARY
Node * ptr; Node * p;
ptr = head; p = new Node;
while (ptr->data != x) p -> data = 150;
{ p -> next = NULL;
ptr = ptr->next; p -> next = ptr -> next;
} ptr -> next = p;

ptr

150

p
NODE INSERTION IN-BETWEEN

Node * insert_between(Node *head, int x, int y)

{
Node *ptr, *p;
p = new Node;
p -> data = X;
p -> next = NULL;
if(head = = NULL)
{
return (p);
}
ptr = head;
while(ptr -> data != y)
ptr = ptr -> next;
p -> next = ptr -> next;
ptr -> next = p;
return (head)
}
NODE DELETION

 Deleting from the beginning of the list

 Deleting from the end of the list

 Deleting from in-between of the list

DELETING FROM THE BEGINNING
Steps:
 Take head pointer to 2nd node

 Free the 1st node

head 6 4 17 42

head
6 4 17 42

head 4 17 42
DELETING FROM THE BEGINNING

head
ptr 6 4 17 42

head
head 6 4 17 42
ptr

head 4 17 42

Node * ptr;
ptr = head;
head = head ->next;
delete ptr;
NODE DELETION FROM BEGINNING

Node * delete_beg(Node *head)

{
Node *ptr;
if(head = = NULL)
{
cout<<“No element available to delete”;
return;
}
ptr = head;
head = head -> next;
free(ptr)
return (head)
}
DELETING FROM THE END
Steps:
 Take pointer at the end of list

 Set previous node pointer to NULL

 Delete the node

head 6 4 17 42

head 6 4 17
DELETING FROM THE END
We need a pointer one node before the node to be deleted

head 6 4 17 42

p q
Node * p;
Node * q;
p = head;
while (p -> next -> next != NULL)
{
p = p -> next;
}

q = p -> next;
delete (q);
P -> next = NULL
NODE DELETION FROM END

Node * delete_end(Node *head)

{
Node *p, *q;
if(head = = NULL)
{
cout<<“No node available to delete”;
return;
}
p = head;
while (p -> next -> next != NULL)
{
p = p -> next;
}
q = p -> next;
delete (q);
P -> next = NULL;
return (head);
}
DELETING IN-BETWEEN NODE
Steps:
 Set previous Node pointer to next node

 Break Node pointer connection

 Delete the node

head 6 4 17 42

head 6 4 17 42

head 6 4 42
DELETING FROM IN-BETWEEN POSITION
We need a pointer on the node to be deleted (as well a pointer to one
node before the node to be deleted)

head 6 4 17 42

p q
Node * p;
Node * q;
p = head; Given the value of the node to
while(p -> next -> data != x) be deleted, assume this to be
{ variable ‘x’
p = p -> next; Keep moving a pointer until the
required node is reached
}
q = p -> next;
p -> next = q -> next;
delete (q)
NODE DELETION FROM END

Node * delete_between(Node *head)

{
Node *p, *q;
if(head = = NULL)
{
cout<<“No node available to delete”;
return;
}
p = head;
while (p -> next -> data != x)
{
p = p -> next;
}
q = p -> next;
p -> next = q -> next;
delete (q);
return (head);
}
PROS AND CONS OF LINKED LISTS

• Access any item as long as external link to first item

maintained
• Insert new item without shifting
• Delete existing item without shifting
• Can expand/contract as necessary
• Overhead of links: used only internally, pure overhead
• No longer have direct access to each element of the
list
• We must go through first element, and then second,
and then third, etc. 57
Traversing the list

32
 fir st 9 17 22 26 34
ptr = first;
while (ptr != null_value)
{ ptr
Process data part of
node pointed to by ptr; 9 17 22 26 34
firs t
ptr = next part of node
pointed to by ptr;
} pt r

.
.
firs t 9 17 22 26 34

pt r

firs t 9 17 22 26 34

ptr
34
TRAVERSING THE LIST
Node * currNode;
currNode = head;
while (currNode != NULL)
{
cout<< currNode->data;
currNode = currNode->next;
}

35
 Circular linked list

A circular linked list is one which

has
 No ending.
 The null pointer in the last node of a linked list is
replaced with the address of its first node .
Structure of circular linked list

Rear

A 1000 B 2000 C 4000

4000 1000 2000
Operations on linked list

 The basic operations on

linked lists are :
1. Creation
2. Insertion
3. Deletion
4. Traversing
5. Searching
 What Is creation
 The creation operation is used to create a
linked list.
 There are two fields in singly circular inked
list.
 Data - any type
 Next – a pointer to the next node

 C/C++ representation
struct node
{
int data;
struct node *next;
}
 What Is creation of CLL
 Allocate a new node  Algorithm
 Insert new element  p = new node
 Make new node point to  p -> data = x
null  p -> next = NULL
 Create head to point to  Rear = p
new node
 Rear -> next = Rear
p Rear

93
NODE INSERTION IN CLL
 Insertion at the beginning of the list
 Insertion at the end of the list

 Insertion in the in between of the list

36
NODE INSERTION AT THE BEGINNING OR END
Steps:
 Create a node

 Set the node data values Rear

 Connect the pointers

Initial list 48 17 142

Step 1
Step 2

Rear
List after Step 3

93
 NODE INSERTION AT THE BEGINNING OR END
Rear
Initial list

Node *p;
p = new Node; 48 17 142
p -> data = 93;
p -> next = NULL;
p ->next = Rear->next;
Rear -> next = p
p p 93

p
93

Rear
NODE INSERTION AT THE BEGINNING OR END

Rear p
Rearrange

93

Rear = p

Rear
Final List

93
NODE INSERTION AT THE BEGINNING OR END
Node * insert_beg_end(Node *Rear, int x)
{
Node *p;
p = new Node;
p -> data = X;
p -> next = NULL;
if(Rear = = NULL)
{
Rear = p;
p -> next = p
return (Rear);
}
else
{
p -> next = Rear -> next
Rear -> next = p;
Rear = p;
return (Rear)
}
}
NODE INSERTION IN BETWEEN
Steps:
 Create a node

 Set the node data values Rear

 Connect the pointers

Initial list 48 17 142

Step 1
Step 2

Rear
List after Step 3

48 93 17 142
 NODE INSERTION IN BETWEEN
Rear
Initial list

Node *p;
p = new Node; 48 17 142
p -> data = 93;
p -> next = NULL;
q = Rear;
While(q->data != y)
p p 93
q = q -> next;
p ->next = q ->next;
q -> next = p
p
93

q Rear
 NODE INSERTION IN BETWEEN

Re-arranging
p Rear

48 93 17 142

Rear = p
p Rear

48 93 17 142
NODE INSERTION IN-BETWEEN

Node * insert_between(Node *Rear, int x, int y)

{
Node *p;
p = new Node;
p -> data = x;
p -> next = NULL;
if(Rear = = NULL)
{
return (p);
}
q = Rear;
while(q -> data != y)
q = q -> next;
p ->next = q ->next;
q -> next = p;
return (Rear);
}
NODE DELETION FROM BEGINNING OR END
Rear
Initial list

93

Rear

List after 48 17 142

deletion
NODE DELETION FROM BEGINNING OR END
Rear
Initial list

93

Node *p;
p = Rear;
while(p -> next != Rear)
p = p -> next; Rear
p

93
NODE DELETION FROM BEGINNING OR END
p Rear

93

Rear = p;
p = p -> next; Rear p

93

Rear -> next = p -> next;

delete p; Rear

48 17 142
NODE DELETION FROM BEGINNING OR END

Node * delete_beg_end(Node *Rear)

{
Node *p;
if(Rear = = NULL)
{
cout<<“No element available to delete”;
return;
}
p = Rear;
while(p -> next != Rear)
p = p -> next;
Rear = p;
p = p -> next;
Rear -> next = p -> next;
delete(p);
return (Rear)
}
NODE DELETION FROM IN BETWEEN
Rear
Initial list

93

Rear

List after 48 142 93

deletion In
Between node
NODE DELETION FROM IN BETWEEN
Rear
Initial list

93

p = Rear;
while(p -> next –> data != x)
p = p -> next;

p Rear

93
NODE DELETION FROM IN BETWEEN
q = p -> next

p q Rear

93

p -> next = q -> next;

delete (q); Rear

List after 48 142 93

deletion In
Between node
NODE DELETION FROM IN-BETWEEN

Node * delete_between(Node *Rear, int x)

{
Node *p, *q;
if(Rear = = NULL)
{
cout<<“No element available to delete”;
return;
}
p = Rear;
while(p -> next -> data != x)
p = p -> next;
q = p -> next;
p -> next = q -> next;
delete(q);
return (Rear);
}
Doubly LinkedList
 In doubly linked list each node contains two pointers.

 Each pointer points to either next node or previous node

 Doubly linked list is two-way list because one can move

either from left to right or from right to left.

 Each node of linked list consist of three fields

a. data
b. Prev, next: Address of previous and next node
Examples of Doubly Linked Lists
head
5000

2000 5000 3000 2000

5000 2000 3000

head
1000

3000 1000 2000 3000

1000 3000 2000

head
5000

2000 5000 3000 2000

5000 2000 3000

Operations on a Doubly linked list (DLL)

1) Create list.
2) Insert element at beginning in list.
3) Insert element at end in list.
4) Insert element in-Between list.
5) Delete element from the beginning of list.
6) Delete element from the end of list.
7) Delete element from in-Between list.
8) Traversing
Creation of Doubly linked list (DLL)

struct dnode
{
int data;
struct dnode *prev, *next;
}

head
5000

2000 5000 3000 2000

5000 2000 3000

Pseudo code for creation of DLL
dnode * create()
{
dnode *head,*p, *q;
int i, n, x;
cout<<“Enter no. of elements”;
cin>>n;
for(i=0; i<n; i++)
{
cout<< “Enter next data”;
p = new dnode;
cin>> p -> data;
p -> prev = p -> next = NULL;
if(head = = NULL)
head = p;
else
{
q = head;
while(q -> next != NULL)
q = q -> next;
q -> next = p;
p -> prev = q;
}
}
return (head);
}
Insertion in Doubly linked list (DLL)

1) Insert element at beginning in list.

2) Insert element at end in list.
3) Insert element in-Between list.
Insertion at beginning of DLL
head
Initial List 5000

2000 5000

5000 2000

dnode *p; p
p = new dnode;
p -> data = 20;
p -> prev = NULL;
3000
p -> next = NULL

head
3000

5000 3000 2000 5000

3000 5000 2000

Insertion at beginning of DLL
p -> next = head
p

5000
head
5000 3000

2000 5000

5000 2000

head -> prev = p

p

5000
head
5000 3000

3000 2000 5000

5000 2000
Insertion at beginning of DLL
head = p;
p

5000
head
3000 3000

3000 2000 5000

5000 2000

Re-arranging

head
3000

5000 3000 2000 5000

3000 5000 2000

NODE INSERTION AT BEGINNING OF DLL
dnode * insert_beg(dnode *head, int x)
{
dnode *p;
p = new dnode;
p -> data = x;
p -> prev = NULL;
p -> next = NULL
if(head = = NULL)
{
return (p);
}
p -> next = head;
head -> prev = p;
head = p;
return (head);
}
Insertion at end of DLL
head
Initial List 5000

2000 5000

5000 2000

dnode *p; p
p = new dnode;
p -> data = 20;
p -> prev = NULL;
3000
p -> next = NULL

head
5000

2000 5000 3000 2000

5000 2000 3000

Insertion at end of DLL
q = head; p

while(q -> next != NULL)

q = q -> next;
q -> next = p 3000
head q
5000

2000 5000 3000

5000 2000 p

p -> prev = q
2000

3000
head q
5000

2000 5000 3000

5000 2000
Insertion at end of DLL

Re-arranging

head
5000

2000 5000 3000 2000

5000 2000 3000

NODE INSERTION AT END OF DLL
dnode * insert_end(dnode *head, int x)
{
dnode *p, *q;
p = new dnode;
p -> data = x;
p -> prev = NULL;
p -> next = NULL
if(head = = NULL)
{
return (p);
}
q = head;
while(q -> next != NULL)
q = q -> next;
q -> next = p;
p -> prev = q;
return (head);
}
Insertion at In-between of DLL
head
Initial List 5000

2000 5000

5000 2000

dnode *p; p
p = new dnode;
p -> data = 20;
p -> prev = NULL;
3000
p -> next = NULL

head
5000

3000 5000 2000 3000

5000 3000 2000

Insertion at In-Between of DLL
p
q = head;
while(q -> data != y) 2000
q = q -> next;
3000
p -> next = q ->next
head q
5000

2000 5000

5000 2000
p
p -> prev = q;
5000 2000

3000
head q
5000

2000 5000

5000 2000
Insertion In-betwenn of DLL p
q -> next -> prev = p;

5000 2000

3000

head q
5000

2000 3000

5000 2000
p
q -> next = p
5000 2000

3000
head q
5000

3000 5000

5000 2000
Insertion In-Between of DLL

Re-arranging

head
5000

3000 5000 2000 3000

5000 3000 2000

NODE INSERTION IN-BETWEEN OF DLL
dnode * insert_end(dnode *head, int x, int y)
{
dnode *p, *q;
p = new dnode;
p -> data = x;
p -> prev = NULL;
p -> next = NULL
if(head = = NULL)
{
return (p);
}
q = head;
while(q -> data != y)
q = q -> next;
p -> next = q ->next;
p -> prev = q;
q -> next -> prev = p;
q -> next = p
return (head);
}
Deletion Operations on a Doubly linked
list (DLL)

1) Deletion of element from the beginning of list.

2) Deletion of element from the end of list.
3) Deletion of element from in-Between of list.
Deletion from Beginning of DLL
Initial List

head
5000

3000 5000 2000 3000

5000 3000 2000

head
5000

3000 5000 2000 3000

5000 3000 2000

After Deletion:
head
3000

5000 2000 3000

3000 2000
Deletion from Beginning of DLL
Initial List

head
5000

3000 5000 2000 3000

5000 3000 2000

dnode *p;
p = head;

p
head 5000
5000

3000 5000 2000 3000

5000 3000 2000

Deletion from Beginning of DLL
head = p -> next;

p head
5000 3000

3000 5000 2000 3000

5000 3000 2000

delete p;
head -> prev = NULL;

head
3000

2000 3000

3000 2000
NODE DELETION FROM BEGINNING

dnode * delete_beg(dnode *head)

{
dnode *p;
if(head = = NULL)
{
cout<<“No element available to delete”;
return;
}
p = head;
head = p -> next;
delete p;
head -> prev = NULL;
return (head);
}
Deletion from End of DLL
Initial List

head
5000

3000 5000 2000 3000

5000 3000 2000

head
5000

3000 5000 2000 3000

5000 3000 2000

After Deletion:
head
5000

3000 5000

5000 3000
Deletion from End of DLL
Initial List

head
5000

3000 5000 2000 3000

5000 3000 2000

dnode *p;
p = head;
While(p -> next != NULL)
P = p -> next;
p
head 5000
5000

3000 5000 2000 3000

5000 3000 2000

Deletion from End of DLL
P -> prev -> next = NULL;
p
head 5000
5000

3000 5000 3000

5000 3000 2000

delete p;

head
5000

3000 5000

5000 3000
NODE DELETION FROM END

dnode * delete_end(dnode *head)

{
dnode *p;
if(head = = NULL)
{
cout<<“No element available to delete”;
return;
}
p = head;
while(p -> next !=NULL)
p = p -> next;
p -> prev -> next = NULL;
delete p;
return (head);
}
Deletion from In-Between of DLL
Initial List

head
5000

3000 5000 2000 3000

5000 3000 2000

head
5000

3000 5000 2000 3000

5000 3000 2000

After Deletion:
head
5000

2000 5000

5000 2000
Deletion from End of DLL
Initial List

head
5000

3000 5000 2000 3000

5000 3000 2000

dnode *p;
p = head;
While(p -> data != x)
p = p -> next;

p
head 3000
5000

3000 5000 2000 3000

5000 3000 2000

Deletion from End of DLL
P -> prev -> next = p -> next;

p
head 3000
5000

2000 5000 2000 3000

5000 3000 2000

P -> next -> prev = p -> prev;

p
head 3000
5000

2000 5000 2000 5000

5000 3000 2000

Deletion from In-Between of DLL
delete p;

head
5000

2000 5000

5000 2000
NODE DELETION FROM In-Between

dnode * delete_end(dnode *head, int x)

{
dnode *p;
if(head = = NULL)
{
cout<<“No element available to delete”;
return;
}
p = head;
while(p -> data != x)
p = p -> next;
P -> prev -> next = p -> next;
P -> next -> prev = p -> prev;
delete p;
return (head);
}
Sorting DLL
Initial List

head
5000

3000 5000 2000 3000

5000 3000 2000

After Sorting:

head
5000

3000 5000 2000 3000

5000 3000 2000

Sorting DLL
Initial List

head
5000

3000 5000 2000 3000

5000 3000 2000

dnode *current, *index;

current = head;
index = current -> next;

current index
5000 3000
head
5000

3000 5000 2000 3000

5000 3000 2000

Sorting DLL
if(current->data > index->data)
swap
current index
5000 3000
head
5000

3000 5000 2000 3000

5000 3000 2000

index = index -> next;

current index
5000 3000
head
5000

3000 5000 2000 3000

5000 3000 2000

Sorting DLL
if(current->data > index->data)
swap
current index
5000 3000
head
5000

3000 5000 2000 3000

5000 3000 2000

current = current -> next;

current index
3000
head 5000

5000

3000 5000 2000 3000

5000 3000 2000

Sorting of DLL
void sortList() {
node *current = NULL, *index = NULL;
int temp;
if(head == NULL) { //Check whether list is empty
return;
}
else {
//Current will point to head
for(current = head; current->next != NULL; current = current->next) {
//Index will point to node next to current
for(index = current->next; index != NULL; index = index->next) {
//If current's data is greater than index's data, swap
if(current->data > index->data) {
temp = current->data;
current->data = index->data;
index->data = temp;
}
}
}
}
}
Operations on a Doubly Circular linked
list (DCLL)
1) Create list.
2) Insert element at beginning in list.
3) Insert element at end in list.
4) Insert element in-Between list.
5) Delete element from the beginning of list.
6) Delete element from the end of list.
7) Delete element from in-Between list.
8) Traversing
Creation of Doubly linked list (DCLL)

struct dnode
{
int data;
struct dnode *prev, *next;
}
rear
3000

2000 5000 3000 2000

5000 2000 3000

Pseudo code for creation of DCLL
dnode * create()
{
dnode *rear,*p, *q;
int i, n, x;
cout<<“Enter no. of elements”;
cin>>n;
for(i=0; i<n; i++)
{
cout<< “Enter next data”;
p = new dnode;
cin>> p -> data;
p -> prev = p -> next = NULL;
if(rear = = NULL)
{ rear = p; p -> next = p; p -> prev = p; }
else
{
p -> prev = rear;
p -> next = rear -> next;
rear -> next -> prev = p;
rear –> next = p
}
}
return (rear);
}
Insertion in Doubly Circular linked list
(DCLL)
1) Insert element at beginning in list.
2) Insert element at end in list.
3) Insert element in-Between list.
Insertion at beginning/end of DCLL
rear
3000

Initial List
3000 5000

5000 3000

dnode *p; p
p = new dnode;
p -> data = 20;
p -> prev = NULL;
2000
p -> next = NULL
rear
2000

2000 3000 5000 2000 3000 5000

5000 3000 2000

Insertion at beginning/end of DCLLp
rear
3000

5000 5000
2000
3000 3000

5000 3000

p -> prev = rear;

p -> next = rear -> next

rear
3000 p

3000 5000
3000 3000 5000 5000
2000
5000 3000
Insertion at beginning/end of DCLL
rear -> next -> prev = p
rear
3000 p

3000 5000
2000 3000 5000 5000
2000
5000 3000

rear -> next = p

rear
3000 p

3000 5000
2000 3000 5000 2000
2000
5000 3000

rear = p
Insertion at beginning/end of DCLL

rear
After Re-arrangement 2000

2000 3000 5000 2000 3000 5000

5000 3000 2000

NODE INSERTION AT THE BEGINNING OR END
Node * insert_beg_end(Node *Rear, int x)
{
Node *p;
p = new Node;
p -> data = x;
p -> next = NULL;
p -> prev = NULL;
if(Rear = = NULL)
{
Rear = p;
p -> next = p;
p -> prev = p;
return (Rear);
}
else
{
p -> prev = rear;
p -> next = rear -> next;
rear -> next -> prev = p;
rear -> next = p
Rear = p;
return (Rear)
}
}
Insertion Between of DCLL
rear
3000

Initial List
3000 5000

5000 3000

dnode *p; p
p = new dnode;
p -> data = 8;
p -> prev = NULL;
2000
p -> next = NULL

rear
2000

3000 2000 5000 3000 2000 5000

5000 2000 3000

Insertion In-Between of DCLL
q = rear; p
while(q->data != y)
q = q->next;
rear
2000 3000
q

3000 3000 5000 5000

5000 3000

p -> prev = q; p
p -> next = q -> next
5000 3000 rear
q 3000
2000

3000 3000 5000 5000

5000 3000
Insertion In-Between of DCLL
q -> next-> prev = p; p

5000 3000 rear

q 3000
2000

3000 3000 2000 5000

5000 3000

q -> next = p; p

5000 3000 rear

q 3000
2000

3000 2000 2000 5000

5000 3000
Insertion Between of DCLL

Rear = p;

rear
2000

3000 2000 5000 3000 2000 5000

5000 2000 3000

NODE INSERTION IN-BETWEEN OF DCLL
Node * insert_between(Node *Rear, int x, int y)
{
Node *p;
p = new Node;
p -> data = x;
p -> next = p -> prev = NULL;
if(Rear = = NULL) {
Rear = p;
p -> next = p;
p -> prev = p;
return (Rear);
}
else {
q = rear;
while(q -> data != y)
q = q -> next;
p -> prev = q;
p -> next = q -> next;
q -> next-> prev = p;
q -> next = p;
Rear = p;
return (Rear);
}
}
Deletion from Doubly Circular linked list
(DCLL)
1) Delete element at beginning of list.
2) Delete element at end of list.
3) Delete element in-Between of list.
Deletion from beginning/end of DCLL
rear
Initial List
2000

2000 3000 5000 2000 3000 5000

5000 3000 2000

rear
2000

2000 3000 5000 2000 3000 5000

5000 3000 2000

rear 3000

2000 3000 5000 2000

5000 3000 After Deletion

Deletion from beginning/end of DCLL
rear
Initial List
2000

2000 3000 5000 2000 3000 5000

5000 3000 2000

dnode *p;
p = rear;
rear = rear -> prev
rear p
3000 2000

2000 3000 5000 2000 3000 5000

5000 3000 2000

Deletion from beginning/end of DCLL
p -> next -> prev = rear

rear p
3000 2000

3000 3000 5000 2000 3000 5000

5000 3000 2000

rear -> next = p -> next

rear p
3000 2000

3000 3000 5000 5000 3000 5000

5000 3000 2000

Deletion from beginning/end of DCLL
delete p;
rear p
3000 2000

3000 3000 5000 5000 3000 5000

5000 3000 2000

After Deletion
rear
3000

2000 3000 5000 2000

5000 3000
NODE DELETION FROM BEGINNING OR END

Node * delete_beg_end(Node *rear)

{
Node *p;
if(rear = = NULL)
{
cout<<“No element available to delete”;
return;
}
p = rear;
rear = rear -> prev;
p -> next -> prev = rear;
rear -> next = p -> next;
delete(p);
return(rear);
}
Deletion from In-Between of DCLL
rear
Initial List
2000

2000 3000 5000 2000 3000 5000

5000 3000 2000

rear
2000

2000 3000 5000 2000 3000 5000

5000 3000 2000

rear 2000

2000 2000 5000 5000

5000 2000 After Deletion

Deletion from beginning/end of DCLL
rear
Initial List
2000

2000 3000 5000 2000 3000 5000

5000 3000 2000

dnode *p;
p = rear;
while(p -> data != y)
p rear
p = p -> next; 2000
3000

2000 3000 5000 2000 3000 5000

5000 3000 2000

Deletion from beginning/end of DCLL
P -> prev -> next = p -> next
P -> next -> prev = p -> prev
p rear
3000 2000

2000 3000 5000 2000 3000 5000

5000 3000 2000

delete p;

rear 2000

2000 2000 5000 5000

5000 2000 After Deletion

NODE DELETION IN-BETWEEN

dnode * delete_end(dnode *read, int y)

{
dnode *p;
if(read = = NULL)
{
cout<<“No element available to delete”;
return;
}
p = rear;
while(p -> data != y)
p = p -> next;
P -> prev -> next = p -> next;
P -> next -> prev = p -> prev;
delete p;
return (rear);
}
 Polynomial Manipulation

1) Representation of Polynomial
2) Polynomial Addition
3) Polynomial Multiplication
 Representation of Polynomial

Each node for each term of polynomial consist of 3

fileds named coefficient, exponent and address of next
node
coeff expo next

To represent 5x3 + 2x – 4 polynomial

head

5 3 2 1 -4 0

To represent 98x78 + 2x5 – 4x2 + 3 polynomial

head

98 78 2 5 -4 2 3 0
 Representation of Polynomial

C / C++ structure:

tydef struct pnode

{
int coeff;
int expo;
struct pnode *next;
}
 Addition of Polynomial

5x3 + 2x – 4 + 98x4 + 2x3 – 4x2 + 3

head1

5 3 2 1 -4 0

head2

98 4 2 3 -4 2 3 0

Pnode *p1, p2
head1 = p1;
head2 = p2;
 Addition of Polynomial
5x3 + 2x – 4 + 98x4 + 2x3 – 4x2 + 3

head1 p1

5 3 2 1 -4 0

head2 p2

98 4 2 3 -4 2 3 0

head3= p3 = new pnode;

p3 -> next = NULL;
head3 p3
if(p2 -> expo > p1 -> expo)
{
98 4
P3 -> coeff = p2 -> coeff;
P3 -> expo = p2 -> expo;
p2 = p2 -> next;
}
 Addition of Polynomial
5x3 + 2x – 4 + 98x4 + 2x3 – 4x2 + 3
head1 p1

5 3 2 1 -4 0

head2 p2

98 4 2 3 -4 2 3 0

P3 -> next = new pnode;

p3 = p3 -> next;
p3 -> next = NULL;
head3 p3
if(p1 -> expo = = p2 -> expo)
{
P3 -> coeff = p1 -> coeff + p2->coeff; 98 4 7 3
P3 -> expo = p1 -> expo;
p1 = p1 -> next;
p2 = p2 -> next;
}
 Addition of Polynomial
head1 p1

5 3 2 1 -4 0

head2 p2

98 4 2 3 -4 2 3 0

P3 -> next = new pnode;

p3 = p3 -> next;
p3 -> next = NULL;
if(p1 -> expo > p2 -> expo)
{
P3 -> coeff = p1 -> coeff;
P3 -> expo = p1 -> expo;
p1 = p1 -> next;
}
head3 p3

98 4 7 3 -4 2 2 1
 Addition of Polynomial

Final Linked list after addition

head3 p3

98 4 7 3 -4 2 2 1 -1 0
Pseudocode: Addition of Polynomial
pnode *addpoly(pnode *p1, pnode *p2)
{
pnode *p3, *head3;
p3 = NULL;
while(p1 != NULL && p2 != NULL)
{
if(p3 = = NULL)
{
head3= p3= new pnode;
p3 -> next = NULL;
}
else
{
p3 -> next = new pnode;
p3 = p3 -> next;
p3 -> next = NULL;
}
Pseudocode: Addition of Polynomial
if(p1 -> expo > p2 -> expo)
{
p3 -> coeff = p1 -> coeff;
p3 -> expo = p1 -> expo;
p1 = p1 -> next;
}
elseif( p2 -> expo > p1 -> expo)
{
p3 -> coeff = p2 -> coeff;
p3 -> expo = p2 -> expo;
p2 = p2 -> next;
}
else
{
p3 -> coeff = p1 -> coeff + p2 -> coeff;
p3 -> expo = p1 -> expo;
p1 = p1 -> next;
p2 = p2 -> next;
}
}
Pseudocode: Addition of Polynomial
while(p1 != NULL)
{
p3 -> next = new pnode;
p3 = p3 -> next;
P3 -> next = NULL;
p3 -> coeff = p1 -> coeff;
p3 -> expo = p1 -> expo;
p1 = p1 -> next;
}

while(p2 != NULL)
{
p3 -> next = new pnode;
p3 = p3 -> next;
P3 -> next = NULL;
p3 -> coeff = p2 -> coeff;
p3 -> expo = p2 -> expo;
p2 = p2 -> next;
}
return (head3);
}
 Generalized Linked List
• Definition: A generalized linked list A, is defined as a finite
sequence n>=0 elements a1 , a2 , …....,an such that ai elements
are either atoms or list of atoms.

• Thus A = ( a1 , a2 , a3….........., an )
where n is total no .of nodes in the list

• Representation of node:

Flag Data/ Down Ponter Next pointer

• Flag 0 means data (atom) exist

• Flag 1 means down pointer exist
• Down pointer exists when list of atoms exist.
• Next pointer points to next node (atom)
 Generalized Linked List
• Example1: (a, (b, c), d)

0 a 1 0 d

0 b 0 c
 Generalized Linked List
Example2: G = (p, q, (r, s, (t, u, v), w), x, y)

0 p 0 q 1 0 x 0 y

0 r 0 s 1 0 w

0 t 0 u 0 v
 Generalized Linked List
Example3: G = ((a, b, c), d, (e, f), g)

1 0 d 1 0 g

0 e 0 f

0 a 0 b 0 c

Example4 for Practice: (L,(M, (N, (O, P)), Q), R, (S, T), (A, (B, C)))
Representation of Polynomial using GLL
Example1: 4x6 + 8x2 + 3x + 7 single variable polynomial

x - 6 4 2 8 1 3 0 7

Polynomial of x

Example2: 3y9 - 6y7 + 2y3 - 4 single variable polynomial

y - 9 3 7 -6 3 2 0 -4

Polynomial of y
 Representation of Polynomial using GLL
Example3: y3(5x2+ 9x) + y(5x + 6) + (9x3 + 7) Two variable polynomial

y - 3 1 0

(5x2+ 9x) (5x + 6) (9x3 + 7)

Polynomial of y
 Representation of Polynomial using GLL
y - 3 1 0

(5x2+ 9x) (5x + 6) (9x3 + 7)

Polynomial of y

y - 3 1 0

x - 3 9 0 7

x - 1 5 0 6

x - 2 5 1 9
Representation of Polynomial using GLL
Example4: x10y3z2 + 2x8y3z2 + 3x8y2z2 +x4y4z + 6x3y4z + 2yz
Re-writing the above polynomial we get
= z2(x10y3+ 2x8y3 + 3x8y2 ) + z(x4y4 + 6x3y4 + 2y)

= z2[y3(x10+ 2x8 )+ 3x8y2)] + z[y4(x4 + 6x3) + 2y]

z - 2 1

y3(x10+ 2x8 )+ 3x8y2) y4(x4 + 6x3) + 2y

Representation of Polynomial using GLL
z - 2 1

y3(x10+ 2x8 )+ 3x8y2) y4(x4 + 6x3) + 2y

z - 2 1

y - 4 1

x4+ 6x3 2

y - 3 2

x10+ 2x8 3x8

 Representation of Polynomial using GLL

z - 2 1

y - 4 1

x - 0 2

x - 4 1 3 6

y - 3 2

x - 8 3

x - 10 1 8 2
 Representation of Polynomial using GLL
Example4: P(a,b,c)= a10b3c2 + 6a8b3c2 + 5a8b2c2 +2a4b4c + 2a3b4c + 8bc

Re-writing the above polynomial we get

= c2(a10b3+ 6a8b3 + 5a8b2 ) + c(a4b4 + 2a3b4 + 8b)

= c2[b3(a10+ 6a8 )+ 3a8b2] + c[b4(a4 + 2a3) + 8b]

c - 2 1

b3(a10+ 6a8 )+ 3a8b2 b4(a4 + 2a3) + 8b

Representation of Polynomial using GLL
c - 2 1

b3(a10+ 6a8 )+ 3a8b2 b4(a4 + 2a3) + 8b

c - 2 1

b - 4 1

a4+2a3 8

b - 3 2

a10+ 6a8 3a8

 Representation of Polynomial using GLL

c - 2 1

b - 4 1

a - 0 8

a - 4 1 3 2

b - 3 2

a - 8 3

a - 10 1 8 6
 Representation of Polynomial using GLL
Example5: 3x4y3 + 5x3y3 + 7xy3 +3x4y6 + 5x3y6+ 7xy6 + 6xy

Re-writing the above polynomial we get

= y6( 3x4 + 5x3 +7x) + y3( 3x4 + 5x3 + 7x ) + 6xy

y - 6 3 1

3x4 + 5x3 +7x 3x4 + 5x3 + 7x 6x

Representation of Polynomial using GLL
y - 6 3 1

3x4 + 5x3 +7x 3x4 + 5x3 + 7x 6x

y - 6 3 1

x - 1 6

x - 4 3 3 5 1 7

x - 4 3 3 5 1 7
 Case study: Garbage collection
• If some object is created and which is not been in use since long
time, then such an object is called garbage

• The garbage collection is a technique in which all such garbage is

collected and removed.

• The garbage collector cleans up the heap memory so that the

memory occupied by unused objected can be freed and can
be allocated to new objects

• Garbage collection algo works in 2 steps:

1. Mark: All the unused objects are located and marked them for
deletion.
2. Sweep: All marked objects are swept, and memory get freed

• Advantages:
1. Manual memory management by programmer is time consuming
and error prone. So this automatic memory management is useful
2. Reusability