Data Structures and Algorithms

Objectives

In this chapter, you will learn to:

Implement a doubly-linked list
Implement a circular linked list
Apply linked lists to solve programming problems

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List

Now consider
Consider a sorted
a caselist in
of which
100000you
numbers
need tostored
displayinthese
a linked
list.
numbers in a descending order.
If youwill
How wantyoutosolve
display thisthese
problem?
numbers in ascending order,
what will node
Each you do?
is linked to the next node in sequence.
Traverse
This meansthethat
list starting
you canfrom the first
traverse node.
the list in the forward
direction only.
Such a linked list is called a singly-linked list.
To display the numbers in the descending order, you need to
reverse the linked list.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.
Algorithm to reverse a
2. If there is only one node in the list:
singly-linked list.
a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

6. Make the next field of ptr1 point to NULL.

7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

6. Make the next field of ptr1 point to NULL.

7. Make the next field of ptr2 point to ptr1.

ptr1 ptr2 ptr3
8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

6. Make the next field of ptr1 point to NULL.

7. Make the next field of ptr2 point to ptr1.

ptr1 ptr2 ptr3
8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr1 6. Make the next field of ptr1 point to NULL.

7. Make the next field of ptr2 point to ptr1.

ptr1 ptr2 ptr3
8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr1 ptr2 6. Make the next field of ptr1 point to NULL.

7. Make the next field of ptr2 point to ptr1.

ptr2 ptr3
8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr1 ptr2 ptr3 6. Make the next field of ptr1 point to NULL.

7. Make the next field of ptr2 point to ptr1.

ptr3
8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr1 ptr2 ptr3 6. Make the next field of ptr1 point to NULL.

7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr1 ptr2 ptr3 6. Make the next field of ptr1 point to NULL.

7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr1 ptr2 ptr3 6. Make the next field of ptr1 point to NULL.

7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr1 ptr2 ptr3 6. Make the next field of ptr1 point to NULL.
ptr1
7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr2 ptr3 6. Make the next field of ptr1 point to NULL.
ptr1 ptr2
7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr3 ptr3 6. Make the next field of ptr1 point to NULL.
ptr1 ptr2
7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr3 6. Make the next field of ptr1 point to NULL.
ptr1 ptr2
7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr1 ptr3 6. Make the next field of ptr1 point to NULL.
ptr1 ptr2
7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr1 ptr3 6. Make the next field of ptr1 point to NULL.
ptr2 ptr2
7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr1 ptr3 ptr3 6. Make the next field of ptr1 point to NULL.
ptr2
7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr1 ptr3 6. Make the next field of ptr1 point to NULL.
ptr2
7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr1 ptr1 ptr3 6. Make the next field of ptr1 point to NULL.
ptr2
7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr1 ptr3 6. Make the next field of ptr1 point to NULL.
ptr2 ptr2
7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

a. Set ptr1 = ptr2

b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr1 ptr3 6. Make the next field of ptr1 point to NULL.
ptr2
7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

ptr3 = NULL
a. Set ptr1 = ptr2
b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr1 6. Make the next field of ptr1 point to NULL.
ptr2
7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

ptr3 = NULL
a. Set ptr1 = ptr2
b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

1. Declare three variables / pointers ptr1,

ptr2, and ptr 3.

2. If there is only one node in the list:

START
a. Exit.
START
3. Mark the first node in the list as ptr1.

10 15 19 21 32 4. Mark the successor of ptr1 as ptr2

5. Mark the successor of ptr2 as ptr3.

ptr1 6. Make the next field of ptr1 point to NULL.
ptr2
7. Make the next field of ptr2 point to ptr1.

8. Repeat until ptr3 becomes NULL

ptr3 = NULL
a. Set ptr1 = ptr2
b. Set ptr2 = ptr3
c. Make ptr3 point to the next node
in its sequence.
d. Make the next field of ptr2 point to
ptr1.

9. Make START point to ptr2.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

Whatcan
How is the
youproblem withproblem?
solve this the previous algorithm?
You need
This to adjust
problem can be the links for
solved all the
if each three
node variables
in the list holds the
whenever of
reference you
itsvisit the next
preceding node.
node in addition to its next node in
sequence.
Disadvantage of this approach:
Consider the following
This approach list: and time consuming for large lists.
is inefficient

START

10 15 19 21 23 25 32

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Doubly-Linked List (Contd.)

You can introduce an additional field in each node of a

singly-linked list, which would hold the address of its
previous node.
Such a type of list is known as a doubly-linked list.

START

10 15 19 21 23 25 32

Structure of a doubly-linked list

Ver. 1.0 Session 8

Data Structures and Algorithms
Representing a Doubly-Linked List

A Linked list is represented in a program by defining two

classes:
Node class: In a doubly-linked list, each node needs to store:
The information
The address of the next node in sequence
The address of the previous node

// Code in C#
class Node
{
public int info;
public Node next;
public Node prev;
}

Ver. 1.0 Session 8

Data Structures and Algorithms
Representing a Doubly-Linked List (Contd.)

// Code in C++
class Node
{
public:
int info;
Node * next;
Node * prev;
};

Ver. 1.0 Session 8

Data Structures and Algorithms
Representing a Doubly-Linked List (Contd.)

DoubleLinkedList class: This class consists of a set of

operations implemented on a linked list. In addition, it declares
a variable/pointer, START, which will always point to the first
node in the list.
// Code in C#
class DoubleLinkedList
{
Node START;
DoubleLinkedList(){}
public void addNode(int element){}
public bool search(int element, ref Node previous,
ref Node current){}
public bool delNode(int element){}
public void traverse() {}
public void revtraverse(){}
}

Ver. 1.0 Session 8

Data Structures and Algorithms
Representing a Doubly-Linked List (Contd.)

// Code in C++
class DoubleLinkedList
{
Node *START;
public:
DoubleLinkedList();
void addNode(int element);
bool search(int element, Node *previous, Node
*current);
bool delNode(int element);
void traverse();
void revtraverse();
};

Ver. 1.0 Session 8

Data Structures and Algorithms
Just a minute

How does the representation of a node in a doubly-linked

list differ from that of a singly-linked list?

Answer:
Unlike singly-linked list, in which each node stores the address
of only the next node in the list, each node in a doubly-linked
list holds the address of its previous node also.

Ver. 1.0 Session 8

Data Structures and Algorithms
Traversing a Doubly-Linked List
1. Mark the first node in the list as
currentNode.
Write an algorithm
Algorithm to traverse
to traverse a doubly a doubly linked list in the
2. Repeat steps 3 and 4 until
forwardlist
linked direction.
in the forward direction. currentNode becomes NULL.

3. Display the information

contained in the node marked as
currentNode.

4. Make currentNode point to the

next node in sequence.

Ver. 1.0 Session 8

Data Structures and Algorithms
Traversing a Doubly-Linked List (Contd.)

1. Mark the last node in the list as

