Data Structures and Algorithms - EE 390

Module 1
Linear Data Structures

Dr. Anirban Dasgupta

Assistant Professor

Department of Electronics And Electrical Engineering, IIT Guwahati

Data Structures
Basic and advanced types of data structures, all
specialized format for

organizing designed to arrange data to suit a specific

purpose
processing
Data structures make it easy for users to access
and work with the data they need in appropriate
retrieving ways

A data structure may be selected or designed to

storing data store data for the purpose of using it with
various algorithms

Department of Electronics And Electrical Engineering, IIT Guwahati

Why are data structures important?
Enhanced Data Representation:
• Standard data types like integers or floating-point values often fall short in capturing complex logical
relationships in data processing.
• Data structures provide a more sophisticated means of organizing data, allowing for enhanced representation
and manipulation of information.

Logical Organization and Simplification:

• Applications dealing with data processing require a clear understanding of how data should be organized to
streamline processing.
• Data structures serve to organize data elements logically, simplifying operations like manipulation, storage, and
sharing of information.

Abstract Data Types as Building Blocks:

• Data structures amalgamate data elements into abstract data types, creating logical units that align with specific
algorithms or applications.
• For instance, an abstract data type like a "customer name" composed of individual strings for "first name,"
"middle name," and "last name" exemplifies how data structures form the building blocks of more complex data
representations.

Department of Electronics And Electrical Engineering, IIT Guwahati

Data Structures - Types
Array
Primitive Data
Types Linked List
Linear
Stack

Data structures
Integer
Queue
Float
Hash Table
Character
Boolean Non-linear Tree

Graph

Department of Electronics And Electrical Engineering, IIT Guwahati

Data Structures - Operations

Accessing Searching Inserting Deleting

Department of Electronics And Electrical Engineering, IIT Guwahati

 Arrays

Department of Electronics And Electrical Engineering, IIT Guwahati

Array Data Structure

An array is a collection of items stored at contiguous memory locations.

The idea is to store multiple items of the same type together.

This makes it easier to calculate the position of each element by simply adding an
offset to a base value

Department of Electronics And Electrical Engineering, IIT Guwahati

Array Data Structure

Department of Electronics And Electrical Engineering, IIT Guwahati

Array Operations

Accessing • O(1)

Searching • O(n)

Inserting • O(n)

Deleting • O(n)

Department of Electronics And Electrical Engineering, IIT Guwahati

 Array Accessing Operations
Array elements are accessed by
using an integer indices

Index starts with 0 and goes till size

of array minus 1. 0 1 2 3 4

X(2)
Name of the array is also a pointer to X(4)
the first element of array
Complexity of accessing is O(1)

Department of Electronics And Electrical Engineering, IIT Guwahati

Array Searching Operations

Unsorted array elements are

searched for a target using linear 5 7 3 8 1
search
0 1 2 3 4

Search for 3

Complexity of searching is O(n)

Department of Electronics And Electrical Engineering, IIT Guwahati

Array Insertion Operations
5 7 3 8 1
Insert operation is to insert an 0 1 2 3 4
element into a specific location
array.
5 7 6 3 8 1
0 1 2 3 4 5

Insert 6 at location 2

Complexity of inserting is O(n)

Department of Electronics And Electrical Engineering, IIT Guwahati

 Array Deleting Operations
Deletion can be either delete by 5 7 3 8 1
location or value
0 1 2 3 4

5 7 8 1
For delete by value in an unsorted 0 1 2 3
array, the element to be deleted is
searched using the linear search, and Delete 3
then delete operation is performed
followed by shifting the elements Complexity of deleting is O(n)

Department of Electronics And Electrical Engineering, IIT Guwahati

Linked Lists

Department of Electronics And Electrical Engineering, IIT Guwahati

Linked List Data Structure

A linked list is a linear A linked list consists of

data structure, in which The elements in a linked nodes where each node
the elements are not list are linked using contains a data field and a
stored at contiguous pointers reference(link) to the next
memory locations node in the list

Department of Electronics And Electrical Engineering, IIT Guwahati

Linked List Data Structure

Department of Electronics And Electrical Engineering, IIT Guwahati

 Linked List: Terminology
