2.

Sorting and Linked list

2.2 Bubble Sort :
Suppose the list of numbers DATA[1], DATA[2], ……., DATA[N] is in
memory.
The bubble sort algorithm works as follows :
Step 1 : Compare DATA1[1] & DATA [2] and arrange them in the
desired order, so that DATA[1] < DATA[2].
- Then compare DATA[2] & DATA[3] and arrange them, so that
DATA[2] < DATA[3].
- Continue this process until we compare DATA[N – 1] with DATA[N]
and arrange them, so that DATA[N – 1] < DATA[N].
- In step 1, there are N – 1 comparisons take place.
- After completing step 1, DATA[N] will contain largest element is
“Bubble up” to the Nth position.
Step 2: Repeat step 1 with one less comparison that means continue
comparison until we compare DATA[N – 2] with DATA[N – 1] and
arrange them so that DATA[N – 2] < DATA[N – 1].
- In step 2, there are N – 2 comparison take place.
- After completing step 2 DATA[N – 1] will contain second largest
element is “Bubble up” to the N-1 position.
|
|
|
Step N – 1: Compare DATA[1] with DATA[2] and arrange them, so
that DATA[1] < DATA[2].
- After N – 1 steps the list will be sorted in ascending order.
- Here during each step the largest element is “bubbled up” to the Nth
position.
- In bubble sort method each of the above step is called “PASS”.

1 / 38
 - Hence to sort a DATA[N] element bubble sort algorithm required N –
1 passes and each pass has N-PASS comparisons.
Ex.: Sort the following list DATA by using bubble sort method and shows
all passes.
42 23 74 11 65 15 10 08
Ans: In bubble sort there are n-1 passes perform i.e 8-1=7 as shown in follows.
Each pass has n-pass comparisons perform.
Circle indicate swapping of two elements
Pass 1: In pass one there are N – 1 comparison are perform as :
i. Compare DATA[1], with DATA[2], since 42 > 23, interchange
them. Hence given list becomes,
23 42 74 11 65 15 10 08

ii. Compare DATA[2] with DATA[3]. Since 42 < 74, a list not alter.
iii. Compare DATA[3] with DATA[4]. Since 74 > 11, interchange them.
Hence given list becomes,
23 42 11 74 65 15 10 08

iv. Compare DATA[4] with DATA[5]. Since 75 > 65, interchange them.
Hence given list becomes,
23 42 11 65 74 15 10 08

v. Compare DATA[5] with DATA[6]. Since 74 > 15 interchange them.

Hence given list becomes,
23 42 11 65 15 74 10 08

vi. Compare DATA[6] with DATA[7]. Since 74 > 10, interchange them.
Hence given list becomes,
23 42 11 65 15 10 74 08

2 / 38
 vii. Compare DATA[7] with DATA[8]. Since 74 > 08, interchange them.
Hence given list becomes,
23 42 11 65 15 10 08 74

After completing first pass the largest number 74 is bubbled up to

the last position i.e 8th, but the remaining numbers are still unsorted.

Pass 2: In Pass 2, there are n-pass i.e 8-2=6 comparisons perform

in following table.

After completing second pass the second largest no. 65 is bubbled up to

the next–to–last position (n – 1) i.e 7th but the remaining numbers are
unsorted.
Pass 3: In Pass 3, there are n-pass i.e 8-3=5 comparisons perform
in following table.

3 / 38
 After completing of pass 3 the third largest no. 42 is bubbled up to the
position (n – 2)i.e. 6th, but the remaining number unsorted.

Pass 4: In Pass 4, there are n-pass i.e 8-4=4 comparisons perform

in following table.

After competing of pass 4 the fourth largest no. 23 is bubbled up

position (n – 3) i.e. 5th ,but the remaining number unsorted.

Pass 5: In Pass 5, there are n-pass i.e 8-5=3 comparisons perform

in following table.

4 / 38
 After completing of pass 5 the fifth largest no. 15 is bubbled up to
position (n – 4) i.e. 4th, but the remaining number unsorted.
Pass 6: In Pass 6, there are n-pass i.e 8-6=2 comparisons perform
in following table.

5 / 38
i. 11 10 08 15 23 42 65 74

6 / 38
 ii. 10 11 08 15 23 42 65 74

10 08 11 15 23 42 65 74

After completing of pass 6 the sixth largest no. 11 is bubbled up to the