Write an algorithm
Algorithm to traverse
to traverse a doubly a doubly linked list in the
currentNode.

backward
linked direction.
list in the backward 2. Repeat steps 3 and 4 until
currentNode becomes NULL.
direction.
3. Display the information
contained in the node marked as
currentNode.

4. Make currentNode point to the

node preceding it.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting Nodes in a Doubly-Linked List

A node can be inserted at any of the following positions in a

doubly-linked list:
Beginning of the list
Between two nodes in the list
End of the list

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the Beginning of the List

Write an algorithm to insert a node in the beginning of a

doubly-linked list.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the Beginning of the List (Contd.)
1. Allocate memory for the new
node.
Algorithm to insert a node in the
2. Assign value to the data field of
beginning of a doubly-linked list. the new node.

3. Make the next field of the new

node point to the first node in the
list.

4. Make the prev field of START

point to the new node.

5. Make the prev field of the new

node point to NULL.

START 6. Make START, point to the new

node.

10 15 17 20

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the Beginning of the List (Contd.)
1. Allocate memory for the new
node.

2. Assign value to the data field of

the new node.

3. Make the next field of the new

node point to the first node in the
list.

4. Make the prev field of START

point to the new node.

newnode 5. Make the prev field of the new

node point to NULL.

START 6. Make START, point to the new

node.

10
10 15 17 20

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the Beginning of the List (Contd.)
1. Allocate memory for the new
node.

2. Assign value to the data field of

the new node.

3. Make the next field of the new

node point to the first node in the
list.

4. Make the prev field of START

point to the new node.

newnode 5. Make the prev field of the new

node point to NULL.

START 6. Make START, point to the new

7 node.

10
10 15 17 20

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the Beginning of the List (Contd.)
1. Allocate memory for the new
node.
[Link] = START
2. Assign value to the data field of
the new node.

3. Make the next field of the new

node point to the first node in the
list.

4. Make the prev field of START

point to the new node.

newnode 5. Make the prev field of the new

node point to NULL.

START 6. Make START, point to the new

7 node.

10
10 15 17 20

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the Beginning of the List (Contd.)
1. Allocate memory for the new
node.
[Link] = START
2. Assign value to the data field of
[Link] = newnode the new node.

3. Make the next field of the new

node point to the first node in the
list.

4. Make the prev field of START

point to the new node.

newnode 5. Make the prev field of the new

node point to NULL.

START 6. Make START, point to the new

7 node.

10
10 15 17 20

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the Beginning of the List (Contd.)
1. Allocate memory for the new
node.
[Link] = START
2. Assign value to the data field of
[Link] = newnode the new node.

[Link] = NULL 3. Make the next field of the new

node point to the first node in the
list.

4. Make the prev field of START

point to the new node.

newnode 5. Make the prev field of the new

node point to NULL.

START 6. Make START, point to the new

7 node.

10
10 15 17 20

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the Beginning of the List (Contd.)
1. Allocate memory for the new
node.
[Link] = START
2. Assign value to the data field of
[Link] = newnode the new node.

[Link] = NULL 3. Make the next field of the new

node point to the first node in the
START = newnode list.

4. Make the prev field of START

point to the new node.

newnode 5. Make the prev field of the new

node point to NULL.

START 6. Make START, point to the new

7 node.

10
10 15 17 20

Insertion complete

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List

Write an algorithm to insert a node between two nodes in a

doubly-linked list.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert
Algorithm
16 to insert a node between locate previous and current, execute the
following steps:
two nodes in a doubly-linked list. a. Make current point to the first
node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
point to current.
5. Make the prev field of the new node
point to previous.
6. Make the prev field of current point to
the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 16 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
point to current.
5. Make the prev field of the new node
point to previous.
6. Make the prev field of current point to
the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 16 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
current node.
4. Make the next field of the new node
point to current.
5. Make the prev field of the new node
point to previous.
6. Make the prev field of current point to
the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 16 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
current node.
4. Make the next field of the new node
previous = NULL point to current.
5. Make the prev field of the new node
point to previous.
6. Make the prev field of current point to
the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 16 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
current node.
4. Make the next field of the new node
previous = NULL point to current.
5. Make the prev field of the new node
point to previous.
6. Make the prev field of current point to
the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 16 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
previous current node.
4. Make the next field of the new node
previous = NULL point to current.
5. Make the prev field of the new node
point to previous.
6. Make the prev field of current point to
the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 16 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
previous current current node.
4. Make the next field of the new node
point to current.
5. Make the prev field of the new node
point to previous.
6. Make the prev field of current point to
the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 16 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
previous current node.
4. Make the next field of the new node
point to current.
5. Make the prev field of the new node
point to previous.
6. Make the prev field of current point to
the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 16 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
previous previous current node.
4. Make the next field of the new node
point to current.
5. Make the prev field of the new node
point to previous.
6. Make the prev field of current point to
the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 16 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
previous currentcurrent node.
4. Make the next field of the new node
point to current.
5. Make the prev field of the new node
point to previous.
6. Make the prev field of current point to
the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 16 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
previous current node.
4. Make the next field of the new node
point to current.
5. Make the prev field of the new node
point to previous.
6. Make the prev field of current point to
the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 16 newnode locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
previous current node.
4. Make the next field of the new node
point to current.
5. Make the prev field of the new node
point to previous.
6. Make the prev field of current point to
the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 16 newnode locate previous and current, execute the
following steps:
a. Make current point to the first
16 node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
previous current node.
4. Make the next field of the new node
point to current.
5. Make the prev field of the new node
point to previous.
6. Make the prev field of current point to
the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
newnode locate previous and current, execute the
following steps:
a. Make current point to the first
16 node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
previous current node.
4. Make the next field of the new node
point to current.
[Link] = current 5. Make the prev field of the new node
point to previous.
6. Make the prev field of current point to
the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
newnode locate previous and current, execute the
following steps:
a. Make current point to the first
16 node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
previous current node.
4. Make the next field of the new node
point to current.
[Link] = current 5. Make the prev field of the new node
point to previous.
[Link] = previous 6. Make the prev field of current point to
the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
newnode locate previous and current, execute the
following steps:
a. Make current point to the first
16 node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
previous current node.
4. Make the next field of the new node
point to current.
[Link] = current 5. Make the prev field of the new node
point to previous.
[Link] = previous 6. Make the prev field of current point to
the new node.
[Link] = newnode 7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
Insertion complete new node is to be inserted. Mark them
as previous and current respectively. To
newnode locate previous and current, execute the
following steps:
a. Make current point to the first
16 node.
b. Make previous point to NULL.
START c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
10
10 15 17 20 e. Make current point to the next
node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new
previous current node.
4. Make the next field of the new node
point to current.
[Link] = current 5. Make the prev field of the new node
point to previous.
[Link] = previous 6. Make the prev field of current point to
the new node.
[Link] = newnode 7. Make the next field of previous point to
[Link] = newnode the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
What is the problem with this locate previous and current, execute the
following steps:
algorithm? a. Make current point to the first
node.
If current is NULL, then the new b. Make previous point to NULL.
node should be inserted at the c. Repeat steps d and e until
[Link] > [Link] or
end of the list. current = NULL.
However, in this case, step 6 will d. Make previous point to current.
e. Make current point to the next
give an error. node in sequence.
2. Allocate memory for the new node.
This is because, NULL cannot 3. Assign value to the data field of the new
have a prev field. node.
4. Make the next field of the new node
Therefore, you need to modify point to current.
5. Make the prev field of the new node
this algorithm so that you can point to previous.
also insert a node at the end of 6. Make the prev field of current point to
the new node.
the list. 7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert
Refer
23 to the modified algorithm locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
point to the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 23 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
point to the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 23 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
current point to the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 23 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
current point to the new node.
7. Make the next field of previous point to
previous = NULL the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 23 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps e and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
current point to the new node.
7. Make the next field of previous point to
previous = NULL the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 23 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous current point to the new node.
7. Make the next field of previous point to
previous = NULL the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 23 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous current current point to the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 23 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous current point to the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 23 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous previous current point to the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 23 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous current current point to the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 23 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous current point to the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 23 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous previous current point to the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 23 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous current current point to the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 23 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous current point to the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 23 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous previous current point to the new node.
7. Make the next field of previous point to
the new node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
Insert 23 locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous current point to the new node.
7. Make the next field of previous point to
the new node.

