Lecture No.
05
Data Structures and Algorithms
Data Structures
An organized collection of values and
perform set of operations on them.
Cover well-known data structures such as
dynamic arrays, linked lists, stacks,
queues, tree and graphs.
Implement data structures in JAVA
Efficiency
A solution is said to be efficient if it solves
the problem within its resource constraints.
– Space
– Time
The cost of a solution is the amount of
resources that the solution consumes.
Arrays
Elementary data structure that exists as built-in in most
programming languages.
1. One dimensional array representation in memory
loc (x[k]) = base(x) + w*(k-lb)
2. Two dimensional array representation in memory
a. Row Major order
x(i,j) = base(x) + n (i-1) + (j-1)
b. Column Major order
x(i,j) = base(x) + m (j-1) + (i-1)
1-D array representation in memory
Name memory
C[0] 24
C[1] 26
C[2] 28
C[3] ...
C[4] ...
C[5] ...
C[6] ...
C[7] ...
C[8] ...
C[9] ...
1-D array representation in memory
Consider array name is Auto established in 1960:
loc (Auto[k]) = base(Auto) + w * ( k - lb)
base (Auto) = 200 //base address of array
w = words per memory cell = 02 //(int having 2 bytes)
K = kth element
Lb = lower bound
Address of any element in the array can be obtained with
contents.
For example standing of Automobile company in 1983?
loc (Auto[1983]) = base(200) + 2 * (1983-1960)
= 200 + 2 * (23)
= 200 + 46 = 246
At address of (246), contents can be retrieved.
2-D array representation in memory
There are Two-ways to represent 2-D array
1. Row Major order
x(i,j) = base(x) + n (i-1) + (j-1) // n is no. of columns
2. Column Major order
b. Column Major order
x(i,j) = base(x) + m (j-1) + (i-1) // m is no. of rows
For example an array having the following data elements
in 3 x 3 matrix:
x[ 3 ] [ 3 ] = 10 20 30
11 22 33
55 66 77
2-D array representation in memory
Row by Row traversing.
60 61 62 63 64 65 66 67 68
10 20 30 11 22 33 55 66 77
1,1 1,2 1,3 2,1 2,2 2,3 3,1 3,2 3,3
Find the location for 55, we have
x(i,j) = base(x) + n (i-1) + (j-1)
x(3,1) = 60 + 3 * (3-1) + (1-1)
= 60 + 3 * (2) + (0)
= 60 + 6
= 66
At 66 location the value can be retrieved.
2-D array representation in memory
Column by Column traversing.
60 61 62 63 64 65 66 67 68
10 11 55 20 22 66 30 33 77
1,1 2,1 3,1 1,2 2,2 3,2 1,3 2,3 3,3
Find the location for 33, we have
x(i,j) = base(x) + m (j-1) + (i-1)
x(2,3) = 60 + 3 * (3-1) + (2-1)
= 60 + 3 * (2) + (1)
= 60 + 6 + 1
= 67
At 66 location the value can be retrieved.
Array - Based Lists
• List: A collection of elements of the same type.
• The length of a list is the number of elements in the list.
• The List is among the most generic of data structures
Real life:
a. shopping list,
b. groceries list,
c. list of people to invite to dinner
d. List of presents to get
Array - Based Lists
A list is collection of items that are all of the same type
(grocery items, integers, names)
The items, or elements of the list, are stored in some
particular order
It is possible to insert new elements into various positions
in the list and remove any element of the list
Array - Based Lists
List is a set of elements in a linear order.
For example, data values x1, x2, x3, x4 can be arranged in
a list:
(x3, x1, x2, x4)
In this list, x3, is the first element, x1 is the second
element, and so on
The order is important here; this is not just a random
collection of elements, it is an ordered collection
List Operations
Useful operations
• createList(): create a new list (presumably empty)
• copy(): set one list to be a copy of another
• clear(); clear a list (remove all elments)
• insert(X, ?): Insert element X at a particular position
in the list
• remove(?): Remove element at some position in
the list
• get(?): Get element at a given position
• update(X, ?): replace the element at a given position
with X
• find(X): determine if the element X is in the list
• length(): return the length of the list.
List Operations
If we use the “current” marker, the following four
methods would be useful:
start(): moves to “current” pointer to the very first
element.
tail(): moves to “current” pointer to the very last
element.
next(): move the current position forward one
element
back(): move the current position backward one
element
Lists Implementation
We have designed the interface for the List; we now
must consider how to implement that interface.
Implementing Lists using an array: for example, the list
of integers (2, 6, 8, 7, 1) could be represented as:
current size
A 2 6 8 7 1
3 5
1 2 3 4 5
List Implementation
add(9); current position is 3. The new list would thus
be: (2, 6, 8, 9, 7, 1)
We will need to shift everything to the right of 8 one
place to the right to make place for the new element ‘9’.
current size
step 1: A 2 6 8 7 1
3 5
1 2 3 4 5 6
step 2: A current size
2 6 8 9 7 1
4 6
1 2 3 4 5 6
notice: current points
to new element
Lists Implementation
next():
current size
A 2 6 8 9 7 1
4 6
1 2 3 4 5 6 5
Lists Implementation
There are special cases for positioning the
current pointer:
a. past the last array cell
b. before the first cell
Lists Implementation
remove(): removes the element at the current
index
current size
Step 1: A 2 6 8 9 1
5 6
1 2 3 4 5 6
5
current size
Step 2: A 2 6 8 9 1
5 5
1 2 3 4 5
We fill the blank spot left by the removal of 7 by
shifting the values to the right of position 5 over to the left
one space.
Lists Implementation
Other operations:
get() return A[current];
update(X) A[current] = X;
length() return size;
back() current--;
start() current = 1;
end() current = size;
Analysis of Array Lists
add
we have to move every element to the right of current to
make space for the new element.
Worst-case is when we insert at the beginning; we have to
move every element right one place.
Average-case: on average we may have to move half of
the elements
remove
Worst-case: remove at the beginning, must shift all
remaining elements to the left.
Average-case: expect to move half of the elements.
find
Worst-case: may have to search the entire array
Average-case: search at most half the array.
Other operations are one-step.
Time Complexity of List Operations
Searching in Arrays (Sequential Search)
Finding required data in arrays, also called linear search.
Algorithm steps
•Visit the first element of array and compare its value with the
required value.
•If matches, search is completed.
•If does’nt match, move to the next element of array and repeat the
same process.
Note: You are required to write Java code for above algorithm
Exercise:
Write a Java code in which one can insert an element
at the location specified by the user.
10 20 30 40 50
Enter location. 2
The element to be inserted is: 99
Output: 10 20 99 30 40 50
// You are also required to delete the specific
element in the array