position (n – 5) i.e. 3rd. But the remaining number is unsorted.

Pass 7: In Pass 7, there are n-pass i.e 8-7=1 comparisons perform

in following

08 10 11 15 23 42 65 74
After completing of pass 7, list get sorted i.e.,
08 10 11 15 23 42 65 74

Q. Sort the given list by using Bubble Sort Method.

a) 32 51 27 85 66 23 13 57
b) 25 48 37 22 57 86 33 92

An algorithm for Bubbled Sort Method :

Algorithm 2.2 : BUBBLESRT (DATA, N, PASS, PTR, TEMP)

Let DATA is linear array unsorted with N element. PASS, PTR,
TEMP are the local variables used to count the PASS, point
element location and to store value temporary respectively.
7 / 38
 This algorithm perform sort the given list in ascending order.
Step 1: Repeat through step 5
For PASS =1 to N – 1
Step 2: [Initialize pointer PTR]
Set PTR = 1
Step 3: Repeat through step 5
While PTR <= N – PASS
Step 4: [Is element at PTR & PTR + 1 in out of order?]
If (DATA[PTR] > DATA[PTR + 1]), then:
[Interchange (PTR) & DATA(PTR + 1)]
TEMP = DATA[PTR]
DATA[PTR] = DATA [PTR + 1]
DATA[PTR + 1] = TEMP

8 / 38
 [End of if structure]
Step 5: [Increase PTR by 1]
set PTR = PTR + 1
[End of step 3 loop]
[End of step 1 loop]
Step 6 : [Finished] Exit.

• Complexity of Bubbled Sort Method :

- Time require to sort given list in terms of comparison perform in
the algorithm.
- The complexity function F(N) is used to count number of
comparison.
- Here in bubbled sort method, in pass 1 there are N – 1
comparisons are perform and this part place a largest element at
the last position.
- In second pass there are N – 2 comparison perform and it place
the second largest element of the second last position. Repeat the
above process until we execute all passes.
- Hence the number of comparison perform in each pass determine
as,
F(N) = (N – 1) + (N – 2) + .........+ 2 + 1
N(N – 1) N2

= 2 = 2 + 0(N) F(N)
= 0(N2)
- That means time require execute the bubble sort algorithm is
propositional to N2.
- Here N is the number of input elements.

9 / 38
 2.1 Selection Sort Method :
- Suppose linear array list DATA is in memory with N elements
DATA[1], DATA[2], ……., DATA[N].
- A selection sort algorithm works as follow, Pass 1:
- Find the location LOC of the smallest element in the list of N elements
DATA[1], DATA[2], ……, DATA[N] and the DATA[LOC] and
DATA[1].
- Then, DATA[1] is sorted.
Pass 2:
- Find the location LOC of the smallest element form the list of N – 1
elements DATA[2], DATA[3], ……., DATA[N] and then interchange
DATA[LOC] with DATA[2].
- Then DATA[1], DATA[2] are sorted, since DATA[1] < DATA[2]1.
|
|
|
Pass N-1 :
- Find the location of the smallest element from the list of elements
DATA[N – 1], DATA[N].
- Then interchange DATA[LOC ]with DATA[N-1].
- Then DATA[1], DATA[2], ………, DATA[N] is sorted, since DATA[N –
1] <= DATA[N].
- After completing N – 1 passes the list of DATA becomes a sorted list
in ascending ordeR

10 / 38
 Ex.: Sort the given list in ascending order using selection sort method
write all passes.
- Consider unsorted list DATA contains 8 elements as follows,
42 23 74 11 65 12 10 05

Ans: Following table shows selection sort algorithm to DATA .

- Observe that, LOC gives the location of the smallest element among
DATA[PASS], DATA[PASS + 1], ……, DATA[N] during pass … pass.
- The Circle elements indicate the elements which are to be interchange
DATA[LOC] with DATA[PASS].

Pass DATA DATA DATA DATA DATA DATA DATA DATA

(1) (2) (3) (4) (5) (6) (7) (8)
Pass 1,
42 23 74 11 65 12 10 05
loc=8
Pass 2,
05 23 74 11 65 12 10 42
loc=7
Pass 3,
05 10 74 11 65 12 23 42
loc=4
Pass 4,
05 10 11 74 65 12 23 42
loc=6
Pass 5,
05 10 11 12 65 74 23 42
loc=7
Pass 6,
05 10 11 12 23 74 65 42
loc=8
Pass 7,
05 10 11 12 23 41 65 74
loc= 0
Sorted 05 10 11 12 23 41 65 74
List

