MODULE 2-ARRAYS AND LINKED LISTS

ARRAYS
An array is a collection of items of the same variable type that are stored
at contiguous memory locations. It’s one of the most popular and simple
data structures and is often used to implement other data structures. Each
item in an array is indexed starting with 0.
The length or the number of data elements of the array can be obtained from the
index set by formula:
length=UB-LB+1 where UB-upper bound and LB-lower bound
The number K in A[K] is called a subscript or an index and A[K] is called a
subscripted variable. The subscript allows any element of A to be referenced by
its relative position in A.
REPRESESNTATION OF LINEAR ARRAYS in memory
Let LA be a linear array in the memory then
LOC(LA[K])=address of element LA[K] of the array LA.
The computer doesnot need to keep track of the address of every element of
LA,but needs to keep track only of the first element of LA denoted by
BASE(LA).
• The computer calculates the address of any element of LA by the
following formula:
LOC(LA(k))=BA(LA)+w(K-lower bound)
where w is the number of words per memory cell for the array LA
Types of arrays:
There are mainly two types of arrays:
1. One Dimensional Array
2. Two Dimensional Array
1. One Dimensional Array:
 It is a list of the variable of similar data types.
 It allows random access and all the elements can be accessed with the
help of their index.
 The size of the array is fixed.
Representation of 1D array:

2. Two Dimensional Array:

 It is a list of lists of the variable of the same data type.
 It also allows random access and all the elements can be accessed with the
help of their index.
 It can also be seen as a collection of 1D arrays. It is also known as the
Matrix.
 Its dimension can be increased from 2 to 3 and 4 so on.
 They all are referred to as a multi-dimensional array.
 The most common multidimensional array is a 2D array.

Representation of 2 D array:

 If X is a 2D m x n array with m rows and n columns,the array will be

represented in memory by a block of m.n sequential memory locations.
When it comes to organizing and accessing elements in a multi-dimensional
array, two prevalent methods are Row Major Order and Column Major Order.
 1. Row Major Order
Row major ordering assigns successive elements, moving across the rows
and then down the next row, to successive memory locations. In simple
language, the elements of an array are stored in a Row-Wise fashion.
To find the address of the element using row-major order uses the following
formula:
ROW MAJOR uses the formula:
Address of (A[j][k]) =BASE(A)+w[N(J-LR)+(K-LC)]
2. Column Major Order
If elements of an array are stored in a column-major fashion means moving
across the column and then to the next column then it’s in column-major
order.
To find the address of the element using column-major order use the
following formula:
Address of (A[j][k]) =BASE(A)+w[M(K- LC)+(J- LR)]

j = Row Subset of an element whose address to be found,

k = Column Subset of an element whose address to be found,
BASE(A) is the address of first element
W = Storage size of one element store in any array(in byte),
M is the [Link] rows
N is the [Link] columns
LR = Lower Limit of row/start row index of matrix (If not given assume it as
zero),
LC = Lower Limit of column/start column index of matrix (If not given
assume it as zero),

TRAVERSING LINEAR ARRAYS

• Accessing and processing of each element of array exactly once is
called traversing.
 • Let A be a collection of data elements stored in the [Link] print the
contents of each element of A or to count the number of elements with a
given property,it is done by traversing A (ie,by accessing and processing
or visiting)each element of A exactly once.

INSERTION
• Insertion refers to the operation of adding another element to the
collection A.
• Inserting an element to the end of the array can be easily done if the array
is large enough to accommodate an additional element.
• If the element is to be inserted in the middle of the array,half of the
elements must be moved to locations with larger subscripts to
accommodate the new element.
DELETION
• Deletion refers to the operation of deleting an element from the collection
A
• Deleting an element from the end of the array is easy,but deleting from
the middle of the array require each subsequent elements be moved one
location ie, to location with smaller sub scripts to fill up the continuous
memory locations in the array

