Data Structures and Algorithms

(ESO207A)

Lecture 9
Data structures:
• Modeling versus Implementation
• Abstract data type “List” and its implementation

1
 Data Structure

Definition:
A collection of data elements arranged and connected in a way
that can facilitate efficient executions
of a (potentially long) sequence of operations.

2
 Two steps process for designing
a Data Structure
Step 1: Mathematical Modeling
A Formal description of the possible operations of a data structure.
Operations can be classified into two categories:
Query Operations: Retrieving some information from the data structure
Update operations: Making a change in the data structure

Outcome of Mathematical Modeling: an Abstract Data Type

Step 2: Implementation
Explore the ways of organizing the data that facilitates
performing each operation efficiently using the existing tools available.
Since we don’t specify here the way
how each operation of the data
structure will be implemented3
MODELING OF LIST

OUTCOME WILL BE:

ABSTRACT DATA TYPE “LIST”

4
 Mathematical Modeling of a List

• List of Roll numbers passing a course. What is common in

all these examples ?
• List of Criminal cases pending in High Court.
• List of Rooms reserved in a hotel.
• List of Students getting award in IITK convocation 2022.

Inference: List is a sequence of elements.

L: , , …, , , …,

th element of list L

5
 Query Operations on a List
• IsEmpty(L): determine if L is an empty list. The type of this parameter
• Search(x,L): determine if x appears in list L. will depend on the implementation

• Successor(p,L):
return the element of list L which succeeds/follows the element at location p.
Example:
If L is , , …, , , …, and p is location of element ,
then Successor(p,L) returns ?? 𝑎 𝑖+1 .
• Predecessor(p,L):
Return the element of list L which precedes (appears before) the element at
location p.

Other possible operations:

• First(L):
return the first element of list L.
• Enumerate(L):
Enumerate/print all elements of list L in the order they appear.
6
 Update Operations on a List
• CreateEmptyList(L): Create an empty list.
• Insert(x,p,L): Insert x at a given location p in list L.
Example: If L is , …, , , …, and p is location of element ,
then after Insert(x,p,L), L becomes
, ??
…, , ,…,

• Delete(p,L): Delete element at location p in L

Example: If L is , …, , , …, and p is location of element ,
then after Delete(p,L), L becomes
??
, …, ,…,

• MakeListEmpty(L): Make the List L empty.

7
 IMPLEMENTATION OF
ABSTRACT DATA TYPE “LIST”

8
 Array based Implementation
CSE students will learn about it perhaps in
CS220 or some later course on Hardware.
• RAM allows O() time to access any
Array A
memory location.
• Array is a contiguous chunk of
memory kept in RAM.
• For an array A[] storing words,
the address of element A[] =
“start address of array A” +

How can we use array

for implementing a
This featurelist?
supports O() RAM
time to access A[] for any

9
 Array based Implementation
• Store the elements of List in array A such that
A[] denotes ?()th element of the list at each stage
(since index starts from ).
(Assumption: The maximum size of list is known in advance.)
• Keep a integer variable Length to denote the number of elements in the
list at each stage.

Example: If at any moment of time List is 3,5,1,8,0,2,40,27,44,67,

then the array A looks like:

A 3 5 1 8 0 2 40 27 44 67 Length = 10

Question: How to describe location of an element of the list ?

Answer: by the corresponding array index. Location of 5th element of List is 4.10
Insert(,,L)
𝒊

𝟐 𝟒𝟎 𝟐𝟕 𝟒𝟒 𝟔𝟕 𝟕 𝟏𝟏

11
Insert(,,L)
𝒊

𝒙 𝟐 𝟒𝟎 𝟐𝟕 𝟒𝟒 𝟔𝟕 𝟕 𝟏𝟏

12
Delete(,L)
𝒊

𝟐 𝟒𝟎 𝟐𝟕 𝟒𝟒 𝟔𝟕 𝟕 𝟏𝟏

13
Delete(,L)
𝒊

𝟐 𝟒𝟎 𝟐𝟕 𝟒𝟒 𝟔𝟕 𝟕 𝟏𝟏