11 / 38
 • Algorithm for Selection Sort Method :

Procedure 2.1 : MIN (DATA, N, PASS, LOC)

Let DATA is a unsorted list with N element. This procedure
finds the location LOC of the smallest element among
DATA[PASS], DATA[PASS + 1], ........ , DATA[N].
Step 1: [Initialize variable MIN and LOC]
set MIN DATA[PASS] and
LOC PASS
Step 2: Repeat for J PASS + 1 to N
Step 3: If MIN > DATA[J], then
Set MIN = DATA[J] and LOC = J
[End of step loop]
Step 4: Return.

Algorithm 2.1 : SELECTSRT (DATA, N, LOC, TEMP)

Let DATA is a linear array with unsorted element with N
element. LOC sorted location, TEMP is temporary variable.
This algorithm perform selection sort method.
Step 1: Repeat step 2 & 3
For PASS =1 to N – 1
Step 2: Call MIN (DATA, PASS, N, LOC)
Step 3: [Interchange DATA(PASS) and DATA(LOC)]
Set TEMP = DATA[PASS]
DATA[PASS] = DATA[LOC]
DATA[LOC] = TEMP

12 / 38
 [End of step 1 loop]
Step 4: [Finished] Exit.

• Complexity of Selection Sort Method :

- In this algorithm, there are N – 1 comparisons are perform during
pass 1 to find first smallest element, there are N – 2 comparisons
during pass 2. Find the second smallest element and so on.
- Thus the number of comparisons performed during whole method
execution is determine by complexity function F(N) as :
F(N) = (N – 1) + (N – 2) + +2+1
N(N – 1)

i.e. =2 = 0(N2) hence,

F(N) = 0(N2).
- This means that time required execute selection sort algorithm
proportional to N2.

- Here N is a input element.

2.3 :Insertion Sort Method :

- Suppose an array DATA with N elements DATA[1], DATA[2], ....... ,
DATA[N] is in memory.
- The insertion sort algorithm scan DATA from DATA[1] to DATA[N],
inserting each element DATA[PASS] into it’s a proper position in the
previously sorted sub array DATA[1], DATA[2],
… .......... DATA[PASS–1], i.e. :

Pass 1 : DATA[1] by itself is trivially sorted

13 / 38
 Pass 2: DATA[2] is inserted either before or after DATA[1], so that
DATA[1] , DATA[2] is sorted.

Pass 3: DATA[3] is inserted into its proper place in

DATA[1],DATA[2], that is, before DATA[1], between DATA[1] and
DATA[2], or after DATA[2], so that DATA[1] , DATA[2], DATA[3] is
sorted.
|
|
|

Pass N: Insert DATA[N] into its proper place in DATA[1], DATA[2],

…. , DATA[N–1]. So that DATA[1], DATA[2], …. , DATA[N–1]is sorted.
- After completion Pass N list get sorted in ascending order.

Ex.: Sort the given list LA in ascending order by using insertion sort
method and shows all passes.
LA={20,50,70,55,15,10,25}
Ans: Following table shows insertion sort algorithm.
The circle element indicate Pass.
The arrow indicate proper place for element.

14 / 38
Algorithm 2.3 : INSERTIONSRT (DATA, N, PASS, PTR, TEMP)
DATA is a linear array with N unsorted element. PASS variable
is used to shows the passes. PTR is a pointer variable and
TEMP is temporary variable. This algorithm perform insertion
sort method.
Step 1: [Initialize sentinel element]
Set DATA[0] = –
Step 2: Repeat step 3 to 5
For PASS = 2 to N
Step 3: Set TEMP = DATA[PASS] and
PTR = PASS – 1
Step 4: Repeat while (TEMP < DATA[PTR])
(a) DATA[PTR + 1] = DATA[PTR]

15 / 38
 [Moves element Forward]
(b) Set PTR = PTR – 1
[End of step 4 loop]
Step 5: [Insert element in proper place]
Set DATA[PTR + 1] = TEMP
[End of step 2 loop]
Step 6: Return.

• Complexity of Insertion Sort Method :