Searching
•Let DATA be a collection of data elements in memory and ITEM be a
specific information given.
•Searching refers to the operation of finding the location LOC of ITEM in
DATA or printing some messages that ITEM does not appear there.
•The search is successful if the ITEM appears in DATA and unsuccessful
otherwise.
•Two searching algorithms are
1)Linear search
2)Binary search
LINEAR SEARCH
The method which traverses an array sequentially to locate an item is called
linear [Link] case complexity O(n).
BINARY SEARCH
If DATA is an array sorted in increasing order,then the most efficient
searching algorithm is binary search(which can be used to find the location
LOC of a given ITEM in DATA.)
•Algorithm works as :
During each stage of the algorithm,our search for ITEM is limited to one
segment of elements of DATA.
DATA[BEG],DATA[BEG+1],DATA[BEG+2],…,DATA[END], where
BEG and END denotes the beginning and end locations of the segment under
consideration.
The algorithm compares ITEM with the middle element DATA[MID] of the
segment where MID =INT((BEG+END)/2)
•If DATA[MID]=ITEM then search us successful and LOC=MID,otherwise
a new segment of DATA is obtained as follows.
a) If ITEM <DATA[MID],then ITEM can appear only in left half of the
segment,DATA[BEG],DATA[BEG+1],….DATA[MID-1].So reset
END=MID-1 and begin searching again.
b)if ITEM>DATA[MID] then ITEM can appear only in right half of the
segment,DATA[MID+1],DATA[MID+2],…DATA[END].So reset
BEG=MID+1 and begin searching again.
Initially BEG=LB and END=UB. if ITEM is not in DATA, then we obtain
END<BEG. This condition signals that the search is unsuccessful.
•Then LOC =NULL(mostly NULL=0)

Complexity of binary search

Complexity is measured by the number f(n) of comparisons to locate ITEM
in DATA where DATA contains n elements
F(n)=|log2n|+1
Parallel arrays
• Also known as structure of array (SoA), multiple arrays of the same size
such that i-th element of each array is closely related and all i-th
elements together representing an object or entity.
first_name= ['Bones', 'Welma', 'Frank', 'Han', 'Jack']
last_name= ['Smith', 'Seger', 'Mathers', 'Solo', 'Jackles']
height = [169, 158, 201, 183, 172]
Advantages
• Parallel arrays are simple to understand and use, and are often used.
• Sequentially examining a single field of each record in the array is very
fast on modern machines.
• They can save a substantial amount of space
Disadvantages

-They are expensive to grow or shrink since each of several arrays must be
reallocated.

-They greatly raise the possibility of errors. Any insertion, deletion, or move
must always be applied consistently to all of the arrays, otherwise the arrays
will no longer be synchronized with each other.

Sparse matrix
• A matrix is a two-dimensional data object made of m rows and n
columns, therefore having total m x n values.
• If most of the elements of the matrix have 0 value, then it is called a
sparse matrix.
Advantage of sparse matrix over simple matrix
Storage:There are lesser non-zero elements than zeros and thus lesser
memory can be used to store only those elements.
Computing time:Computing time can be saved by logically designing a data
structure traversing only non-zero elements..
Sparse Matrix Representations
Triplet Representation (Array Representation)
2D array is used to represent a sparse matrix in which there are three rows
named as
Row:Index of row, where non-zero element is located
Column:Index of column, where non-zero element is located
Value:Value of the non zero element located at index –(row, column)

Linked list representation

In linked list, each node has four fields. These four fields are defined as:
Row:Index of row, where non-zero element is located
Column:Index of column, where non-zero element is located
Value:Value of the non zero element located at index –(row,column)
Next node:Address of the next node

Linked list
• A linked list is a linear data structure, in which the elements are not
stored at contiguous memory locations.
• A linked list consists of nodes where each node contains a data field and a
reference(link) to the next node in the list.
• The elements in a linked list are linked using pointers as shown in the
below image:

Representation of Linked List in memory

• Let LIST be a linked list.
• LIST requires a variable HEAD/START which points to beginning of
list.
• It requires two linear arrays INFO and LINK such that INFO[k] and
LINK[k] contains respectively information part and next pointer field of a
node of LIST.
 • LINK[k]=NULL indicates the end of the list.

Traversal in a linked list

Algorithm
(Traversing a linked list)Let LIST be a linked list in memory. This algorithm
traverses LIST applying the operation PROCESS to each element of the
LIST. The variable PTR points to the node currently being processed.
1. Set PTR:=START[Initializes pointer PTR]
2. Repeat steps 3 and 4 while PTR≠ NULL
3. Apply PROCESS to INFO[PTR]
4. Set PTR:=LINK[PTR][PTR now points to the next node]
[End of step 2 loop]
5. Exit
Searching a linked list
LIST is a linked list in memory. The algorithms find the location LOC of the
node where a specific information ITEM appears first in the LIST.
• LIST is unsorted
• The ITEM is searched by traversing through the LIST using a pointer
variable PTR and comparing ITEM with the contents of INFO[PTR] of
each node of LIST
 • Two conditions are checked before updating the pointer
