Array Operations

Traversing, Searching, Insertion,

Deletion and Sorting with Examples
and Algorithms
 TRAVERSING IN AN ARRAY
TRAVERSE ARR ( ARR , LB , UB )

ARR - Linear Array

LB - Lower Bound of array
UB - Upper bound of array
Step 1 : Start

Step 2 : [Initialization] SET K = LB

Step 3 : Repeat steps 4 and 5 while ( K < = UB )

Step 4 : Apply PROCESS to ARR[K]

Step 5 : SET K = K + 1

Step 6 : Exit
SEARCHING ALGORITHM
Linear Search
Binary Search
LINEAR SEARCH ( ARR, N, LOC, ITEM)

ARR - Linear array of size N

N - Size of the array
LOC - Position of the required element in ARR
ITEM - Element to be searched
Step 1 : Start
Step 2 : [Initialization] SET K = 1 , LOC = 0
Step 3 : Repeat steps 4 and 5 while ( K <= N )
Step 4 : If (ITEM == ARR[K] ) SET LOC = K
Break
Step 5 : K = K + 1
[End of Loop]
Step 6 : If (LOC == 0) PRINT ( Unsuccessful Search )
Else PRINT ( Element found at LOC )
Step 7 : Exit
BINARY SEARCH ( ARR, LB, UB, LOC, ITEM)

ARR - Linear array of size N

LB - Lower Bound of ARR
UB - Upper Bound of ARR
LOC - Position of the required element in ARR
ITEM - Element to be searched
Step 1 : Start
Step 2 : [Initialization] SET BEG = LB , END = UB , MID = INT (( BEG + END ) / 2 )
Step 3 : Repeat steps 4 and 5 while ( BEG <= END AND ARR[MID] != ITEM )
Step 4 : If (ITEM < ARR[MID] ) then SET END = MID - 1
Else SET BEG = MID + 1
Step 5 : SET MID = INT (( BEG + END ) / 2 )
[End of Loop]
Step 6 : If ( ARR[MID] == ITEM ) SET LOC = MID and
PRINT ( Element found at MID )
Else PRINT ( Unsuccessful Search )
Step 7 : Exit
 INSERTION IN AN ARRAY
INSERT ARR ( ARR , K , N, ELEMENT )

ARR - Linear Array of size N

N - Number of elements in array
K - Position/ Location where element needs to be inserted

ELEMENT - New value that needs to be inserted

This algorithm inserts an element at the given position in

a linear array.
Step 1 : Start
Step 2 : [Initialization] SET J = N
Step 3 : Repeat steps 4 and 5 while ( J >= K)
Step 4 : SET ARR [ J + 1 ] = ARR [ J ]
Step 5 : SET J = J - 1
[End of Step 3 loop]
Step 6 : SET ARR [ K ] = ELEMENT
Step 7 : SET N = N + 1
Step 8 : Exit
 DELETION IN AN ARRAY
DELETE ARR ( ARR , K , N, ITEM )

ARR - Linear Array of size N

N - Number of elements in array
K - Position/ Location from where element needs to be deleted

ITEM - Variable to store deleted data element

This algorithm deletes the Kth element from ARR

Step 1 : Start
Step 2 : SET ITEM = ARR [ K ]
Step 3 : Repeat step 4 for J = K to N
Step 4 : SET ARR [ J ] = ARR [ J + 1 ]
[End of Step 3 loop]
Step 5 : SET J = J + 1
Step 6 : [Decrease size of array] SET N = N - 1
Step 7 : Exit
BUBBLE SORT
BUBBLESORT(ARR , N)

ARR - Linear Array of size N

N - Number of elements in array

Step 1 : Start

Step 2 : Repeat steps 3 and 4 FOR K = 1 TO K = N - 1)

Step 3 : SET J = 1

Step 4 : REPEAT WHILE J <= N - K

IF ARR[J] > ARR[J+1] then SWAP

SET J = J + 1