- The number F(N) of comparisons in the insertion sort algorithm can
be easily computed.
- First of all the worst case occurs when the array DATA is in reverse
order and the linear loop must use the maximum number PASS – 1 of
comparisons.
Hence, F(N) = 1 + 2 + ........... + (N – 1)
N(N – 1)

= 2 = 0(N2)
- Further more, one can show that on the average their will be
approximately comparisons in the linear loop.
- Accordingly for the average case,
N 1

F(N) = + +……….. + 2

–
N(N 1)

= 4

= 0(N2)

2.4 Linked List :-

- A linked list is a linear collection of data elements, called ‘nodes’.
- Here, the linear order is obtained by using pointers.
- A linked as also called as ‘one–way–list’.

16 / 38
- Every node of linked list is get divided into two fields.
1. First field is INFO which is used to store information of the
element.
2. Second field is LINK or next pointer field which is used to store
address of the next node in the list.
- Following figure shows a linked list with four nodes.
START

Next pointer field of second node.

Information field of second node.

Fig. Linked List with 4 nodes.

- It is clear that, in above fig. each node is pictured with two fields.
- The left field use the actual information, and right field use store the
address of the next node.
- Arrows are used to show the order of the nodes.
- The next pointer or LINK field of the last node contain a invalid
address called ‘null pointer’.
- The null pointer (X) is used to shows the end of the list.
- The linked list has also a list pointer variable called START which
contains address of first node in the list.
- The starting address o the list which is sorted in START is used to
traverse the whole linked list.
- Here if the linked list has no any node then such a list is called ‘null
list’ or ‘empty list’. And it is denoted by the null pointer assigning to
START i.e. START = NULL.

17 / 38
2.5 Representation of Linked List in Memory :-

- Suppose list be a linked list for the storage of such a list in memory it
requires linear arrays.
- One is a general array set “INFO”, another pointer array set “LINK”.
- An array INFO[K] will contain the information part and an array
LINK[k] will contain the address of the next element of the list.
- In linked list, a pointer variable START is used to store starting
location of the list. NULL is used to show the end of the list.
- If the subscripts of an array INFO & LINK will be positive integer, then
NULL = 0 used to show end of the linked list.
- Here, the nodes of the linked list doesn’t need occupy the adjacent
dement in the array INFO & LINK.
- Also more than one linked list may be maintain in the same linear
array but only by storing the static address of the second list. Another
pointer variable set START = 1 & so on.
- Ex.: suppose we want to store the words :- BCA–SEM 3 using a linked
list.
- The linked list representation of these words is as follows.

START

B C A S E M 5

- Internal representation of linked list is as follow,

18 / 38
 START INFO LINK
1
2 3
3 B
0
4 E
A 6
5
6 C 8
7 – 7
8 M
5
9 5
9
2
4

- The actual list can be obtain as follows,

START = 3 INFO[3] = B
LINK[3] = 6 INFO[6] = C
LINK[6] = 5 INFO[5] = A
LINK[5] = 7 INFO[7] = –
LINK[7] = 9 INFO[9] = S
LINK[9] = 4 INFO[4] = E
LINK[4] = 8 INFO[8] = M
LINK[8] = 2 INFO[2] = 3
LINK[2] = 0

- The NULL value, so that the list has ended.

2.6 Searching Linked List :

- Let LIST is a linked list stored in memory using linear array INFO and
pointer array LINK

19 / 38
 - In data structure searching operation is used to find the location LOC
of an ITEM in a given list.
- As the LIST may or may not be sorted in memory.
- Hence there are two searching algorithm are used to find the location
LOC of a node where an item appear in the list.
- These algorithms are, 1. LIST is unsorted.
2. LIST is sorted.

1. LIST is Unsorted :
- An algorithm to search an ITEM in unsorted linked List.
- Let LIST is a unsorted linked list stored in memory with INFO and
LINK.
- START is a pointer variable which is used to stored initial address of
linked list.
- Then one searches for ITEM in list by traversing to the list using
pointer variable PTR and comparing ITEM with the contains
INFO[PTR] of each node, one by one of list.

- Before we update the pointer PTR by, PTR LINK [PTR] - We

require to tests.
- First we have to check to see weather we have reached the end of the
list i.e. PTR = NULL.
- If not then check INFO[PTR] = ITEM, search become successful.