current = NULL

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
newnode current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous point to the new node.
7. Make the next field of previous point to
the new node.

current = NULL

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
newnode current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 23 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous point to the new node.
7. Make the next field of previous point to
the new node.

current = NULL

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
[Link] = current locate previous and current, execute the
following steps:
a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
newnode current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 23 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous point to the new node.
7. Make the next field of previous point to
the new node.

current = NULL

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
[Link] = current locate previous and current, execute the
following steps:
[Link] = previous a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
newnode current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 23 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous point to the new node.
7. Make the next field of previous point to
the new node.

current = NULL

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
[Link] = current locate previous and current, execute the
following steps:
[Link] = previous a. Make current point to the first
node.
b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
newnode current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 23 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous point to the new node.
7. Make the next field of previous point to
the new node.

current = NULL

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Identify the nodes between which the
new node is to be inserted. Mark them
as previous and current respectively. To
[Link] = current locate previous and current, execute the
following steps:
[Link] = previous a. Make current point to the first
node.
[Link] = newnode b. Make previous point to NULL.
c. Repeat steps d and e until
[Link] > [Link] or
newnode current = NULL.
d. Make previous point to current.
e. Make current point to the next
node in sequence.
START 23 2. Allocate memory for the new node.
3. Assign value to the data field of the new
node.
4. Make the next field of the new node
10 15 17 20 point to current.
10 5. Make the prev field of the new node
point to previous.
6. If current is not NULL:
a. Make the prev field of current
previous point to the new node.
Insertion complete 7. Make the next field of previous point to
the new node.

current = NULL

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the end of the List
1. Allocate memory for the new node.

2. Assign value to the data field of the new

Write an algorithm
Algorithm to insert a tonode
insertatathe
node at the end of a
node.

doubly-linked
end list that contains
of a doubly-linked list a variable,
3. MakeLAST, to ofkeep
the next field the node marked
track of the last node of the list. as LAST point to the new node.

4. Make the prev field of new node point to

node marked LAST.

5. Make the next field of the new node

point to NULL.

6. Mark the new node as LAST.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting Nodes from a Doubly-Linked List

You can delete a node from one of the following places in a

doubly-linked list:
Beginning of the list
Between two nodes in the list
End of the list

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the Beginning of the List

Write an algorithm to delete a node from the beginning of a

doubly-linked list.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the Beginning of the List (Contd.)

1. Mark the first node in the list as

current.
Algorithm to delete a node from the
2. Make START point to the next
beginning of a doubly-linked list. node in sequence.

3. If START is not NULL: /* If the

node to be deleted is not the
only node in the list */
START
a. Assign NULL to the prev
field of the node marked
as START.
10 15 17 20 4. Release the memory of the node
marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the Beginning of the List (Contd.)

1. Mark the first node in the list as

current.

2. Make START point to the next

node in sequence.

3. If START is not NULL: /* If the

node to be deleted is not the
only node in the list */
START
a. Assign NULL to the prev
field of the node marked
as START.
10
10 15 17 20 4. Release the memory of the node
marked as current.

current

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the Beginning of the List (Contd.)

1. Mark the first node in the list as

current.

2. Make START point to the next

node in sequence.

3. If START is not NULL: /* If the

node to be deleted is not the
only node in the list */
START START
a. Assign NULL to the prev
field of the node marked
as START.
10
10 15 17 20 4. Release the memory of the node
marked as current.

current

START = [Link]

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the Beginning of the List (Contd.)

1. Mark the first node in the list as

current.

2. Make START point to the next

node in sequence.

3. If START is not NULL: /* If the

node to be deleted is not the
only node in the list */
START
a. Assign NULL to the prev
field of the node marked
as START.
10
10 15 17 20 4. Release the memory of the node
marked as current.

current

START = [Link]
START. prev = NULL

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the Beginning of the List (Contd.)

1. Mark the first node in the list as

Delete operation complete current.

2. Make START point to the next

node in sequence.

3. If START is not NULL: /* If the

node to be deleted is not the
only node in the list */
START
a. Assign NULL to the prev
field of the node marked
as START.
10 15 17 20 4. Release the memory of the node
marked as current.

current
Memory released
START = [Link]
START. prev = NULL

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List

Write an algorithm to delete a node after any other node in a

doubly-linked list.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)
1. Mark the node to be deleted as current
and its predecessor as previous. To
locate previous and current, execute
Algorithm
Delete 17 to delete a node between the following steps:
two nodes in a doubly-linked list. a. Make previous point to NULL.
// Set previous = NULL

START b. Make current point to the first

node in the linked list. // Set
current = START

10 15 17 20 c. Repeat steps d and e until either

the node is found or current
becomes NULL.

d. Make previous point to current.

e. Make current point to the next

node in sequence.

2. Make the next field of previous point to

the successor of current.

3. Make the prev field of the successor of

current point to previous.

4. Release the memory of the node

marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)
1. Mark the node to be deleted as current
and its predecessor as previous. To
locate previous and current, execute
Delete 17 the following steps:

a. Make previous point to NULL.

// Set previous = NULL

START b. Make current point to the first

node in the linked list. // Set
current = START

10
10 15 17 20 c. Repeat steps d and e until either
the node is found or current
becomes NULL.

d. Make previous point to current.

e. Make current point to the next

node in sequence.

2. Make the next field of previous point to

the successor of current.

3. Make the prev field of the successor of

