Data Structure

Lecture 2
Anwar Rashad
Linear Data Structure

• A Data Structure is said to be linear if its elements form a sequence, or linear

list.
• Two ways to represent linear structure in memory.
• One way is to have the linear relationship between the elements
represented by means of sequential memory locations. Called Array.

• Other way is to have a linear relationship between the elements

represented by means of pointer or links. Called Linked List;

Anwar Rashad, Assistant Professor in Computer Science

Linear Arrays

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

such that

a) The elements of the array are referenced by an index set.

b) The elements of the array are stored in successive memory locations.

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

Anwar Rashad, Assistant Professor in Computer Science

Linear Arrays (Continue…)

• Length or Number of data elements of the array can be obtained from the
index set by the formula
Length = UB – LB + 1

• For example:

127 16 12 23 4 DATA

Anwar Rashad, Assistant Professor in Computer Science

Representation of Linear
Arrays in Memory

• Let LA be a linear array in computer memory, and elements of LA are stored in

successive memory cell.
• We need to know the address of the first element of the array. i.e Base
(LA).

• Using the Base (LA), the computer calculate the address of any element of LA
by the following formula:
LOC(LA[K]) = Base (LA) + w (K – LB)

Where “w” is the number of words per memory cell for the array LA.
Anwar Rashad, Assistant Professor in Computer Science
Traversing Linear Arrays
• Let A be an array, and we want to print the contents of each elements of A.
OR
• We want to count the number of elements of A. This can be accomplished by
Traversing A.

Algorithm for Traversing a Linear Array.

1. For K = LB to UB then
1. Set K = LB
2. While K ≤ UB then Apply PROCESS to LA [K]
Apply PROCESS to LA [K] OR [End of Loop]
set K = K + 1 2. Exit
[End of Loop]
3. Exit
Inserting & Deleting

• Let A is a Linear Array. “Inserting” refers to the operation of adding

another element to the array A.

• And “Deleting” refers to the operation of removing one of the elements

from A.

• Inserting an element at the “End” of a Linear Array can be easily done, if

the array is large enough to accommodate the additional element.

Anwar Rashad, Assistant Professor in Computer Science

Inserting & Deleting

• However, Inserting an element in the “middle” of the array needs – that half of
the elements must be moved downward to new locations to accommodate the
new element and keep the order of the other elements.

• Similarly, deleting an elements at the “End” of an array presents no difficulties.

• But deleting an element somewhere in the “middle” of the array would

require that each subsequent element be moved one location upward in
order to “fill up” the array.

Anwar Rashad, Assistant Professor in Computer Science

Algorithm for Insertion In LA

• INSERT (LA, N, K, ITEM)

LA = Linear Array with N elements and K is a NOTE:
positive integer.
N = No. of elements presented in
1) Set J := N
array
2) While J ≥ K
Set LA[J + 1] := LA[J] K = Location number where new
Set J := J – 1 element to be inserted.
[End of Loop]
3) Set LA[K] := ITEM
4) Set N := N + 1
5) Exit

Anwar Rashad, Assistant Professor in Computer Science

Algorithm for Deletion In LA
• DELETE (LA, N, K, ITEM)

LA = Linear Array with N elements and K is a NOTE:

positive integer.
N = No. of elements presented
1) Set ITEM := LA[K] in array
2) For J = K to N – 1
Set LA[J] := LA[J + 1]
[End of Loop]
3) Set N := N – 1
4) Exit

Anwar Rashad, Assistant Professor in Computer Science

BUBBLE SORT

• Let A be a list of n numbers. Sorting A refers to the operation of rearranging

the elements of A so they are in increasing or decreasing order.

A[1] < A[2] < A[3] < ……….. < A[N]

• The bubble sort is notoriously slow,

• but it’s conceptually the simplest of the sorting Algorithms.

Anwar Rashad, Assistant Professor in Computer Science

HOW BUBBLE SORT WORK

Let A[1], A[2], A[3], ………… A[N] is a list then

• Bubble Sort algorithm works as follows:

• Step 1: Compare A[1] & A[2] and arrange them in the desired order,
• Then Compare A[2] & A[3] and arrange them.
• Continue until we compare A[N-1] & A[N] and arrange them.

• Step 1 contain n – 1 comparisons. During step 1 the largest element is

“Bubbled up” to the nth position.

Anwar Rashad, Assistant Professor in Computer Science

HOW BUBBLE SORT WORK

• Step 2: Repeat step 1 with one less comparison.

• Step 3: Repeat Step 1 with two less comparison.
• And so on…

• For Example: 32, 51, 27, 85, 66, 23, 13, 57 Arrange in ascending order
using bubble sort.

Anwar Rashad, Assistant Professor in Computer Science

Algorithm for Bubble Sort

• BUBBLE (DATA, N)

DATA is an array with N elements. (b) Set PTR := PTR + 1

1) Repeat Step 2 & 3 For K = 1 to N – 1 [End of Inner loop]
2) Set PTR := 1 [End of Outer loop]
3) While PTR ≤ N – K [Executes Pass] 4) Exit
(a) If DATA [PTR] > DATA [PTR + 1], then
Interchange DATA [PTR] and DATA[PTR + 1]
[End of If Structure]

Anwar Rashad, Assistant Professor in Computer Science

Complexity of the
Bubble Sort Algorithm
• The Complexity for a sorting algorithm is measured in terms of the number of
comparisons.