PTR:=LINK[PTR],
• 1)Whether the end of list is reached , ie PTR=NULL
• 2)Whether ITEM is found ,ie INFO[PTR]=ITEM
Algorithm SEARCH(INFO,LINK,START,ITEM,LOC)
LIST is a linked list in memory. This algorithm finds the location LOC of the
node where ITEM appears first in the LIST or sets LOC=NULL
1. Set PTR:=START
2. Repeat step 3 while PTR≠NULL
3. If ITEM=INFO[PTR] then
Set LOC=PTR and Exit
else
Set PTR=LINK[PTR][PTR now points to the next node]
(End of If structure)
4. [Search is unsuccessful] Set LOC=NULL
5. Exit
Algorithm SRCHSL(INFO,LINK,START,ITEM,LOC)
LIST is a sorted list in memory. This algorithm finds the location LOC of the
node where ITEM first appears in LIST or sets LOC=NULL
[Link] PTR:=START
2. Repeat step 3 while PTR≠NULL
[Link] ITEM >INFO[PTR] ,then
Set PTR:=LINK[PTR][PTR now points to the next node]
Else if ITEM :=INFO[PTR] then
Set LOC:=PTR and Exit[Search is successful]
Else
Set LOC:=NULL and Exit [ITEM< INFO[PTR]]
[End of if structure]
[End of Step 2 loop]
4. Set LOC=NULL
5. Exit
Insertion into a linked list
Let LIST be linked list with successive nodes A and [Link] node N is to be
inserted into the list between nodes A and B

Three modes of insertion:

• Inserting at the beginning of a list
• Inserting after a given node
• Inserting into a sorted linked list

Garbage Collection
If a node is deleted from a list or an entire list is deleted from a program,some
memory space becomes [Link] space can be reinserted to the free storage
list which is time consuming for the [Link],The OS periodically collects all the
deleted space into the free storage [Link] technique which does this is called
garbage [Link] is done when there is only some minimum amount of
space or no space at all left in the free storage list or when the CPU is idle and
has time to do the collection(invisible to the programmer)
Overflow and Underflow
•If a new data is to be inserted into a data structure and the free storage list is
empty, this situation is called an overflow.
•The programmer my handle overflow by printing the message [Link]
occurs when AVAIL=NULL.
•If we try to delete a data from an empty datastructure, the situation is called
underflow.
•The programmer may handle underflow by printing the message
UNDERFLOW. It occurs when START=NULL.
 • Inserting at the beginning of a list

Algorithm: Inserting after a given node

INSLOC(INFO,LINK,START,AVAIL,LOC,ITEM)
This algorithm inserts ITEM so that ITEM follows the node with location
LOC or inserts ITEM as the first node when LOC=NULL.

Algorithm: Inserting into a sorted linked list

•ITEM is inserted to a sorted linked list [Link] must be inserted between
nodes A and B so that INFO(A)<ITEM<=INFO(B)
•The procedure finds the location LOC of node A(location LOC of the last node
in the list whose value is less than ITEM)
•Traverse the list using a pointer variable PTR and compare ITEM with
INFO[PTR] at each node.
•Keep track of the location of the preceeding node by using a pointer variable
[Link] and PTR are updated as
SAVE:=PTR
PTR:=LINK[PTR]

•Traversing continues as long as INFO[PTR]<ITEM and stops as soon as

ITEM<INFO[PTR].Then PTR points to node B,so SAVE will contain the
location of the node A.
•The two cases are
1)LIST is empty
2)ITEM<INFO[START],so LOC=NULL

Algorithm: Inserting into a sorted linked list

INSERT(INFO,LINK,START,AVAIL,ITEM)
This algorithm inserts ITEM into a sorted linked list.
[Link] FINDA(INFO,LINK,START,ITEM,LOC)[to find the location of the node
preceding ITEM]
[Link] INSLOC(INFO ,LINK,START,AVAIL,LOC,ITEM)
[Link].
FINDA(INFO,LINK,START,ITEM,LOC)

Deletion from a linked list