Link
Node Head Next
Hopping
• Basic building • This is the first node • Each link of a linked • Traversal of linked
blocks of a linked list • Nothing points to list contains a link to lists
• Each node has two this node the next link called • Also called pointer
components: Next hopping
• a data item • The last node points
• a reference to the to NULL
next node in the
list

Department of Electronics And Electrical Engineering, IIT Guwahati

 Linked Lists Operations

Accessing • O(n)

Inserting at beginning • O(1)

Inserting at end • O(n)

Deleting • O(n)

Department of Electronics And Electrical Engineering, IIT Guwahati

Linked List vs Array
Arrays Linked lists
• Store elements in contiguous memory • Elements are usually not stored in
locations, resulting in easily calculable contiguous locations, hence they need to
addresses for the elements stored be stored with additional tags giving a
• Allows faster access to an element at a reference to the next element
specific index • Slower memory access
• Size is fixed • Size is not fixed
• Memory usually allocated from stack • Memory usually allocated from heap
• For same no. of elements, less memory • For same no. of elements, more memory
required required
• Inserting new elements at start is expensive • Inserting new elements less expensive

Department of Electronics And Electrical Engineering, IIT Guwahati

Linked List Types

Singly Linked List

Doubly Linked List

Circular Linked List

Department of Electronics And Electrical Engineering, IIT Guwahati

Singly Linked List
Illustrations/Applications
1.Train
2. Playlist in Music Apps
3. Browser History
4. To-Do List
5. Library Book Checkout System
6. GPS Navigation Routes

Department of Electronics And Electrical Engineering, IIT Guwahati

 Doubly Linked List
a special type of linked list in which each node contains a pointer to the previous node as well as the
next node of the linked list

Advantages Applications
• can be traversed in both forward and backward directions 1. Web browsers for backward and forward
• delete operation is more efficient if a pointer to the node to navigation of web pages
be deleted is given 2. Cache are constructed using Doubly
• In a singly linked list, to delete a node, a pointer to the Linked Lists
previous node is needed. To get this previous node, 3. Maintain undo and redo functionalities
sometimes the list is traversed. In DLL, we can get the 4. Thread scheduler to keep track of processes
previous node using the previous pointer.
that are being executed at that time

Department of Electronics And Electrical Engineering, IIT Guwahati

 Circularly Linked List
a circularly linked list is a list that curves
back around and connects to itself
Two types:
• Circular singly linked list
• Circular doubly linked list

Applications
Advantages
1. Round-Robin Scheduling
• entire list can be traversed from any 2. Music and Media Players
node of the list 3. Simulations or games where objects
• saves time when we have to go to the interact in a circular
first node from the last node 4. Implementation of a Circular Buffer

Department of Electronics And Electrical Engineering, IIT Guwahati

 Circularly Doubly Linked List
• circular doubly linked list is a combination of the doubly linked list and
the circular linked list
• this linked list is bidirectional, contains two pointers and the last pointer
points to the first pointer

Department of Electronics And Electrical Engineering, IIT Guwahati

 Stacks

Department of Electronics And Electrical Engineering, IIT Guwahati

Stack Data Structure
• Stack is a linear data structure which follows a particular order in which the
operations are performed.
• The order may be LIFO (Last In First Out) or FILO (First In Last Out).

Department of Electronics And Electrical Engineering, IIT Guwahati

Stack - Real-life example
• Consider an example of plates stacked over one another in the
canteen.
• The plate which is at the top is the first one to be removed.
• The plate which has been placed at the bottommost position remains in
the stack for the longest period of time.
• So, it can be simply seen to follow LIFO (Last In First Out) / FILO
(First In Last Out) order.

Department of Electronics And Electrical Engineering, IIT Guwahati

Stack - Operations
Push
• Adds an item in the stack. If the stack is full,
then it is said to be an Overflow condition.
Pop
• Removes an item from the stack.
• Items removed in the reversed order in which
they are pushed.
• Popping empty stack leads to stack Underflow
condition.
Peek or Top
• Returns the top element of the stack.

isEmpty
• Returns true if the stack is empty, else false.
push(), pop(), peek() and isEmpty() all take O(1) time.
Department of Electronics And Electrical Engineering, IIT Guwahati
Applications of Stack
Redo-Undo Features
Evaluation of Arithmetic Expressions
Processing Function Calls
Forward and Backward Feature in Web Browsers
Backtracking
String Reversal
Department of Electronics And Electrical Engineering, IIT Guwahati
Implementation
array
implement
a stack
linked list