Algorithm 2.4 : SEARCHULL (LIST,INFO, LOC, LINK, START, PTR,

ITEM)
Let given linked list is unsorted which stored in memory INFO
variable, LINK is a linked list and START is a starting pointer
variable. This algorithm search a location LOC of the node
where ITEM appear or set LOC = NULL. Here PTR is a local

20 / 38
 pointer variable which indicate the node which is going to
process.
Step 1.: [Initialize pointer PTR]
set PTR START
Step 2.: Repeat step 3 while
PTR NULL
Step 3.: [Is ITEM present at node PTR?]
If ITEM = INFO[PTR], then:
Write : “Successful search” and
Set LOC= PTR and Exit.
Else
[Now point to the next node]
Set PTR = LINK[PTR]
[End of if structure]
[End of step 2 loop]
Step 4.: write “Unsuccessful search” and
Set LOC = NULL
Step 5.: [Finished] Exit.
2. LIST is Sorted :
- An algorithm to search an ITEM in sorted linked List.
- Suppose list is sorted linked list stored in memory.
- This algorithm makes search for the location LOC of an ITEM in LIST
by traversing list using pointer variable PTR.
- Here while traversing an ITEM of information is compare with each
node of the list successful.
- Here traversing is stop when, 1. ITEM is appear at location PTR.
2. ITEM < INFO[PTR] or.
3. There is no further element to make comparison i.e. PTR =
NULL.

21 / 38
 Algorithm 2.5 : SEARCHULL (INFO, LOC, LINK, START, PTR, ITEM)
Let given linked list is sorted which stored in memory with
INFO and LINK. START is a starting pointer variable and PTR
is a local pointer variable which indicate the node which is
going to process. This algorithm finds the location LOC of the
node where ITEM first appear in the list or set LOC = NULL.

Step 1.: [Initialize pointer PTR]

set PTR START
Step 2.: Repeat step 3 while
PTR NULL
Step 3.: [Is ITEM present at node PTR?]
If ITEM = INFO[PTR], then Write
: “Successful search” and Set
LOC= PTR and Exit.
Else if ITEM < INFO[PTR], then
Write “ITEM is out of range” and
Set LOC = NULL and Exit
Else
[update PTR]
Set PTR = LINK[PTR]
[End of if structure]
[End of step 2 loop]
Step 4.: write “Unsuccessful search” and
Set LOC = NULL
Step 5.: [Finished] Exit.

• Complexity for Searching Algorithm :

22 / 38
 1. Sorted Searching Algorithm Complexity :-
a. The complexity of this algorithm is set as complete searching
algorithm for sorted linear array.
b. A sorted linear array we can apply binary search whose running
time is propositional to log2N.

2. Unsorted Searching Algorithm Complexity :-

a. The worst case running time is propositional to the number N of
elements in list and the average case running time is
approximately propositional to N/2.

2.7 Memory Allocation and Garbage Collection :-

1. Memory Allocation :-

- Let a linked list stored in memory using linear array INFO and pointer
array LINK.
- The linked representation of a linked list as follows,

STAR

15 50 10 20 35

START
INFO LINK
1 1 20 4
2 15
2 5
3 10
3 35 1
4
4 5 50 0
5 3

23 / 38
- From above representation, it is clear that one can’t insert any
element (node) in given linked list because there is no any memory
space present.
- Now suppose an element 20 is deleted from the list.
- We know in linked list deletion is take place only by changing.
- The link address of previous node.
- Here a previous node of node 20 is 10.
- Hence, in the LINK field of the node 1 10 will contain the address of
node 35, if one deleted node 20.
- Now though the element 20 is deleted still it is present physically in
the memory cell at location one.
- Hence, one can’t insert new element in this linked list.
- To overcome above problem, some mechanism is used which will
collects, memory space of deleted node are then available for future
use.
- A mechanism which performs such function is known as “Memory
Allocation”.
- In case of linked list, a memory allocation is perform by describing
another special list in the same arrays INFO and LINK.
- Here all the unused memory cells and the cells of deleted nodes will
be linked list by this special list.
- A variable AVAIL which is pointer of type of used to store beginning
location of the special linked list and invalid address NULL is used to
indicate the end of the special list.
- The special list is also known by the list of available space or free
storage list.
- A data structure with frequently will be denoted by writing : LIST
(INFO, LINK, START, AVAIL)

24 / 38
 - Ex.: Consider a list of books is stored in linear array book & LINK then