Step 6 : Exit
SELECTION SORT
Algorithm SELECTION SORT:
An array A of size n .
Step 1: Start
Step 2: Input the array A and Size n
Step 3: Repeat step 4 to step 7 for i = 0 to n-1
Step 4: Set min_index = i
Step 5: Repeat for j= i+1 to n
If ( A[ j ] < A[ min_ index ] then
Set min_index = j
Swap A[ j ] to A [ j+1 ]
End of inner Loop
Step 6: Swap A[ j ] to A[min _index]
Step 7: End of outer loop.
Step 8: Output of sorted array A
Step 9: Exit.
 Linked List Operations

Traversing, Searching, Insertion, and

Deletion with Examples and
Algorithms
1. Stack (ADT)
•Operations:
•push(x) → insert element
•pop() → remove element
•peek() → return top element
•isEmpty() → check if empty

•Implementation:
•Using Array
•Using Linked List

Example:
If you use a stack to check balanced parentheses, you don’t care if it’s implemented using an
array or linked list, only that you can push and pop.

2. Queue (ADT)
•Operations:
•enqueue(x) → add element at rear
•dequeue() → remove element from front
•peek() → view front element
•Implementation:
•Circular Array
•Linked List

Example:
When people stand in line (queue) at a ticket counter, the rule is First-In-First-Out (FIFO). The
ADT says how it works, not how it’s built.
 Introduction to Linked List
• A Linked List is a linear data structure where
elements are stored in nodes. Each node
contains:
• 1. Data
• 2. Pointer (next) to the next node.
 Traversal in Linked List
• To traverse a linked list:
• 1. Start from the head node.
• 2. Visit each node.
• 3. Move to the next pointer until NULL.
 Traversing Algorithm
Algorithm: A LIST be a linked list in memory. This algorithm travers List
applying an operation Process to each element of LIST.

Step1. SET PTR= START [initialize Pointer PTR].

Step 2. Repeat Step 3 & 4 while PTR!=NULL
Step [Link] PROCESS to INFO [PTR]
Step [Link] PTR=LINK[PTR] [PTR Now points to New Node]
[End of step 2 loop]
Step [Link]
SEARCHING IN LINKED LIST
SEARCH LL ( INFO , LINK , START, ITEM, LOC )

INFO - Part of node that stores information

LINK - Part of node that stores address of next node
START - Contains address of first node
ITEM - The data element to be searched
LOC - Location of first occurence of ITEM
Step 1 : Start

Step 2 : [Initialization] SET PTR = START

Step 3 : Repeat step 4 while PTR != NULL

Step 4 : If ITEM == INFO[PTR]

SET LOC = PTR and Exit

Else

SET PTR = LINK[PTR]

[End of If Structure]

[End of Step 3 Loop]

Step 5 : SET LOC = NULL

Step 6 : Exit
 Insertion in Linked List
• Types of Insertion:
• 1. At beginning
• 2. At end
• 3. At specific position
• Example: Insert 10 at beginning → 10 -> 20 ->
30
INSERTION IN LINKED LIST
INSERT FIRST ( INFO , LINK , START, ITEM, AVAIL )

INFO - Part of node that stores information

LINK - Part of node that stores address of next node
START - Contains address of first node
ITEM - The data element to be inserted
AVAIL - List of available memory locations

This algorithm inserts ITEM as the first node in the list.

Step 1 : Start

Step 2 : [Check Overflow] IF AVAIL == NULL then PRINT OVERFLOW and EXIT

Step 3 : [Remove first node from AVAIL] SET NEW = AVAIL and AVAIL = LINK[AVAIL]

Step 4 : SET INFO[NEW] = ITEM [Copy new data into new node]

Step 5 : SET LINK[NEW] = START [New node now points to original first node]

Step 6 : SET START = NEW [START now points to the new node]

Step 7 : Exit
INSERT LOC ( INFO , LINK , START, ITEM, AVAIL,LOC )

INFO - Part of node that stores information

LINK - Part of node that stores address of next node
START - Contains address of first node
ITEM - The data element to be inserted
AVAIL - List of available memory locations
LOC - Location of the node after which the new node needs to be inserted

This algorithm inserts ITEM after the node with location LOC.
Step 1 : Start

Step 2 : [Check Overflow] IF AVAIL == NULL then PRINT OVERFLOW and EXIT

Step 3 : [Remove first node from AVAIL] SET NEW = AVAIL and AVAIL = LINK[AVAIL]

Step 4 : SET INFO[NEW] = ITEM [Copy new data into new node]

Step 5 : IF LOC == NULL [Insert as first node]

SET LINK[NEW] = START and START = NEW

ELSE [Insert after LOC]

SET LINK[NEW] = LINK[LOC] and LINK[LOC] = NEW

[End of IF structure ]

Step 6 : Exit
INSERT END ( INFO , LINK , START, ITEM, AVAIL )

INFO - Part of node that stores information

LINK - Part of node that stores address of next node
START - Contains address of first node
ITEM - The data element to be inserted
AVAIL - List of available memory locations

This algorithm inserts ITEM at the end of the linked list.

Step 1 : Start

Step 2 : [Check Overflow] IF AVAIL == NULL then PRINT OVERFLOW and EXIT

Step 3 : [Remove first node from AVAIL] SET NEW = AVAIL and AVAIL = LINK[AVAIL]

Step 4 : SET INFO[NEW] = ITEM [Copy new data into new node]

Step 5 : SET LINK[NEW] = NULL

Step 6 : [If list is empty] IF START == NULL then SET START = NEW and EXIT

Step 7 : SET PTR = START

Step 8 : Repeat step 9 while LINK[PTR] != NULL

Step 9 : SET PTR = LINK[PTR]

Step 10 : SET LINK[PTR] = NEW

Step 11 : Exit
 Deletion in Linked List
• Types of Deletion:
• 1. At beginning
• 2. At end
• 3. At specific position

• Example: Delete first node from 10 -> 20 -> 30

→ 20 -> 30
DELETION IN LINKED LIST
Deletion at beginning

DEL BEG ( INFO , LINK , START, AVAIL )

INFO - Part of node that stores information

LINK - Part of node that stores address of next node
START - Contains address of first node
AVAIL - List of available memory locations

This algorithm deletes the first node in the list.

Step 1 : Start

Step 2 : [Check Underflow] IF START == NULL then PRINT UNDERFLOW and EXIT

Step 3 : SET PTR = START

Step 4 : SET START = LINK[START] [START now points to the second node]

Step 5 : SET LINK[PTR] = AVAIL [Update AVAIL]

Step 6 : SET AVAIL = PTR

Step 7 : Exit
Deletion at given location

DEL( INFO , LINK , START, AVAIL, LOC, LOCP )

INFO - Part of node that stores information

LINK - Part of node that stores address of next node
START - Contains address of first node
AVAIL - List of available memory locations
LOC - Location of node (N) to be deleted
LOCP - Location of the node which precedes N

This algorithm deletes the node N with location LOC.

Step 1 : Start

Step 2 : [Check Underflow] IF START == NULL then PRINT UNDERFLOW and EXIT

Step 3 : IF LOCP == NULL [N is the first node]

SET START = LINK[START] [Deletes first node]

ELSE
SET LINK[LOCP] = LINK[LOC] [Deletes node N]

Step 4 : SET LINK[LOC] = AVAIL

Step 5 : SET AVAIL = LOC

Step 6 : Exit
Deleting the node with given item

DEL( INFO , LINK , START, AVAIL, ITEM )

INFO - Part of node that stores information

LINK - Part of node that stores address of next node
START - Contains address of first node
AVAIL - List of available memory locations
ITEM - Data element to be deleted

This algorithm deletes the node N which contains the given ITEM.
Step 1 : Start

Step 2 : [Use Procedure FIND to find the location of N and its preceding node.]
Call FIND(INFO, LINK,START,ITEM,LOC,LOCP)

Step 3 : If LOC == NULL then PRINT ITEM is not in the list and EXIT

Step 4 : IF LOCP == NULL

SET START = LINK[START] [Delete first node]

ELSE

SET LINK[LOCP] = LINK[LOC]

Step 5 : SET LINK[LOC] = AVAIL

Step 6 : SET AVAIL = LOC

Step 7 : Exit
 Example Walkthrough
• Example:
• Start: 10 -> 20 -> 30
• Insert 5 at beginning: 5 -> 10 -> 20 -> 30
• Insert 40 at end: 5 -> 10 -> 20 -> 30 -> 40
• Delete first node: 10 -> 20 -> 30 -> 40
• Traverse: Print all elements.
Stack and Queue Operations

Push, Pop, Enqueue, and Dequeue

Algorithms
 Algorithm: PUSH (STACK, TOP,
MAXSTK, ITEM)
.PUSH:
The operation used to insert (add) an element into the stack.
•STACK:
The array or list that holds all the elements of the stack.
•TOP:
A pointer or index that indicates the current topmost position in the stack (where
the last element was inserted).
•MAXSTK:
The maximum size or capacity of the stack — the total number of elements it can
hold.
•ITEM:
The new element (data) that needs to be inserted (pushed) into the stack.
 Algorithm: PUSH (STACK, TOP,
MAXSTK, ITEM)

• 1. If TOP = MAXSTK, then Print: OVERFLOW

and Return.
• 2. Set TOP = TOP + 1
• 3. Set STACK[TOP] = ITEM
• 4. Return
Algorithm: POP (STACK, TOP, ITEM)

• POP:
Removes the topmost element from the stack.
• STACK:
The array or structure that holds stack elements.
• TOP:
The index of the current top element; it
decreases by one after removal.
• ITEM:
The value removed from the top of the stack.
Algorithm: POP (STACK, TOP, ITEM)

• 1. If TOP = 0, then Print: UNDERFLOW and

Return.
• 2. Set ITEM = STACK[TOP]
• 3. Set TOP = TOP - 1
• 4. Return
 Algorithm: ENQUEUE (QUEUE, REAR,
MAXQ, ITEM)
ENQUEUE:
Inserts an element at the rear of the queue.
QUEUE:
The structure that holds queue elements.
REAR:
The index of the last element; increases by one after insertion.
MAXQ:
The maximum capacity of the queue.
ITEM:
The element to be added to the queue.
 Algorithm: ENQUEUE (QUEUE, REAR,
MAXQ, ITEM)
• 1. [Queue already filled?]
If FRONT=1
and REAR = N , or if FRONT = REAR +1, then
Write OVERFLOW, and Return.
• 2. [Find new value of REAR]
If FRONT= NULL, then
Set FRONT=1 and REAR=1
Else if REAR = N ,then:
Set REAR=1
Else
Set REAR=REAR+1
[END Of if Structure]
• 3. Set QUEUE[REAR] = ITEM [ This inserts new element]
• 4. Return
 Algorithm: DEQUEUE (QUEUE,N, REAR,
MAXQ, ITEM)
• DEQUEUE:
Removes an element from the front of the queue.
• QUEUE:
The structure that stores all queue elements.
• N:
The front index indicating the position of the first element.
(It increases by one after deletion.)
• REAR:
The index of the last element in the queue.
• MAXQ:
The maximum capacity of the queue.
• ITEM:
The element removed from the front of the queue.
 Algorithm: DEQUEUE (QUEUE,N, REAR,
MAXQ, ITEM)
• 1. [Queue already empty?]
If FRONT=NULL,
Write UNDERFLOW, and Return.
• 2. Set ITEM =QUEUE[FRONT]
• 3.[Find new value of FRONT]
If FRONT= REAR, then :[Queue has only one element to start.]
Set FRONT=NULL and REAR=NULL
Else if FRONT = N ,then:
Set FRONT=1
Else
Set FRONT=FRONT+1
[END Of if Structure]
• 4. Return