1 Linear Data Structures

Data Structure
Linear
Non-Linear

A Data structure is said to be linear if its elements form a

sequence or in other words form a linear list
2 Representation in Memory

Two basic representation in memory

Have a linear relationship between the elements represented by
means of sequential memory locations [ Arrays]

Have the linear relationship between the elements represented by

means of pointer or links [ Linked List]
3 Operation on Linear Structure

Traversal : Processing each element in the list

Search : Finding the location of the element with a given value or
the record with a given key
Insertion: Adding a new element to the list
Deletion: Removing an elements from the list
Sorting : Arranging the elements in some type of order
Merging : Combining two list into a single list
4 Linear Arrays

A linear array is a list of a finite number of n homogeneous data

elements ( that is data elements of the same type) such that
The elements of the arrays are referenced respectively by an
index set consisting of n consecutive numbers
The elements of the arrays are stored respectively in successive
memory locations
5 Linear Arrays

The number n of elements is called the length or size of the array.

The index set consists of the integer 1, 2, … n
Length or the number of data elements of the array can be obtained
from the index set by
Length = UB – LB + 1 where UB is the largest index called the
upper bound and LB is the smallest index called the lower bound
of the arrays
6 Linear Arrays

Element of an array A may be denoted by

Subscript notation A1, A2, , …. , An
Parenthesis notation A(1), A(2), …. , A(n)
Bracket notation A[1], A[2], ….. , A[n]

The number K in A[K] is called subscript or an index and A[K] is

called a subscripted variable
7 Representation of Linear Array in Memory

1000
1001
1002
1003
1004
1005
:
Computer Memory
8 Representation of Linear Array in Memory

Let LA be a linear array in the memory of the computer

LOC(LA[K]) = address of the element LA[K] of the array LA
The element of LA are stored in the successive memory cells
9 Representation of Linear Array in Memory

Computer does not need to keep track of the address of every

element of LA, but need to track only the address of the first
element of the array denoted by Base(LA) called the base address
of LA
LOC(LA[K]) = Base(LA) + w(K – lower bound) where w is the
number of words per memory cell of the array LA [w is size of the
data type]
10 Example 1

200 LA[1]
Find the address for LA[6] LA[2]
201
Each element of the array occupy
1 byte 202 LA[3]
203 LA[4]
204 LA[5]
205 LA[6]
206 LA[7]
207 LA[8]

LOC(LA[K]) = Base(LA) + w(K – lower bound) :

LOC(LA[6]) = 200 + 1(6 – 1) = 205
11 Example 2

200
Find the address for LA[16] LA[1]
201
Each element of the array occupy
2 byte 202
LA[2]
203
204
LA[3]
205
206
LA[4]
207

LOC(LA[K]) = Base(LA) + w(K – lower bound) :

LOC(LA[16]) = 200 + 2(16 – 1) = 230
12 Representation of Linear Array in Memory

Given any value of K, time to calculate LOC(LA[K]) is same

Given any subscript K one can access and locate the content of
LA[K] without scanning any other element of LA
A collection A of data element is said to be indexed if any element
of A, called Ak, can be located and processed in time that is
independent of K
13 Traversing Linear Arrays

Traversing is accessing and processing (aka visiting ) each element

of the data structure exactly ones

Linear Array
•••
14 Traversing Linear Arrays

Traversing is accessing and processing (aka visiting ) each element of the data structure
exactly ones

Linear Array
•••
15 Traversing Linear Arrays

Traversing is accessing and processing (aka visiting ) each element of the data structure
exactly ones

Linear Array
•••
16 Traversing Linear Arrays

Traversing is accessing and processing (aka visiting ) each element of the data structure
exactly ones

Linear Array
•••
17 Traversing Linear Arrays

Traversing is accessing and processing (aka visiting ) each element of the data structure
exactly ones

Linear Array
•••
18 Traversing Linear Arrays

Traversing is accessing and processing (aka visiting ) each element of the data structure
exactly ones

Linear Array
•••
19 Traversing Linear Arrays

Traversing is accessing and processing (aka visiting ) each element of the data structure
exactly ones

Linear Array
•••

1. Repeat for K = LB to UB
Apply PROCESS to LA[K]
[End of Loop]
2. Exit
Example

int total=0;
int i;
printf (“Enter CLASS_SIZE”);
scanf(“%d”, &c);
int marks[c];
for(i=0; i<c; i++)
scanf(“%f”, &marks[i]);
for(i=0; i<c; i++) {
printf (“ %d %f\n”,i, marks[i]);
total += marks[i] ;
}
average=total/c;
printf (“Average = %f\n”,average) ;
 Inserting and Deleting
21
Insertion: Adding an element
Beginning
Middle
End

Deletion: Removing an element

Beginning
Middle
End
22 Insertion
1 Brown 1 Brown
2 Davis 2 Davis
3 Johnson 3 Johnson
4 Smith 4 Smith
5 Wagner 5 Wagner
6 6 Ford
7 7
8 8

Insert Ford at the End of Array

23 Insertion

1 Brown 1 Brown 1 Brown 1 Brown

2 Davis 2 Davis 2 Davis 2 Davis
3 Johnson 3 Johnson 3 Johnson 3 Ford
4 Smith 4 Smith 4 4 Johnson
5 Wagner 5 5 Smith 5 Smith
6 6 Wagner 6 Wagner 6 Wagner
7 7 7 7
8 8 8 8

Insert Ford as the 3rd Element of Array

Insertion is not Possible without loss of data

if the array is FULL
24 Deletion
1 Brown 1 Brown
2 Davis 2 Davis
3 Ford 3 Ford
4 Johnson 4 Johnson
5 Smith 5 Smith
6 Taylor 6 Taylor
7 Wagner 7
8 8