current point to previous.

4. Release the memory of the node

marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)
1. Mark the node to be deleted as current
and its predecessor as previous. To
locate previous and current, execute
the following steps:

a. Make previous point to NULL.

// Set previous = NULL

START b. Make current point to the first

node in the linked list. // Set
current = START

10 15 17 20 c. Repeat steps d and e until either

the node is found or current
becomes NULL.

d. Make previous point to current.

e. Make current point to the next

previous = NULL node in sequence.

2. Make the next field of previous point to

the successor of current.

3. Make the prev field of the successor of

current point to previous.

4. Release the memory of the node

marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)
1. Mark the node to be deleted as current
and its predecessor as previous. To
locate previous and current, execute
the following steps:

a. Make previous point to NULL.

// Set previous = NULL

START b. Make current point to the first

node in the linked list. // Set
current = START

10
10 15 17 20 c. Repeat steps d and e until either
the node is found or current
becomes NULL.

current d. Make previous point to current.

e. Make current point to the next

previous = NULL node in sequence.

2. Make the next field of previous point to

the successor of current.

3. Make the prev field of the successor of

current point to previous.

4. Release the memory of the node

marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)
1. Mark the node to be deleted as current
and its predecessor as previous. To
locate previous and current, execute
the following steps:

a. Make previous point to NULL.

// Set previous = NULL

START b. Make current point to the first

node in the linked list. // Set
current = START

10
10 15 17 20 c. Repeat steps d and e until either
the node is found or current
becomes NULL.

current d. Make previous point to current.

e. Make current point to the next

previous = NULL node in sequence.

2. Make the next field of previous point to

the successor of current.

3. Make the prev field of the successor of

current point to previous.

4. Release the memory of the node

marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)
1. Mark the node to be deleted as current
and its predecessor as previous. To
locate previous and current, execute
the following steps:

a. Make previous point to NULL.

// Set previous = NULL

START b. Make current point to the first

node in the linked list. // Set
current = START

10
10 15 17 20 c. Repeat steps d and e until either
the node is found or current
becomes NULL.

current d. Make previous point to current.

previous e. Make current point to the next

previous = NULL node in sequence.

2. Make the next field of previous point to

the successor of current.

3. Make the prev field of the successor of

current point to previous.

4. Release the memory of the node

marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)
1. Mark the node to be deleted as current
and its predecessor as previous. To
locate previous and current, execute
the following steps:

a. Make previous point to NULL.

// Set previous = NULL

START b. Make current point to the first

node in the linked list. // Set
current = START

10
10 15 17 20 c. Repeat steps d and e until either
the node is found or current
becomes NULL.

current current d. Make previous point to current.

previous e. Make current point to the next

node in sequence.

2. Make the next field of previous point to

the successor of current.

3. Make the prev field of the successor of

current point to previous.

4. Release the memory of the node

marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)
1. Mark the node to be deleted as current
and its predecessor as previous. To
locate previous and current, execute
the following steps:

a. Make previous point to NULL.

// Set previous = NULL

START b. Make current point to the first

node in the linked list. // Set
current = START

10
10 15 17 20 c. Repeat steps d and e until either
the node is found or current
becomes NULL.

current d. Make previous point to current.

previous previous e. Make current point to the next

node in sequence.

2. Make the next field of previous point to

the successor of current.

3. Make the prev field of the successor of

current point to previous.

4. Release the memory of the node

marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)
1. Mark the node to be deleted as current
and its predecessor as previous. To
locate previous and current, execute
the following steps:

a. Make previous point to NULL.

// Set previous = NULL

START b. Make current point to the first

node in the linked list. // Set
current = START

10
10 15 17 20 c. Repeat steps d and e until either
the node is found or current
becomes NULL.

previous
current current d. Make previous point to current.

previous e. Make current point to the next

node in sequence.

2. Make the next field of previous point to

the successor of current.

3. Make the prev field of the successor of

current point to previous.

4. Release the memory of the node

marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)
1. Mark the node to be deleted as current
and its predecessor as previous. To
locate previous and current, execute
the following steps:

a. Make previous point to NULL.

// Set previous = NULL

START b. Make current point to the first

node in the linked list. // Set
current = START

10
10 15 17 20 c. Repeat steps d and e until either
the node is found or current
becomes NULL.

previous current d. Make previous point to current.

e. Make current point to the next

node in sequence.
previous. next = current. next
2. Make the next field of previous point to
the successor of current.

3. Make the prev field of the successor of

current point to previous.

4. Release the memory of the node

marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)
1. Mark the node to be deleted as current
and its predecessor as previous. To
locate previous and current, execute
the following steps:

a. Make previous point to NULL.

// Set previous = NULL

START b. Make current point to the first

node in the linked list. // Set
current = START

10
10 15 17 20 c. Repeat steps d and e until either
the node is found or current
becomes NULL.

previous current d. Make previous point to current.

e. Make current point to the next

node in sequence.
previous. next = current. next
[Link] = previous 2. Make the next field of previous point to
the successor of current.

3. Make the prev field of the successor of

current point to previous.

4. Release the memory of the node

marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)
1. Mark the node to be deleted as current
and its predecessor as previous. To
locate previous and current, execute
the following steps:
Deletion complete
a. Make previous point to NULL.
// Set previous = NULL

START b. Make current point to the first

node in the linked list. // Set
current = START

10
10 15 17 20 c. Repeat steps d and e until either
the node is found or current
becomes NULL.

previous current d. Make previous point to current.

e. Make current point to the next

node in sequence.
previous. next = current. next
[Link] = previous 2. Make the next field of previous point to
the successor of current.

3. Make the prev field of the successor of

current point to previous.

4. Release the memory of the node

marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)
1. Mark the node to be deleted as current
and its predecessor as previous. To
locate previous and current, execute
What is the problem with this the following steps:

algorithm? a. Make previous point to NULL.

If the last node is to be deleted from the // Set previous = NULL

list, then step 3 will give an error. b. Make current point to the first
This is because, the successor of node in the linked list. // Set
current = START
current is NULL. Therefore, it cannot
have a prev field. c. Repeat steps d and e until either
the node is found or current
In that case, you need to modify the becomes NULL.
algorithm so that the last node can be
deleted from the list by using the same d. Make previous point to current.
algorithm. e. Make current point to the next
node in sequence.

2. Make the next field of previous point to

the successor of current.

3. Make the prev field of the successor of

current point to previous.

4. Release the memory of the node

marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)

1. Mark the node to be deleted as current

and its predecessor as previous.
Refer
Deleteto20the modified algorithm
2. Make the next field of previous point to
the successor of current.

3. If the successor of current exists:

START
a. Make the prev field of the
successor of current point to
previous.
10 15 17 20
4. Release the memory of the node
marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)

1. Mark the node to be deleted as current

and its predecessor as previous.
Delete 20
2. Make the next field of previous point to
the successor of current.