available memory space in the linear array book may be linked as :

AVAIL
INFO LINK
1 1 DBMS 4
2
START
2 6
3 BASIC
3 5
4 HTML
4 5 C++ 0
6 5 1
6 0

- In above fig. AVAIL indicates first location i.e. 2 is the available space,
next 6 is available space.

2. Garbage Collection :

- It is mechanism or technique which perform the collection of all

deleted space on to the free storage list.
- The kernel of operating system such function in computer.
- To make such collection operating system to the following two steps
:
▪ Computer traverses all lust or memory cell and apply tags
(margin) to the memory cell which are currently in use.
▪ Then computer check all memory cells and collects all untag
memory cells on to the free storage list.
- Generally the garbage collection is take place n two cases:
▪ If there is no memory space at all left in the free storage list.
▪ When CPU has no any work i.e. CUP in idle state.

25 / 38
• Overflow and Underflow :

1. Overflow :
a. Overflow refers the situation one wants to insert the data into the
data structure, which is already filled.
b. This situation can be handle by printing message “OVERFLOW”.
c. In case of linked list overflow will occur when AVAIL = NULL.

2. Underflow :
a. Underflow refers a situation where one wants to delete data from a
empty data structure.
b. This situation can be handle by printing message “UNDERFLOW”.

c. In case of linked list underflow will occur when START = NULL.

2.8 Insertion and Deletion in linked list.

Insertion into Linked List:
- Suppose a linked list is stored in memory in the form of ,
- LIST (INFO, LINK, START, AVAIL)
- A variable ITEM contains new information that to be added into the
list.
- The node in the AVAIL list is used for insertion by using the following
steps :
a. Check for available spaces in AVAIL list. If AVAIL = NULL then
print a message “OVERFLOW”.
b. Removing first node from the AVAIL list and store at pointer
variable NEW as :

26 / 38
 Set NEW = AVAIL and AVAIL = LINK [AVAIL]
c. Place a new information ITEM into the new node as, Set
INFO[NEW] = ITEM.

- The schematic or systematic diagram as follow:

AVAIL STAR Free – storage list

ITEM

- Algorithm which insert nodes into linked list come up in various

situation.
a. Insert a node at the beginning of the list.
b. Insert a node after the node with a given location.
c. Insert a node into a sorted linked list.

1. An algorithm to insert ITEM at the beginning of the linked list.

STAR

NEW

ITEM

Fig. Insertion at the

beginning at a linked list

Algorithm 2.6 : INSERTBLL (INFO, AVAIL, NEW, LINK, START, ITEM)

27 / 38
 Let LINK is a linked list with memory array INFO and LINK.
START and AVAIL is a link pointer variable which indicates
address of beginning with actual linked list. Here NEW is a
local pointer variable used to store address of node. This
algorithm perform insert an ITEM of information at the
beginning of the given linked list.

Step 1. : [Is Overflow ?]

If AVAIL = NULL, then
Write : “OVERFLOW” and Exit
[End of if structure]
Step 2. : [Remove first node from AVAIL]
Set NEW = AVAIL and
AVAIL = LINK[AVIAL]
Step 3. : [place ITEM into NEW node]
Set INFO[NEW] = ITEM
Step 4. : [link NEW node at the beginning]

Set LINK[NEW] START

Step 5. : [change START to the NEW node]
Set START = NEW
Step 6. : [Finished] Exit.

2. An algorithm to insert an ITEM after given node. (After given

location.) ITEM = 90, LOC = 3.

STAR

28 / 38
 10 05 08 40

AVAIL

ITEM

Fig. Insertion after given lolinked list.

Algorithm 2.7 : INSERTLOC (INFO, START, ITEM, LOC, AVAIL,

LINK, NEW)

Let linked list is stored in memory with INFO and LINK. START
and AVAIL is a LINK pointer variable which indicate the
address of beginning actual linked list. This algorithm perform
to insert ITEM after the given location LOC.
Otherwise is LOC = NULL insert at beginning.

Step 1.: [Is Overflow ?]

If AVAIL = NULL, then
Write : “OVERFLOW” and Exit
[End of if structure]
Step 2.: [Remove first node from AVAIL]
Set NEW = AVAIL and
AVAIL = LINK[AVIAL]

29 / 38
 Step 3.: [place ITEM into NEW node]