Deletion of Wagner at the End of Array

25 Deletion

1 Brown 1 Brown 1 Brown

1 Brown
2 Davis 2 2 Ford
2 Ford
3 Ford 3 Ford 3
3 Johnson
4 Johnson 4 Johnson 4 Johnson
4
5 Smith 5 Smith 5 Smith
5 Smith
6 Taylor 6 Taylor 6 Taylor
6 Taylor
7 Wagner 7 Wagner 7 Wagner
7 Wagner
8 8 8
8

Deletion of Davis from the Array

26 Deletion

1 Brown
2 Ford
3 Johnson
4 Smith
5 Taylor
6 Wagner
7
8

No data item can be deleted from an empty array

 Insertion Algorithm
27
INSERT (LA, N , K , ITEM) [LAis a linear array with N elements
and K is a positive integers such that K ≤ N. This algorithm
insert an element ITEM into the Kth position in LA ]
1. [Initialize Counter] Set J := N
2. Repeat Steps 3 and 4 while J ≥ K
3. [Move the Jth element downward ] Set LA[J + 1] :=
LA[J]
4. [Decrease Counter] Set J := J -1
5 [Insert Element] Set LA[K] := ITEM
6. [Reset N] Set N := N +1;
7. Exit
 Deletion Algorithm
28
DELETE (LA, N , K , ITEM) [LA is a linear array with N elements
and K is a positive integers such that K ≤ N. This algorithm
deletes Kth element from LA ]
1. Set ITEM := LA[K]
2. Repeat for J = K to N -1:
[Move the J + 1st element upward] Set LA[J] := LA[J + 1]
3. [Reset the number N of elements] Set N := N - 1;
4. Exit
29 Multidimensional Array

One-Dimensional Array
Two-Dimensional Array
Three-Dimensional Array
Some programming Language allows as many as 7 dimension
 Two-Dimensional Array
30
A Two-Dimensional m x n array A is a collection of m . n data elements such that
each element is specified by a pair of integer (such as J, K) called subscript with
property that
1 ≤ J ≤ m and 1 ≤ K ≤ n

The element of A with first subscript J and second subscript K will be denoted by AJ,K
or A[J][K]
 2D Arrays
The elements of a 2-dimensional array a is shown as below

a[0][0] a[0][1] a[0][2] a[0][3]

a[1][0] a[1][1] a[1][2] a[1][3]
a[2][0] a[2][1] a[2][2] a[2][3]
 Rows Of A 2D Array
a[0][0] a[0][1] a[0][2] a[0][3] row 0
a[1][0] a[1][1] a[1][2] a[1][3] row 1
a[2][0] a[2][1] a[2][2] a[2][3] row 2
 Columns Of A 2D Array

a[0][0] a[0][1] a[0][2] a[0][3]

a[1][0] a[1][1] a[1][2] a[1][3]
a[2][0] a[2][1] a[2][2] a[2][3]

column 0 column 1 column 2 column 3

34 2D Array

Let A be a two-dimensional array m x n

The array A will be represented in the memory by a block of m x n sequential memory
location
Programming language will store array A either
Column by Column (Called Column-Major Order) Ex: Fortran, MATLAB
Row by Row (Called Row-Major Order) Ex: C, C++ , Java
 2D Array in Memory
35
A Subscript A Subscript
(1,1) (1,1)
(2,1) (1,2)
Column 1 Row 1
(3,1) (1,3)
(1,2) (1,4)
(2,2) Column 2 (2,1)
(3,2) (2,2)
(1,3) Row 2
(2,3)
(2,3) Column 3 (2,4)
(3,3) (3,1)
(1,4) (3,2) Row 3
(2,4) Column 4
(3,3)
(3,4) (3,4)

Column-Major Order Row-Major Order

36 2D Array
LOC(LA[K]) = Base(LA) + w(K -1)

LOC(A[J,K]) of A[m,n]
Column-Major Order
LOC(A[J,K]) = Base(A) + w[m(K-1) + (J-1)]
Row-Major Order
LOC(A[J,K]) = Base(A) + w[n(J-1) + (K-1)]
37 2D Array Example

Consider a 25 x 4 array A. Suppose the Base(A) = 200 and w =4. Suppose the
programming store 2D array using row-major. Compute LOC(A[12,3])

• LOC(A[J,K]) = Base(A) + w[n(J-1) + (K-1)]

LOC(A[12,3]) = 200 + 4[4(12-1) + (3 -1)]

= 384
38 Pointer, Pointer Array

Let DATA be any array

A variable P is called a pointer if P points to an element in DATA i.e if P contains the
address of an element in DATA
An array PTR is called a pointer array if each element of PTR is a pointer
39

Group 1 Group 2 Group 3 Group 4

Evan Conrad Davis Baker
Two Dimensional
Harris Felt Segal Cooper
Lewis Glass Ford 4x9 or 9x4 array
Shaw Hill Gray
Penn Jones
Silver Reed
Troy
Wagner
King
 1 Evan
40 2 Harris
3 Lewis Group 1
4 Shaw
5 Conrad
: : Group 2
13 Wagner
14 Davis
Group 3
15 Segal
16 Baker
: : Group 4
21 Reed
 1 Evan
41 : : Group 1
4 Shaw
5 $$$
6 Conrad Group are not index in
Group 2 this representation
: :
14 Wagner
15 $$$
16 Davis Group 3
17 Segal
18 $$$
19 Baker
: : Group 4
24 Reed
 1 Evan
42 2 Harris Group 1
Group
3 Lewis
1 1 4 Shaw
2 5
5 Conrad
3 14
: : Group 2
4 16
5 22 13 Wagner
14 Davis
Group 3
15 Segal
16 Baker
: : Group 4
21 Reed
22 $$$