3. If the successor of current exists:

START
a. Make the prev field of the
successor of current point to
previous.
10
10 15 17 20
4. Release the memory of the node
marked as current.

previous current

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)

1. Mark the node to be deleted as current

and its predecessor as previous.

2. Make the next field of previous point to

the successor of current.

3. If the successor of current exists:

START
a. Make the prev field of the
successor of current point to
previous.
10
10 15 17 20
4. Release the memory of the node
marked as current.

previous current

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)

1. Mark the node to be deleted as current

and its predecessor as previous.

2. Make the next field of previous point to

the successor of current.

3. If the successor of current exists:

START
a. Make the prev field of the
successor of current point to
previous.
10
10 15 17 20
4. Release the memory of the node
marked as current.

previous current

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List (Contd.)

1. Mark the node to be deleted as current

and its predecessor as previous.

2. Make the next field of previous point to

the successor of current.

3. If the successor of current exists:

START
a. Make the prev field of the
successor of current point to
previous.
10
10 15 17 20
4. Release the memory of the node
marked as current.

previous current

Delete operation complete

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Circular Linked List

Let us
You cansuppose you are developing
use a singly-linked list. an action game in which
a player isthe
However, given a set ofneed
weapons n weapons.
to be displayed in a sequence
Each weapon
repeatedly in aappears on the
round robin screen after a specific time
manner.
period.
Therefore, once all the weapons have been displayed, the
The player
pointer mustis start
required
againtowith
selectthethe
firstweapon
weaponwithin
in the10 list.
seconds
This or else
requires thethe weapon
pointer to be becomes unusable.
reinitialized each time the
Onceofthe
end th weapon
thenlist is displayed, the weapon that came
is reached.
first
In is displayed
this situation, itagain
wouldandbe the
good process
if aftercontinues.
traversing the node
corresponding to the last weapon, the pointer could
automatically move towill
Which data structure theyou
firstuse
weapon in the
to store the list.
list of
weapons
This can bein this case?
implemented by using a circular linked list.

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Circular Linked List (Contd.)

You can implement a circular linked list by linking the last

node back to the first node in the list.

START

10 15 9 11 23 5 12

Ver. 1.0 Session 8

Data Structures and Algorithms
Implementing a Circular Linked List (Contd.)

In a circular linked list, the last node holds the address of

the first node.

LAST

10 15 9 11 23 5 12

In a circular linked list, you need to maintain a

variable/pointer, LAST, which always point to the last node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Representing a Circular Linked List

To represent a circular linked list, you need to declare two

classes, Node and List:
Node class: The declaration of the Node class of a circular
linked list is the same as that of a singly-linked list.
List class: This class consists of a set of operations
implemented on a linked list. These operations are insertion,
deletion, search, and traversal. It also contains the declaration
of a variable/pointer, LAST, that always points to the last node
in the list.

Ver. 1.0 Session 8

Data Structures and Algorithms
Representing a Circular Linked List (Contd.)

// Code in C#
class List
{
private Node LAST;
List()
{
LAST = NULL;
}
public void addNode(int element) {}
public bool search(int element, ref Node
previous, ref Node current){}
public bool delNode(int element) {}
public void traverse() {}
}

Ver. 1.0 Session 8

Data Structures and Algorithms
Representing a Circular Linked List (Contd.)

// Code in C++
class List
{
Node * LAST;
public:
List()
{
LAST = NULL;
}
void addNode(int element);
bool search(int element, Node *previous, Node
*current);
bool delNode(int element);
void traverse();
};

Ver. 1.0 Session 8

Data Structures and Algorithms
Traversing a Circular Linked List
1. Make currentNode point to
the successor of the node
marked as LAST, such that
Write an algorithm
Algorithm to traverse
to traverse a circularalinked
circular linked list.
currentNode points to the
list. first node in the list.

2. Repeat step 3 and 4 until

currentNode = LAST.

3. Display the information

contained in the node
marked as currentNode.

4. Make currentNode point to

the next node in its
sequence.

5. Display the information

contained in the node
marked as LAST.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node in a Circular Linked List

In a circular linked list, you can insert a node at any of the

following positions:
Beginning of the list
End of the list
Between two node in the list

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the Beginning of the List

Write an algorithm to insert a node in the beginning of a

circular linked list.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the Beginning of the List (Contd.)
1. Allocate memory for the new
node.
Algorithm to insert a node in the 2. Assign value to the data field
beginning of a circular linked list. of the new node.

3. Make the next field of the

new node point to the
successor of LAST.
LAST
4. Make the next field of LAST
point to the new node.

10
10 15 17 20

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the Beginning of the List (Contd.)
1. Allocate memory for the new
node.

2. Assign value to the data field

of the new node.
newnode
3. Make the next field of the
new node point to the
successor of LAST.
LAST
4. Make the next field of LAST
point to the new node.

10
10 15 17 20

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the Beginning of the List (Contd.)
1. Allocate memory for the new
node.

2. Assign value to the data field

of the new node.
newnode
3. Make the next field of the
new node point to the
successor of LAST.
7 LAST
4. Make the next field of LAST
point to the new node.

10
10 15 17 20

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the Beginning of the List (Contd.)
1. Allocate memory for the new
node.

2. Assign value to the data field

of the new node.
newnode
3. Make the next field of the
new node point to the
successor of LAST.
7 LAST
4. Make the next field of LAST
point to the new node.

10
10 15 17 20

newnode. next = LAST. next

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the Beginning of the List (Contd.)
1. Allocate memory for the new
node.

2. Assign value to the data field

of the new node.
newnode
Insertion complete 3. Make the next field of the
new node point to the
successor of LAST.
7 LAST
4. Make the next field of LAST
point to the new node.

10
10 15 17 20

newnode. next = LAST. next

LAST. next =newnode

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List

The algorithm to insert a node between two nodes in

a circular linked list is same as that of a singly-linked
list.
However, the algorithm to search for the nodes
between which the new node is to be inserted is a bit
different in a circular linked list.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Make current point to the first node.

2. Make previous point to NULL.

Algorithm
Insert 16 to locate the nodes
between which the new node is 3. Repeat steps 4 and 5 until [Link] >
[Link] or previous = LAST.
to be inserted.
4. Make previous point to current.

5. Make current point to the next node in

sequence.

LAST

10 15 17 20

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Make current point to the first node.

2. Make previous point to NULL.

3. Repeat steps 4 and 5 until [Link] >

[Link] or previous = LAST.

4. Make previous point to current.

5. Make current point to the next node in

sequence.

LAST

10
10 15 17 20

current

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Make current point to the first node.

2. Make previous point to NULL.

3. Repeat steps 4 and 5 until [Link] >

[Link] or previous = LAST.

4. Make previous point to current.

5. Make current point to the next node in

sequence.

LAST

10
10 15 17 20

current

previous = NULL

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Make current point to the first node.

2. Make previous point to NULL.