Set INFO[NEW] = ITEM
Step 4.: If LOC = NULL, then
[Insert as first node]
Set LINK[NEW] = START and
Set START = NEW
Else:
[Insert node after a given location]
Set LINK[NEW] = LINK[LOC] and
LINK[LOC] = NEW
[End of if structure]
Step 5.: [Finished] Exit.

3. Algorithm to insert an ITEM into a sorted linked list.

- Suppose list is a sorted linked list stored in memory using linear array
INFO and LINK.
- When an ITEM is to be inserted into a sorted linked list, then it must
be satisfy the condition.
INFO[A] < ITEM < INFO[B]. Where A and B are two successive
nodes.
- To insert a NEW ITEM into a sorted linked list, one must know the
required location LOC of a node after which ITEM is to be inserted.

Procedure to find location LOC of a node is a sorted linked list, ITEM = 20.

LOC P PTR
STAR

9 10 15 25 30

- This procedure find location LOC of a node A. here value is < ITEM.

30 / 38
- The location is search by traversing a list using point variable PTR
and comparing ITEM with INFO[PTR].
- Here, while traversing the location of precidy node is save using a
pointer variable LOC P as shown in above figure.
- The pointer variable LOC and PTR is updated as,
Set LOCP = PTR and
PTR = LINK[PTR]
- Here, the traversing get stop as soon as ITEM < = INFO[PTR]
- If the above condition become true then this procedure set value of
LOC as,
LOC = LOCP and return.
- Also if given list is empty or ITEM < INFO[START] then it
Set LOC = NULL and return.
Procedure 2.2 : FINDLOCLL (INFO, LINK, START, ITEM, LOC)

Let this procedure find the location LOC of a node in a sorted

linked list such that INFO[LOC] < ITEM or Set LOC = NULL.
Here, PTR and LOC are the actual local pointer variable used to
store address of a node which is going to process and address
of previous node respectively.

Step 1.: [Is Underflow ?]

If START = NULL, then
Write “UNDERFLOW (empty list)”, and
LOC = NULL and Exit.
[End of if structure]
Step 2.: [Is ITEM < Starting element ?]
If ITEM < INFO[START], then
Set LOC = NULL and return

31 / 38
 [End of if structure]
Step 3.: [Initialize LOCP and PTR]
Set LOCP = START and
PTR = LINK[START]
Step 4.: [Make search]

While PTR NULL

Step 5. : [check ITEM and INFO(PTR)]
If ITEM < INFO[PTR], then
LOC = LOCP and return
Else
[update LOCP and PTR]
Set LOC = PTR and
PTR = LINK[PTR]
[End of if structure]
[End of step 4 loop]
Step 6. : Set LOC = LOCP
Step 7.: Return. [Return to the point of call]

4. An algorithm to insert ITEM at location in sorted linked list.

Algorithm 4.8 : INSERTSLL (LINK, INFO, LOC, START, PTR, AVAIL,

ITEM)

Let given linked list is a sorted linked list which is stored in

memory using a linear array INFO and LINK. This algorithm
insert an ITEM into given linked list.

Step 1.: [use procedure 4.1 to find location LOC]

Call FINDLOC (INFO, LINK, START, LOC, ITEM)

32 / 38
 Step 2.: [use algorithm 4.7 to insert ITEM after given
location]
Call INSERTFLOC(INFO, LINK, START, ITEM)
Step 3.: [Finished] Exit

Deletion From Linked List :

- LIST is a linked list with a node X between node A and node B as

shown in following figure.

STAR
Data List
Node A
Node B

10 05 50 20
AVAIL

Free Storage List

- We know in linked list deletion take place as soon as the next pointer
field of node A point to node B.
- When node X is deleted from the list its used memory space is
immediately return to the beginning of the AVAIL list shown in above
figure.
- From figure it is observe that three pointer fields are changes as
follows,
▪ The next pointer field of node A to node B, here node X
previously pointed.
▪ The next pointer field of X now points to the first node in he
free storage list.
▪ AVAIL now points to the deleted node X.

33 / 38
 - When deletion operation occurs, their must be to cases consider :
▪ If deleting the node X is the first node in the list then START
will point node B.
▪ If deleting node X is the last node in the list, then the LINK
pointer field of node A will contain a NULL pointer.

1. An algorithm delete a node following a given node :