14
 Time Complexity of each List operation using
Array based implementation
Operation Time Complexity per operation
IsEmpty(L) O(1)
Search(x,L) : number of elements
O() in list at present
Successor(,L)
O(1)
Predecessor(,L)
O(1)
CreateEmptyList(L)
O(1)
Arrays are very rigid Insert(x,,L)
O()
Delete(,L)
O()
MakeListEmpty(L)
O(1)

Homework: Write C Function for each

operation with matching time complexity.
16
 Link based Implementation:
Address of previous (left) node
Head

node

Value

Address of next (or right) node

Doubly Linked List

Singly Linked List

17
 Doubly Linked List based Implementation
• Keep a doubly linked list
where elements appear in the order we follow while traversing the list.
• The location of an element : the address
? of the node containing it.

Example: List 3,9,1 appears as

Head

3 9 1

18
 How to perform Insert(x,p,L) ?

Head p

3 9 1

How is it done actually ?

19
 How to perform Insert(x,p,L) ?

Head temp p

3 9 1

Insert(x,p,L){
q new(node); x
q.value x;
temp p.left;
q.right  p;
q
O() time
p.left q;
q.left  temp; Lists are very flexible
temp.right q; Homework: How to perform Delete(x,p,L) ?
}

20
Some students were interpreting the parameter p in Insert(x,p,L) with the integer
signifying the order (1st, 2nd,…) at which element x is to be inserted in list L.
Based on this interpretation, they felt that Insert(x,p,L) will require scanning the list
and hence will take time of the order of p and not O().

Here is my advice:
Please refer to the modeling of the list for exact interpretation of p.
The implementation in the lecture is for that modeling and indeed takes O() time.
However, if you wish to model list differently such that the parameter p is an integer
parameter as defined above, then you are right.
Lesson learnt:
Implementation of a data structure
depends upon its mathematical modeling (interpretation of various operations).

21
 How to perform successor(p,L) ?

Head p

p.right

3 9 1

Successor(p,L){
q p.right;
return q.value;
}

22
Time Complexity of each List operation using
Doubly Linked List based implementation
Operation Time Complexity per
operation
IsEmpty(L)
O(1)
Search(x,L)
O()
Successor(p,L) O(1)
Predecessor(p,L) O(1) It takes O(1) time if we
CreateEmptyList(L) implement it by setting the
O(1) head pointer of list to
Insert(x,p,L) NULL. However, if one has
O(1) to free the memory used
by the list, then it will
Delete(p,L)
O(1) require traversal of the
entire list and hence O(n)
MakeListEmpty(L)
O(1) time. You might learn
more about it in Operating
System course.

Homework: Write C Function for each

operation with matching complexity.
23
Doubly Linked List based implementation versus array
based implementation of “List”
Operation Time Complexity per Time Complexity per
operation for array based operation for doubly linked
implementation list based implementation

IsEmpty(L) O(1) O(1)

Search(x,L) O() O()
Successor(p,L) O(1) O(1)
Predecessor(p,L) O(1) O(1)
CreateEmptyList(L) O(1) O(1)
Insert(x,p,L) O() O(1)
Delete(p,L) O() O(1)
MakeListEmpty(L) O(1) O(1)

24
A CONCRETE PROBLEM

25
 Problem
Maintain a telephone directory Array based Linked list based
Operations: solution solution
• Search the phone # of a person with name x
LogO() O()

• Insert a new record (name, phone #,…) O() O()

Yes. Keep the array sorted

according to the names and
Can do
we improve it ? Think over it …
Binary search for x.

Can we achieve the best of the two

data structures simultaneously ?

We shall together invent such a novel data structure in the next class
26
 Important Advice
• Pointers and linked lists in C are very important topics. A brief
document containing material on these topics on www and
some practice problems was posted on the course website
(under Section “”Additional Supporting Material of the
Course”)

• We also had an optional session yesterday conducted by 2

tutors.

• You must acquire good command on these topics, and then…

• make sincere attempts on designing the data structure which

is better than arrays and doubly linked lists for the problem
discussed in today’s lecture. 27