Array Implementation
Pros Cons
• Easy to implement. • It is not dynamic.
• Memory is saved as pointers • It doesn’t grow and shrink
are not involved. depending on needs at runtime.

Department of Electronics And Electrical Engineering, IIT Guwahati

Array Implementation - Push

-1
123405

0 1 2 3 4 5 Top

5 Push(4) 5 3 8 4
Push(5)

5 3 Push(9) 5 3 8 4 9
Push(3)

5 3 8 Push(2) 5 3 8 4 9 2
Push(8)

Push(6)
Department of Electronics And Electrical Engineering, IIT Guwahati Stack Overflow
Array Implementation - Pop

435

0 1 2 3 4 5 Top

5 3 8 4 9 2

Pop() 5 3 8 4 9

Pop() 5 3 8 4

Department of Electronics And Electrical Engineering, IIT Guwahati

 Reversing a String with a Stack

• Push all the characters onto the stack.

• Pop all the characters onto the stack.

STRESSED D D E S S E R T S
E
S
S
E
R
T
S

Department of Electronics And Electrical Engineering, IIT Guwahati

Monotonic Stack
• A monotonic stack is a stack whose elements are monotonically
increasing or decreasing.
• It contains all qualities that a typical stack has and its elements are all
monotonic decreasing or increasing.
• There are 2 types of monotonic stacks:
• Monotonic Increasing Stack
• Monotonic Decreasing Stack
• Monotonic stacks are generally used for solving questions of the type
- next greater element, next smaller element, previous greater element
and previous smaller element.

Department of Electronics And Electrical Engineering, IIT Guwahati

Monotonic Stack Creation
Push the second
Start with an Enter the first Else keep
element if its
empty stack element popping
greater than top

Monotonic Increasing Stack

Department of Electronics And Electrical Engineering, IIT Guwahati

Infix, Postfix and Prefix Notation