3. Repeat steps 4 and 5 until [Link] >

[Link] or previous = LAST.

4. Make previous point to current.

5. Make current point to the next node in

sequence.

LAST

10
10 15 17 20

current

previous = NULL

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Make current point to the first node.

2. Make previous point to NULL.

3. Repeat steps 4 and 5 until [Link] >

[Link] or previous = LAST.

4. Make previous point to current.

5. Make current point to the next node in

sequence.

LAST

10
10 15 17 20

previous current

previous = NULL

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Make current point to the first node.

2. Make previous point to NULL.

3. Repeat steps 4 and 5 until [Link] >

[Link] or previous = LAST.

4. Make previous point to current.

5. Make current point to the next node in

sequence.

LAST

10
10 15 17 20

previous current current

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Make current point to the first node.

2. Make previous point to NULL.

3. Repeat steps 4 and 5 until [Link] >

[Link] or previous = LAST.

4. Make previous point to current.

5. Make current point to the next node in

sequence.

LAST

10
10 15 17 20

previous previous current

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node Between Two Nodes in the List (Contd.)
1. Make current point to the first node.

2. Make previous point to NULL.

3. Repeat steps 4 and 5 until [Link] >

[Link] or previous = LAST.

4. Make previous point to current.

5. Make current point to the next node in

sequence.
Nodes located
LAST

10
10 15 17 20

previous currentcurrent

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the End of the List

Write an algorithm to insert a node at the end of a circular

linked list.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the End of the List (Contd.)
1. Allocate memory for the new
node.
Let us insert
Algorithm a nodea after
to insert nodenode
at the20 2. Assign value to the data field
end of the list of the new node.

3. Make the next field of the

new node point to the
LAST successor of LAST.

4. Make the next field of LAST

point to the new node.
10 15 17 20
5. Mark LAST point to the new
node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the End of the List (Contd.)
1. Allocate memory for the new
node.
Let us insert a node after node 20 2. Assign value to the data field
of the new node.

newnode 3. Make the next field of the

new node point to the
LAST successor of LAST.

4. Make the next field of LAST

point to the new node.
10
10 15 17 20
5. Mark LAST point to the new
node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the End of the List (Contd.)
1. Allocate memory for the new
node.

2. Assign value to the data field

of the new node.

newnode 3. Make the next field of the

new node point to the
LAST successor of LAST.
24 4. Make the next field of LAST
point to the new node.
10
10 15 17 20
5. Mark LAST point to the new
node.

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the End of the List (Contd.)
1. Allocate memory for the new
node.

2. Assign value to the data field

of the new node.

newnode 3. Make the next field of the

new node point to the
LAST successor of LAST.
24 4. Make the next field of LAST
point to the new node.
10
10 15 17 20
5. Mark LAST point to the new
node.

[Link] = LAST. next

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the End of the List (Contd.)
1. Allocate memory for the new
node.

2. Assign value to the data field

of the new node.

newnode 3. Make the next field of the

new node point to the
LAST successor of LAST.
24 4. Make the next field of LAST
point to the new node.
10
10 15 17 20
5. Mark LAST point to the new
node.

[Link] = LAST. next

LAST. next = newnode

Ver. 1.0 Session 8

Data Structures and Algorithms
Inserting a Node at the End of the List (Contd.)
1. Allocate memory for the new
node.
Insertion complete
2. Assign value to the data field
of the new node.

newnode 3. Make the next field of the

new node point to the
LAST successor of LAST.
24 4. Make the next field of LAST
point to the new node.
10
10 15 17 20
5. Mark LAST point to the new
node.

[Link] = LAST. next

LAST. next = newnode
LAST = newnode

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node from a Circular Linked List

You can delete a node from any of the following places in a

circular linked list:
Beginning of the list
End of the list
Between two nodes in the list

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the Beginning of the List

Write an algorithm to delete a node from the beginning of a

circular linked list.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the Beginning of the List (Contd.)
1. If the node to be deleted is
the only node in the list:
// If LAST points to itself
Algorithm for deleting a node from the
beginning of a circular linked list. a. Mark LAST as NULL
b. Exit

2. Make current point to the

successor of LAST
LAST
3. Make the next field of LAST
point to the successor of
current
10 15 17 20 4. Release the memory for the
node marked as current

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the Beginning of the List (Contd.)
1. If the node to be deleted is
the only node in the list:
// If LAST points to itself

a. Mark LAST as NULL

b. Exit

2. Make current point to the

successor of LAST
LAST
3. Make the next field of LAST
point to the successor of
current
10
10 15 17 20 4. Release the memory for the
node marked as current

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the Beginning of the List (Contd.)
1. If the node to be deleted is
the only node in the list:
// If LAST points to itself

a. Mark LAST as NULL

b. Exit

2. Make current point to the

successor of LAST
LAST
3. Make the next field of LAST
point to the successor of
current
10
10 15 17 20 4. Release the memory for the
node marked as current

current

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the Beginning of the List (Contd.)
1. If the node to be deleted is
the only node in the list:
// If LAST points to itself

a. Mark LAST as NULL

b. Exit

2. Make current point to the

successor of LAST
LAST
3. Make the next field of LAST
point to the successor of
current
10
10 15 17 20 4. Release the memory for the
node marked as current

current

LAST. next = [Link]

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the Beginning of the List (Contd.)
1. If the node to be deleted is
the only node in the list:
Deletion Complete // If LAST points to itself

a. Mark LAST as NULL

b. Exit

2. Make current point to the

successor of LAST
LAST
3. Make the next field of LAST
point to the successor of
current
10 15 17 20 4. Release the memory for the
node marked as current

current

LAST. next = [Link]

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List

Delete operation in between two nodes in a circular linked

list is same as that of a singly-linked list.
However, the algorithm to locate the node to be deleted is a
bit different in a circular linked list.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List
1. Make previous point to
the successor of LAST
Delete 17 for locating the node to be
Algorithm 2. Make current point to the
deleted from a circular linked list. successor of LAST

3. Repeat steps 4 and 5

until either the node is
found, or previous =
LAST
LAST
4. Make previous point to
current

10 15 20 5. Make current point to the

17 next node in sequence

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List
1. Make previous point to
the successor of LAST
Delete 17 2. Make current point to the
successor of LAST

3. Repeat steps 4 and 5

until either the node is
found, or previous =
LAST
LAST
4. Make previous point to
current

10 15 20 5. Make current point to the

10 17 next node in sequence

previous

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List
1. Make previous point to
the successor of LAST
Delete 17 2. Make current point to the
successor of LAST

3. Repeat steps 4 and 5

until either the node is
found, or previous =
LAST
LAST
4. Make previous point to
current

10 15 20 5. Make current point to the

10 17 next node in sequence

current previous

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List
1. Make previous point to
the successor of LAST
Delete 17 2. Make current point to the
successor of LAST

3. Repeat steps 4 and 5