Let LIST be a linked list with node N between node A and B .Suppose node N
is to be [Link] deletion occurs as soon as the next pointer field of node A
is changed so that it points to node [Link] deletion ,keep track of address of
the node which immediately precedes the node that is to be deleted.
Deleting the node following a given node

When a node is deleted from our list,we will immediately return its memory
space to the AVAIL [Link] changes in three pointer fields are as follows:
[Link] nextpointer field of node A now points to node B where node N was
previously pointed.
[Link] nextpointer field of node N points to the original first node in free pool
where AVAIL previously pointed.
[Link] now points to the deleted node N.

Special cases
1. If deleted node N is the first node in the list,then START will point to node B
2. If deleted node N is the last node in the list then node A will contain the
NULL pointer.

Deletion Algorithms
•Deletion of a node following a given node
•Deletion of a node with a given ITEM of information
Assume that Linked list is of the form LIST(INFO,LINK,START,AVAIL).Both
the deletion algorithms return the memory space of deleted node N to the
beginning of AVAIL list.

•LOC is the location of the deleted node N

LINK[LOC]:=AVAIL and AVAIL=LOC

Deleting the node following a given node

Deleting the node with a given ITEM of information
•LIST is a linked list in memory.
•We want to delete the first node N which contains ITEM in LIST.
•First we write a procedure which finds the location LOC of the node N
containing ITEM and the location LOCP of the preceding node
•If N is the first node , LOCP=NULL and if ITEM is not in the LIST ,
LOC=NULL
•Traverse the LIST using PTR and comparing ITEM with INFO[PTR].
•Keep track of the preceding node using SAVE
•SAVE:=PTR and PTR:=LINK[PTR] (updating SAVE and PTR)
•Traversing stops when ITEM:=INFO[PTR].
•Then PTR contains the location LOC of node N and SAVE contains the
location LOCP of the preceding node.
•Special case: INFO[START]=ITEM(node N is the first node),SAVE is not
involved
Algorithm: Deleting the node with a given ITEM of information

Procedure FINDB
Header linked list
It is a linked list which always contains a special node called the header node
at the beginning of the list.
•Two types of header lists:
1. Grounded header list: list where last node contains the NULL pointer
2. Circular header list: list where last node points back to the header node.
•START always point to the header node.
•LINK[START]:= NULL indicates that the grounded header list is empty.
•LINK[START]:= START indicates that the circular header list is empty.
 The first node in a header list is the node following the header node and the
location of the first node is LINK[START] and not START as with ordinary
linked list.
Circular header lists are frequently used instead of ordinary linked list
because many operations are much easier to state and implement in header
lists. A linked list whose last node points back to the first node instead of
containing the NULL pointer is called a circular list.
Properties of Circular header lists :
[Link] pointers contain valid addresses .NULL pointer is not used.
[Link] node has a preceding node. So first node may not require a special
case.
The variations of linked lists are:
•Singly linked list (ordinary linked list)
• Doubly linked list(two way list)

•
A linked list which contain a special header node at the beginning and a
special trailer node at the end.
•
Doubly linked list(two way list)
Two way lists
•
This list can be traversed in two directions:
-in the usual forward direction from the beginning of the list to the end.
-in the backward direction from end of the list to beginning.
•Given a location LOC of a node N in the list, one has immediate access to both
the next node and the preceding node in the list.
•A two way list is a linear collection of data elements called nodes where each
node N has three parts:
1)An information field INFO which contains the data of N.
2)A pointer field FORW which contains the location of the next node in the list.
3)A pointer field BACK which contains the location of the preceding node in
the list.
This list also requires two list pointer variables :
FIRST which points to the first node in the list
LAST which points to last node in the list
•In the fig., null pointer appears in the FORW field of the last node in the list
and also in the BACK field of the first node in the list.

Using pointer variable FIRST and pointer field FORW the list can be traversed
forward as before
•Using pointer variable LAST and pointer field BACK the list can be traversed
backwards.
•Suppose LOCA and LOCB are the locations of nodes A and B in a two way
list then,
FORW[LOCA]=LOCB iff BACK[LOCB]=LOCA
ie. Node B follows node A is similar to node A precedes node B
Two way header list
Advantages of a two way list and a circular header list is combined in two way
circular header list.

Operations on two way list:

1)Traversing
2)Searching
3)Inserting
4)deleting