Data Structures

Lecture 5: Linked List Operations

By
Ravi Kant Sahu
Asst. Professor

Lovely Professional University, Punjab

 Outlines
• Introduction
• Memory Allocation & Garbage Collection
• Overflow and Underflow
• Traversing a Linked List
• Searching a Linked List
• Review Questions

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
Ravi Kant Sahu, Asst. Professor @ Lovely
Professional University, Punjab (India)
 Memory Allocation
• Together with the linked list, a special list is maintained
which consists of unused memory cells.

• This list has its own pointer.

• This list is called List of available space or Free-storage

list or Free pool.

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
 Free Pool
• Linked list with free pool or list of Available space.

INFO LINK
START 1 0
2
2 A 6
3 E 9
AVAIL 4 10 C 7
5 8
6 B 4
7 D 3
8 1
9 F 0

10 5

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
 Free Pool
• It is a list of free nodes in the memory. It contains unused
memory cells and these memory cells can be used in future. It
is also known as ‘List of Available Space’ or ‘Free Storage List’
or ‘Free Pool’. 
• It is used along with linked list. Whenever a new node is to be
inserted in the linked list, a free node is taken from the AVAIL
List and is inserted in the linked list. Similarly, whenever a node
is deleted from the linked list, it is inserted in the AVAIL List. So
that it can be used in future.

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
 Free Pool
• It is a list of free nodes in the memory. It contains unused
memory cells and these memory cells can be used in future. It
is also known as ‘List of Available Space’ or ‘Free Storage List’
or ‘Free Pool’. 
• It is used along with linked list. Whenever a new node is to be
inserted in the linked list, a free node is taken from the AVAIL
List and is inserted in the linked list. Similarly, whenever a node
is deleted from the linked list, it is inserted in the AVAIL List. So
that it can be used in future.

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
 Free Pool

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
 Garbage Collection
• Garbage collection is a technique of collecting all the
deleted spaces or unused spaces in memory.

• The OS of a computer may periodically collect all the

deleted space onto the free-storage list.

• Garbage collection may take place when there is only

some minimum amount of space or no space is left in free
storage list.

• Garbage collection is invisible to the programmer.

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
Ravi Kant Sahu, Asst. Professor @ Lovely
Professional University, Punjab (India)
Ravi Kant Sahu, Asst. Professor @ Lovely
Professional University, Punjab (India)
Garbage Collection

Ravi Kant Sahu, Asst. Professor @ Lovely

Professional University, Punjab (India)
 Garbage Collection Process
• Garbage collection takes place in two steps.

1. The computer runs through all lists tagging those cells

which are currently in use.

2. Then computer runs through the memory, collecting all

the untagged spaces onto the free storage list.

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
 Overflow and Underflow
 Overflow: When a new data are to be inserted into a data
structure but there is no available space i.e. the free storage
list is empty.

• Overflow occurs when AVAIL = NULL, and we want insert

an element.

• Overflow can be handled by printing the ‘OVERFLOW’

message and/or by adding space to the underlying data
structure. By deleting the existing data.

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
 Overflow and Underflow
 Underflow: When a data item is to be deleted from an
empty data structure.

• Underflow occurs when START = NULL, and we want to

delete an element.

• Underflow can be handled by printing the ‘UNDERFLOW’

message.

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
 Traversing a Linked List
• PTR is a pointer variable which points to the node currently
being processed.
• LINK [PTR] points to the next node to be processed.

 Algorithm (Traversing a linked list)

1. Set PTR = START. [Initialize pointer PTR]

2. Repeat step 3 and 4 while PTR ≠ NULL.
3. Apply PROCESS to INFO[PTR].
4. Set PTR = LINK [PTR]. [PTR points to next node]
[End of Step 2 Loop.]
5. EXIT
Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
 Problems
• Write an algorithm to modify each element of an integer
linked list such that
(a) each element is double of its original value.
(b) each element is sum of its original value and its previous element.

• Write an algorithm to find out the maximum and minimum

data element from an integer linked list.

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
 Searching a Linked List

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
 Searching a Linked List (1)
 List is Unsorted
SEARCH (INFO, LINK, START, ITEM, LOC)
1. Set PTR = START, LOC=NULL.
2. Repeat Step 3 While PTR ≠ NULL.
3. If ITEM == INFO [PTR], then:
Set LOC = PTR, and EXIT.
Else:
Set PTR = LINK [PTR]. [PTR points to next node]
[End of if Structure.]
[End of step 2 Loop.]
4. IF LOC = NULL, Then Print “ITEM not Found” [Search is
Unsuccessful.]
5. Exit . [Return LOC and Exit.]

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
 Searching a Linked List (2)
 List is Sorted
SEARCH (INFO, LINK, START, ITEM, LOC)
1. Set PTR = START.
2. Repeat Step 3 While PTR ≠ NULL.
3. If ITEM > INFO [PTR], then:
PTR = LINK [PTR]. [PTR points to next node]
Else if ITEM = INFO [PTR], then:
Set LOC = PTR, and EXIT. [Search is successful.]
Else:
Set LOC = NULL, and EXIT. [ITEM exceeds INFO[PTR]…]
[End of if Structure.]
[End of step 2 Loop.]
4. Return LOC .
5. Exit.
Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
 Review Questions
• Write an algorithm to find out the maximum and minimum
data element from an integer linked list.

• What is the condition of Overflow and underflow?

• What are the steps followed during garbage collection?

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
 MCQ
• The situation when in a linked list AVAIL=NULL
is
• a. underflow
• b. overflow
• c. housefull
• d. saturated

Ravi Kant Sahu, Asst. Professor @ Lovely

Professional University, Punjab (India)
 MCQ
• Which data structure allows deleting data
elements from front and inserting at rear?
• a. Stacks
• b. Queues
• c. Deques
• d. Binary search tree

Ravi Kant Sahu, Asst. Professor @ Lovely

Professional University, Punjab (India)
 MCQ
• In a circular linked list

• a) Components are all linked together in some

sequential manner.
• b) There is no beginning and no end.
• c) Components are arranged hierarchically.
• d) Forward and backward traversal within the
list is permitted.
Ravi Kant Sahu, Asst. Professor @ Lovely
Professional University, Punjab (India)
• Which of the following correctly declares an
array?
• A. int array[10];
• B. int array;
• C. array{10};
• D. array array[10];

Ravi Kant Sahu, Asst. Professor @ Lovely

Professional University, Punjab (India)
• which of the following is used to terminate the
function declaration?

• A. :
• B. )
• C. ;
• D. none of the mentioned

Ravi Kant Sahu, Asst. Professor @ Lovely

Professional University, Punjab (India)
• Which is more effective while calling the
functions?
• A. call by value
• B. call by reference
• C. call by pointer
• D. none of the mentioned

Ravi Kant Sahu, Asst. Professor @ Lovely

Professional University, Punjab (India)
Ravi Kant Sahu, Asst. Professor @ Lovely
Professional University, Punjab (India)