until either the node is
found, or previous =
LAST
LAST
4. Make previous point to
current

10 15 20 5. Make current point to the

10 17 next node in sequence

current previous

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List
1. Make previous point to
the successor of LAST
Delete 17 2. Make current point to the
successor of LAST

3. Repeat steps 4 and 5

until either the node is
found, or previous =
LAST
LAST
4. Make previous point to
current

10 15 20 5. Make current point to the

10 17 next node in sequence

current previous

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List
1. Make previous point to
the successor of LAST
Delete 17 2. Make current point to the
successor of LAST

3. Repeat steps 4 and 5

until either the node is
found, or previous =
LAST
LAST
4. Make previous point to
current

10 15 20 5. Make current point to the

10 17 next node in sequence

current previous current

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List
1. Make previous point to
the successor of LAST
Delete 17 2. Make current point to the
successor of LAST

3. Repeat steps 4 and 5

until either the node is
found, or previous =
LAST
LAST
4. Make previous point to
current

10 15 20 5. Make current point to the

10 17 next node in sequence

previous current

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List
1. Make previous point to
the successor of LAST
Delete 17 2. Make current point to the
successor of LAST

3. Repeat steps 4 and 5

until either the node is
found, or previous =
LAST
LAST
4. Make previous point to
current

10 15 20 5. Make current point to the

10 17 next node in sequence

previous current
previous

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node Between Two Nodes in the List
1. Make previous point to
the successor of LAST
Once you locate the node to be 2. Make current point to the
deleted along with its predecessor, successor of LAST

the process of deletion is same as 3. Repeat steps 4 and 5

that of a singly-linked list. until either the node is
found, or previous =
LAST
LAST
4. Make previous point to
current

10 15 20 5. Make current point to the

10 17 next node in sequence

previous current current

Nodes located

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the End of the List

Write an algorithm to delete a node from the end of a

circular linked list.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the End of the List (Contd.)
1. Make current point to LAST.

2. Mark the predecessor of LAST

Let
Algorithm
us perform
for deleting
a deletea operation
node fromonthethe as previous. To locate the
endnode
last of a circular linkedcircular
of the given list. list. predecessor of LAST, execute
the following steps:

LAST a. Make previous point to

the successor of LAST.

b. Repeat step c until the

10 15 17 20 successor of previous
becomes LAST.

c. Make previous point to

the next node in its
sequence.

3. Make the next field of previous

point to the successor of LAST.

4. Mark previous as LAST.

5. Release the memory for the

node marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the End of the List (Contd.)
1. Make current point to LAST.

2. Mark the predecessor of LAST

as previous. To locate the
predecessor of LAST, execute
the following steps:

LAST a. Make previous point to

the successor of LAST.

b. Repeat step c until the

10
10 15 17 20 successor of previous
becomes LAST.

c. Make previous point to

current the next node in its
sequence.

3. Make the next field of previous

point to the successor of LAST.

4. Mark previous as LAST.

5. Release the memory for the

node marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the End of the List (Contd.)
1. Make current point to LAST.

2. Mark the predecessor of LAST

as previous. To locate the
predecessor of LAST, execute
the following steps:

LAST a. Make previous point to

the successor of LAST.

b. Repeat step c until the

10
10 15 17 20 successor of previous
becomes LAST.

c. Make previous point to

previous current the next node in its
sequence.

3. Make the next field of previous

point to the successor of LAST.

4. Mark previous as LAST.

5. Release the memory for the

node marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the End of the List (Contd.)
1. Make current point to LAST.

2. Mark the predecessor of LAST

as previous. To locate the
predecessor of LAST, execute
the following steps:

LAST a. Make previous point to

the successor of LAST.

b. Repeat step c until the

10
10 15 17 20 successor of previous
becomes LAST.

c. Make previous point to

previous current the next node in its
sequence.

3. Make the next field of previous

point to the successor of LAST.

4. Mark previous as LAST.

5. Release the memory for the

node marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the End of the List (Contd.)
1. Make current point to LAST.

2. Mark the predecessor of LAST

as previous. To locate the
predecessor of LAST, execute
the following steps:

LAST a. Make previous point to

the successor of LAST.

b. Repeat step c until the

10
10 15 17 20 successor of previous
becomes LAST.

c. Make previous point to

previous previous current the next node in its
sequence.

3. Make the next field of previous

point to the successor of LAST.

4. Mark previous as LAST.

5. Release the memory for the

node marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the End of the List (Contd.)
1. Make current point to LAST.

2. Mark the predecessor of LAST

as previous. To locate the
predecessor of LAST, execute
the following steps:

LAST a. Make previous point to

the successor of LAST.

b. Repeat step c until the

10
10 15 17 20 successor of previous
becomes LAST.

c. Make previous point to

previous current the next node in its
sequence.

3. Make the next field of previous

point to the successor of LAST.

4. Mark previous as LAST.

5. Release the memory for the

node marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the End of the List (Contd.)
1. Make current point to LAST.

2. Mark the predecessor of LAST

as previous. To locate the
predecessor of LAST, execute
the following steps:

LAST a. Make previous point to

the successor of LAST.

b. Repeat step c until the

10
10 15 17 20 successor of previous
becomes LAST.

c. Make previous point to

previous previous current the next node in its
sequence.

3. Make the next field of previous

point to the successor of LAST.

4. Mark previous as LAST.

5. Release the memory for the

node marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the End of the List (Contd.)
1. Make current point to LAST.

2. Mark the predecessor of LAST

as previous. To locate the
predecessor of LAST, execute
the following steps:

LAST a. Make previous point to

the successor of LAST.

b. Repeat step c until the

10
10 15 17 20 successor of previous
becomes LAST.

c. Make previous point to

previous current the next node in its
sequence.

3. Make the next field of previous

[Link] = [Link] point to the successor of LAST.

4. Mark previous as LAST.

5. Release the memory for the

node marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the End of the List (Contd.)
1. Make current point to LAST.

2. Mark the predecessor of LAST

as previous. To locate the
predecessor of LAST, execute
the following steps:

LAST LAST a. Make previous point to

the successor of LAST.

b. Repeat step c until the

10
10 15 17 20 successor of previous
becomes LAST.

c. Make previous point to

previous current the next node in its
sequence.

3. Make the next field of previous

[Link] = [Link] point to the successor of LAST.

LAST = previous 4. Mark previous as LAST.

5. Release the memory for the

node marked as current.

Ver. 1.0 Session 8

Data Structures and Algorithms
Deleting a Node From the End of the List (Contd.)
1. Make current point to LAST.

2. Mark the predecessor of LAST

as previous. To locate the
predecessor of LAST, execute
the following steps:

LAST a. Make previous point to

Memory released the successor of LAST.

b. Repeat step c until the

10
10 15 17 20 successor of previous
becomes LAST.

c. Make previous point to

previous current the next node in its
sequence.

3. Make the next field of previous