• There are n – 1 comparisons during the first pass, which place the largest
element in the last position;
• There are n – 2 comparisons in the second step, which places the second
largest element in the next-to-last position;
• and so on…
𝑛(𝑛 −1) 𝑛2 𝑛
• f(n) = (n – 1) + (n – 2) + ………….. + 2 + 1 = = - = O(n2)
2 2 2
• The time required to execute the bubble sort algorithm is proportional to n2.
Anwar Rashad, Assistant Professor in Computer Science
 SEARCH

• Let DATA is list of elements in memory, and ITEM is any information.

• Searching refers to the operation of finding the location LOC of ITEM in

DATA.

• Search is said to be successful if ITEM does appear in DATA and

• Unsuccessful otherwise.

Anwar Rashad, Assistant Professor in Computer Science

LINEAR SEARCH

• Let DATA is a linear array with n elements.

• To search ITEM in DATA, We compare ITEM with each element of DATA

one by one.

• This method which traverses DATA sequentially to locate ITEM, is called

Linear Search Or Sequential Search.

Anwar Rashad, Assistant Professor in Computer Science

Algorithm for Linear Search
• LINEAR (DATA, N, ITEM, LOC)
DATA is an array with N elements, and ITEM is a given item of information. This
algorithm finds the location LOC of ITEM in DATA, or sets LOC:= 0 if the search is
unsuccessful.

1) Set DATA[N + 1] := ITEM

4) If LOC = N + 1, then:
2) Set LOC := 1 Set LOC := 0
3) While DATA [LOC] ≠ ITEM Else Print LOC
Set LOC := LOC + 1 5) Exit
[End of loop]

Anwar Rashad, Assistant Professor in Computer Science

Assignment

What are the applications of Array?

&
Complexity of the Linear Search Algorithm
With in a Weak Time…
BINARY SEARCH

• Let DATA is an array which is stored in increasing numerical order or,

equivalently, alphabetically.
• Then there is extremely efficient algorithm, called Binary Search.

• If we want to find the location of some name in a telephone directory.

• One open the directory in the middle to determine which half contains the
name being sought.
• Then opens that half in the middle to determine which quarter contain the
name.
• and so on

Anwar Rashad, Assistant Professor in Computer Science

Algorithm for
Binary Search
• BINARY (DATA, LB, UB, ITEM, LOC) Set BEG := MID + 1
DATA is an array and ITEM is a given item of [End of If Structure]
information. This algorithm finds the location 4) Set MID := INT ((BEG + END)/2)
LOC of ITEM in DATA, or sets LOC:= NULL if the (End of step 2 Loop)
search is unsuccessful.
5) If DATA[MID] := ITEM, then
1) Set BEG := LB, END := UB and MID =
Set LOC := MID
INT((BEG + END)/2)
Else
2) Repeat Step 3 & 4 While BEG ≤ END and
DATA[MID] ≠ ITEM Set LOC := NULL
3) IF ITEM < DATA [MID], then [End of If structure]
Set END := MID – 1 6) Exit
Else
Limitations of the Binary
Search Algorithm
• Since the Binary Search algorithm is very efficient (e.g. it requires only about
20 comparisons with an initial list of 1,000,000 elements).

• Why would one want to use any other search algorithm?

• Observe that the algorithm requires two conditions:

1) The list must be sorted.
2) One must have direct access to the middle element in any sub-list.

Anwar Rashad, Assistant Professor in Computer Science

MULTI-DIMENSIONAL ARRAYS

• The arrays discussed so far are called One-Dimensional Arrays.

• Since each element is referenced by a single subscript.

• Most Programming languages allow Two & Three Dimensional Arrays.

• i.e. where each element is referenced respectively, by two & three
subscripts.

Anwar Rashad, Assistant Professor in Computer Science

TWO-DIMENSIONAL ARRAYS

• A Two-dimensional m x n array is a collection of m.n data elements such

that each element is specified by a pair of integers (such as J, K), called
subscripts.

• Two-dimensional arrays are called matrices in mathematics and table in

business application;

• Two-dimensional arrays are sometime called Matrix arrays.

Anwar Rashad, Assistant Professor in Computer Science

REPRESENTATION OF TWO-DIMENSIONAL
ARRAYS IN MEMORY

• Let “Arr” is a two-dimensional m x n array, with m rows and n columns

• This array will be represented in memory by a block of m.n sequential
memory locations.

• Programming languages will store the array “Arr” either

i. Column by column, which is called column-major order.
OR
ii. Row by row, is called row-major order

Anwar Rashad, Assistant Professor in Computer Science

REPRESENTATION OF TWO-DIMENSIONAL
ARRAYS IN MEMORY

• In two-dimensional array, the computer keeps track of Base (Arr) – the address
of the first element A[1, 1] of “Arr”.
• Formula for Column-Major-Order
LOC (Arr[J, K]) = Base (Arr) + w [M(K – 1) + (J – 1)]
• Formula for Row-Major-Order
LOC (Arr[J, K]) = Base (Arr) + w [N(J – 1) + (K – 1)]

Note: W denote the number of words per memory location for the array “Arr”.
With M rows & N columns.

Anwar Rashad, Assistant Professor in Computer Science

Records: Records Structures

• A Record is a collection of related data items, each of which is called a field or

attribute, and
• A file is a collection of similar records.
• Record is differs from a linear array in the following ways
a) A Record may be a collection of non-homogeneous data; i.e each data
item have different data types.
b) The data item in a record are indexed by attribute names, so they may
not be a natural ordering of its elements.

Anwar Rashad, Assistant Professor in Computer Science

END