- Deletion algorithm will return the memory space of the deleted node
X to the beginning of the AVAIL list.
- Here LOC is a location of the deleted node X as,
LINK[LOC] = AVAIL and AVAIL = LOC
- These two operations are shown in following figure.

LOC

Node X

AVAIL

Free Storage List

2. An algorithm check to see if there is node in the list if not i.e.
START = NULL then print message “Underflow”.

Algorithm 4.9 : DELNODE (INFO, LINK, AVAIL, LOC, START, LCOP)

Let LIST be a linked list stored in memory with INFO and LINK.
LCO is a location of Node X which will delete and LOCP is a
location of the node precidy X. When X is the first node then
LOCP = NULL. This algorithm delete the node X with location
LOC.

34 / 38
 Step 1.: If LOCP = NULL, then
Set START = LINK[START]
[Delete first node]
Else
Set LINK[LOCP] = LINK[LOC]
[Delete node X]
[End of if structure]
Step 2.: [Insert deleted node at the AVAIL list]
Set LINK[LOC] = AVAIL and
AVAIL = LOC
Step 3.: [Finished] Exit.

2. An algorithm delete a node with a given item of information.

- Let LIST be a linked list in memory.

- Suppose we are given an ITEM of information and we want to delete
from the LIST.
- The first node which contain ITEM one need to node the location of
the node preceding location etc.
- If the node X is first node then set LOCP = NULL an ITEM doesn’t
appear in the LIST at that time set LOC = NULL.
- Traverse the LIST using the pointer variable PTR and while
traversing variable PTR and while traversing compare ITEM with
INFO[PTR] at each node, while traversing keep track of the location
of the preceding node by using pointer variable SAVE.
- Here SAVE & PTR updated as,
SAVE = PTR & PTR = LINK[PTR]

- Traversing continues as long as INFO[PTR] ITEM.

- Following is a procedure which points find location LOCP and LOC.

35 / 38
 Procedure 4.2 : FINDLOCPLOC (INFO, LINK, START, PTR, LOCP, ITEM,
LOC)

This procedure find the location LOC of the first node X which
contains ITEM and location LCOP of the preceding node X. If
ITEM doesn’t appear in the LIST, then the procedure set LOC =
NULL and if ITEM appears in the first node then it sets LCOP =
NULL.

Step 1.: [Is list empty ?]

If START = NULL, then
Write “List is Empty”(Underflow), and
Set LOCP = NULL and
LOC = NULL and
Return
[End of if structure]
Step 2.: [Is ITEM present at first node of the list?]
If INFO[START] = ITEM, then
Write “Successful search”, and
Set LOC = START and
LOCP = NULL and Return
Step 3.: [Initialize pointer SAVE and PTR]
Set SAVE = START and
PTR = LINK[START]
Step 4.: Repeat step though 5

While PTR NULL

Step 5. : [Is item present at node PTR?]
If INFO[PTR] = ITEM, then
Write “successful search”, and

36 / 38
 Set LOCP = SAVE and
LOC = PTR and Return
Else :
[update pointer SAVE and PTR]
Set SAVE = PTR and
PTR = LINK[PTR]
[End of if structure]
[End of step 4 loop]
Step 6. : [Set LOCP & LOC]
Write “Unsuccessful search”
Set LOCP = NULL and
LOC = NULL
Step 7.: Return. [Return to the point of call]

Following is an algorithm which delete node X (node n) with

ITEM of information.

Algorithm 4.10 : DELITEM (INFO, LINK, LOC, START, LCOP)

This algorithm deletion from linked list the first node X which
contain the ITEM of information.

Step 1.: [Use procedure 4.2 to find location LOC of X its

preceding node LOCP]
Call FINDLOCPCOL[INFO, LINK, START, LOC,
LOCP]

Step 2.: [Is underflow ?]

If LOC = NULL, then
Write “UNDERFLOW”, and

37 / 38
 Exit
Step 3.: [Is ITEM of node present at the beginning the list ?]
If LOCP = NULL, then
[Delete node]
Set START = LINK[START]
[End of if structure]
Step 4.: [Delete node from location LOC using preceding
node LOCP]

Set LINK[LOCP] = LINK[LOC]

Step 5.: [Insert deleted node at the begin of AVAIL list]
Set LINK[LOC] = AVAIL and

AVAIL LOC
Step 6.: [Finished] Exit.

38 / 38