[Link] = [Link] point to the successor of LAST.

LAST = previous 4. Mark previous as LAST.

5. Release the memory for the

node marked as current.
Delete operation complete

Ver. 1.0 Session 8

Data Structures and Algorithms
Applications of Linked Lists

Linked lists provide an efficient mechanism for storing data.

They are used to solve many programming problems easily.
They form the basic foundation for implementing various
other data structures such as stacks, queues, and binary
trees.

Ver. 1.0 Session 8

Data Structures and Algorithms
Gaming Applications

Linked lists are implemented in various gaming applications.

Consider a game in which the player protects himself from the
enemy by firing bullets.
Whenever a bullet is fired, its details (size, color, and
coordinates) need to be stored somewhere.
The details of the bullets are stored in a linked list, because the
total number of bullets to be fired are not known in advance.
The coordinates of the bullets stored in a node are updated on
a regular basis to indicate that the bullet is moving forward.
The same is then rendered on the screen.

Ver. 1.0 Session 8

Data Structures and Algorithms
File System in Operating System

Linked lists are used to implement the internals of a file

system.
A file is divided into blocks, which are scattered randomly on
the disk.
When a new file is created, a new block of memory is
allocated to it.
The new block may not be contiguous to the block that was
earlier allocated.
Therefore, each block also contains the address of the next
allocated block, forming a linked list.

Ver. 1.0 Session 8

Data Structures and Algorithms
Adding Polynomials Using Linked Lists

Linked lists can be used to implement various arithmetic

operations on polynomial expressions.
In the polynomial expression, 4x5 + 5x4 + 2x3 + 3x2 + 7x,
each occurrence of variable x is attached to two values:
Coefficient
Exponent

Ver. 1.0 Session 8

Data Structures and Algorithms
Adding Polynomials Using Linked Lists (Contd.)

Each node holds three pieces of information:

Coefficient
Exponent
Address of the next node in sequence

910 6

coefficient

exponent
address of the next node

Ver. 1.0 Session 8

Data Structures and Algorithms
Adding Polynomials Using Linked Lists (Contd.)

Let us now perform addition of two polynomial expressions.

Polynomial 1: 4x5 + 5x4 + 2x3 + 3x2 + 7x

Polynomial 2: 9x6 + 6x4 + 3x2

Ver. 1.0 Session 8

Data Structures and Algorithms
Adding Polynomials Using Linked Lists (Contd.)

Polynomial 1: 4x5 + 5x4 + 2x3 + 3x2 + 7x

Polynomial 2: 9x6 + 6x4 + 3x2

Read the first node of Polynomial 1 and the first node of

Polynomial 2.
Compare the exponent values of the two nodes.
The node read from Polynomial 2 has a greater exponent
value (6>5).
Add the node with exponent value 6 to the list for
Polynomial 3.
9 10
6

Polynomial 3: 9x6
Ver. 1.0 Session 8
Data Structures and Algorithms
Adding Polynomials Using Linked Lists (Contd.)

Polynomial 1: 4x5 + 5x4 + 2x3 + 3x2 + 7x

Polynomial 2: 9x6 + 6x4 + 3x2

Read the next node from Polynomial 2.

Compare the exponent value of current node of Polynomial
1 with that of Polynomial 2.
The node read from Polynomial 1 has a greater exponent
value (5>4). Therefore, add the node with the exponent
value 5 to the list for Polynomial 3.

9 10
6 4 10
5

Polynomial 3: 9x6 + 4x5

Ver. 1.0 Session 8
Data Structures and Algorithms
Adding Polynomials Using Linked Lists (Contd.)

Polynomial 1: 4x5 + 5x4 + 2x3 + 3x2 + 7x

Polynomial 2: 9x6 + 6x4 + 3x2

Read the next node from Polynomial 1.
Compare the exponent value of the current node of
Polynomial 1 with that of Polynomial 2. Both the exponents
are equal, that is, 4.
Add the coefficients of both the nodes. The resultant node
now has the coefficient value 11 (6+5).
Add the resultant node to the list for Polynomial 3.

9 10
6 4 10
5 11 10
4

Polynomial 3: 9x6 + 4x5 + 11x4

Ver. 1.0 Session 8
Data Structures and Algorithms
Adding Polynomials Using Linked Lists (Contd.)

Polynomial 1: 4x5 + 5x4 + 2x3 + 3x2 + 7x

Polynomial 2: 9x6 + 6x4 + 3x2

Read the next node from both the lists.
Compare the exponent value of the current node of
Polynomial 1 with that of Polynomial 2.
The node read from Polynomial 1 has a greater exponent
value (3>2).
Add the node with the exponent value 3 to the list for
Polynomial 3.
9 10
6 4 10
5 11 10
4 2 10
3

Polynomial 3: 9x6 + 4x5 + 11x4 + 2x3

Ver. 1.0 Session 8
Data Structures and Algorithms
Adding Polynomials Using Linked Lists (Contd.)

Polynomial 1: 4x5 + 5x4 + 2x3 + 3x2 + 7x

Polynomial 2: 9x6 + 6x4 + 3x2

Read the next node from Polynomial 1.
Compare the exponent value of the current node of
Polynomial 1 with that of Polynomial 2. Both the exponents
are equal, that is, 2.
Add the coefficients of both the nodes. The resultant node
now has the coefficient value 6 (3+3).
Add the resultant node to the list for Polynomial 3.

9 10
6 4 10
5 11 10
4 2 10
3 6 10
2

Polynomial 3: 9x6 + 4x5 + 11x4 + 2x3 + 6x2

Ver. 1.0 Session 8
Data Structures and Algorithms
Adding Polynomials Using Linked Lists (Contd.)

Polynomial 1: 4x5 + 5x4 + 2x3 + 3x2 + 7x

Polynomial 2: 9x6 + 6x4 + 3x2

Now there are no more nodes in Polynomial 2.

Therefore, add the remaining nodes of Polynomial 1 to the
resultant list.

9 10
6 4 10
5 11 10
4 2 10
3 6 10
2 7 10
1

Polynomial 3: 9x6 + 4x5 + 11x4 + 2x3 + 6x2 + 7x

Ver. 1.0 Session 8
Data Structures and Algorithms
Summary

In this session, you learned that:

In a doubly-linked list, each node needs to store:
The information.
The address of the next node in the list.
The address of the previous node in the list.
Doubly-linked list enables you to traverse the list in forward as
well as backward direction.
A singly-linked list can be made circular by making the last
node in the list point back to the first node in the list.

Ver. 1.0 Session 8

Data Structures and Algorithms
Summary (Contd.)

Linked lists offer various applications. For example:

They form the basis of various other data structures such as
stacks and queues, and binary trees.
They are used in various gaming applications.
They are used to implement internals of file system internals in
various operating systems.
They offer a simple and convenient mechanism to perform
various arithmetic operations on polynomial expressions.

Ver. 1.0 Session 8