Data Structures and Algorithms - EE 390
Chapter 5
Linear Data Structures
Dr. Anirban Dasgupta
Assistant Professor
Department of Electronics And Electrical Engineering, IIT Guwahati
Data Structures - Types
Integer Array
Float
Data structures
Primitive
Character Linked List
Boolean
Stack
Linear
Queue
Non-primitive
Hash Table
Tree
Non-linear
Graph
Department of Electronics And Electrical Engineering, IIT Guwahati
Data Structures - Operations
Accessing Searching Inserting Deleting
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 the
X(4)
first element of array
Complexity of accessing is O(1)
Department of Electronics And Electrical Engineering, IIT Guwahati
Department of Electronics And Electrical Engineering, IIT Guwahati
Array Searching Operations
Unsorted array elements are
searched for a target using linear
search 5 7 3 8 1
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 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: 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 List vs Array
Arrays Linked lists
• Store elements in contiguous memory • Elements are usually not stored in contiguous
locations, resulting in easily calculable locations, hence they need to be stored with
addresses for the elements stored additional tags giving a reference to the next
• Allows faster access to an element at a 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.
Line for a cashier
Doubly Linked List.
Browser cache
Circular Linked List.
Multiplayer games
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
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 examples
• 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. The items are
removed in the reversed order in which they are
pushed. If the stack is empty, then it is said to be
an 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 3
Push(8)
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
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
enqueue(), dequeue() 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
Dequeue() 2 9 4 8 3
Dequeue() 2 9 4 8
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
Department of Electronics And Electrical Engineering, IIT Guwahati
Method 2: Making Pop costly
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
push() takes O(1) time. pop() 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
push() takes O(n) time. pop() 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
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