• Infix, Postfix and Prefix notations are three different but equivalent ways of
writing expressions.
• Infix notation: Operators are written in-between their operands.
• X+Y
• A* ( B+C) /D X Y operands
+ operator
• Postfix notation: Operators are written after their operands.
• XY+
• ABC+* D /
• Prefix notation: Operators are written before their operands.
• +XY
• /*A+BCD
Department of Electronics And Electrical Engineering, IIT Guwahati
Conversion Using Stacks

Department of Electronics And Electrical Engineering, IIT Guwahati

 Queues

Department of Electronics And Electrical Engineering, IIT Guwahati

Queue Data Structure
• The order is First In First Out (FIFO).
• Insertion occurs strictly at one end called rear or tail
• Deletion occurs strictly at the other end called front or head
• A good example of a queue is any queue of consumers for a resource where the consumer that
came first is served first.

Department of Electronics And Electrical Engineering, IIT Guwahati

Difference between Stack and Queue

Department of Electronics And Electrical Engineering, IIT Guwahati

Operations on Queue

Enqueue • Insert at rear or tail

Dequeue • Remove at front or head

• Returns value of the front node of the

Peek queue, without removing it
enqueue(), dequeue(), peek() all take O(1) time
Department of Electronics And Electrical Engineering, IIT Guwahati
Array Implementation – Enqueue

-1
123405

0 1 2 3 4 5 Peek /
Front

5 Enqueue(4) 4 8 3 5
Enqueue(5)

3 5 Enqueue(9) 9 4 8 3 5
Enqueue(3)

8 3 5 Enqueue(2) 2 9 4 8 3 5
Enqueue(8)

Department of Electronics And Electrical Engineering, IIT Guwahati

Array Implementation – Dequeue or Pop

435

0 1 2 3 4 5 Peek /
Front

2 9 4 8 3 5 • Queue overflow results from

trying to add an element onto a
Dequeue()
full queue
2 9 4 8 3
• Queue underflow happens when
trying to remove an element from
Dequeue() 2 9 4 8 an empty queue
Department of Electronics And Electrical Engineering, IIT Guwahati
Implement Stack using Queues
Problem:
• given a queue data structure with Enqueue and Dequeue operations
• the task is to implement a stack using instances of queue data structure and
operations on them

Solution:
A stack can be implemented using two queues
Let stack to be implemented be s and queues used to implement s be q1 and q2.
s can be implemented in two ways

Department of Electronics And Electrical Engineering, IIT Guwahati

 Method 1: Making Push costly
Push O(n), Pop O(1)

Department of Electronics And Electrical Engineering, IIT Guwahati

 Method 2: Making Pop costly
Push O(1), Pop O(n)

Department of Electronics And Electrical Engineering, IIT Guwahati

Implement Queue using Stacks
Problem:
given a stack data structure with Push and Pop operations
the task is to implement a queue using instances of stack data structure and
operations on them

Solution:
• A queue can be implemented using two stacks.
• Let queue to be implemented be q and stacks used to implement q be s1 and s2.
• q can be implemented in two ways

Department of Electronics And Electrical Engineering, IIT Guwahati

 Method 1: Making Dequeue costly
If this was a q 5 4 3 2 1
To perform an enqueue
operation

s1 5 4 3 2 1 s1 4 3 2 1
• Push the element to
be added to stack1
s2 s2 5
To perform dequeue
operation
s1 3 2 1 s1 1

• Push all the elements

from stack1 to
s2 4 5 s2 2 3 4 5 stack2.
• Pop and return the
element from the
enqueue() takes O(1) time. dequeue() takes O(n) time.
stack2
Department of Electronics And Electrical Engineering, IIT Guwahati
 Method 2: Making Enqueue costly
If this was a q 5 4 3 2 1
To perform an enqueue
operation

s1 1 s1 • Push all the elements

from stack1 to
stack2.
• Push the new
s2 s2 1 element to stack2.
• Pop all the elements
from stack2 to
stack1.
s1 2 s1
To perform dequeue
operation
s2 1 s2 2 1
• Pop and return the
enqueue() takes O(n) time. dequeue() takes O(1) time. element from stack1.

Department of Electronics And Electrical Engineering, IIT Guwahati

 Method 2: Making Enqueue costly
If this was a q 5 4 3 2 1
To perform an enqueue
operation

s1 2 1 s1 3 • Push all the elements

from stack1 to
stack2.
• Push the new
s2 s2 2 1 element to stack2.
• Pop all the elements
from stack2 to
stack1.
s1 1 2 3 s1 1 2 3 4 5
To perform dequeue
operation
s2 s2
• Pop and return the
push() takes O(n) time. pop() takes O(1) time. element from stack1.

Department of Electronics And Electrical Engineering, IIT Guwahati

Circular Queue
• extended version of a normal queue where the
last element of the queue is connected to the
first element of the queue forming a circle
• operations are performed based on FIFO
principle
• also called ‘Ring Buffer’
• In a normal Queue, we can insert elements until
queue becomes full. But once queue becomes
full, we can not insert the next element even if
there is a space in front of queue.

Department of Electronics And Electrical Engineering, IIT Guwahati

Circular Queue Illustration

Department of Electronics And Electrical Engineering, IIT Guwahati

Double Ended Queue
• allows insert and delete at both ends
• applied as both stack and queue, as it supports both
operations

Department of Electronics And Electrical Engineering, IIT Guwahati

Double Ended Queue Methods
Operation Description Time Complexity
push_front() Inserts the element at the beginning. O(1)
push_back() Adds element at the end. O(1)
pop_front() Removes the first element from the deque. O(1)
pop_back() Removes the last element from the deque. O(1)
front() Gets the front element from the deque. O(1)
back() Gets the last element from the deque. O(1)
empty() Checks whether the deque is empty or not. O(1)
size() Determines the number of elements in the deque. O(1)

Department of Electronics And Electrical Engineering, IIT Guwahati

 Priority Queue
• Type of queue that arranges elements based on their priority values
• Each element in a priority queue has an associated priority

Department of Electronics And Electrical Engineering, IIT Guwahati

References
• Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 3rd
edition, The MIT Press, McGraw-Hill, 2001.
• C. Cherniavsky and J. A. Storer, An Introduction to Data Structures and
Algorithms, 2nd edition. Birkhauser Boston, 2001.

Department of Electronics And Electrical Engineering, IIT Guwahati