Data Structure &
Algorithms
Mashal Tariq
Contents:
1. Data Structures
2. Types of Data Structure
3. Linear Data Structure
4. Types of Linear Data Structure
5. Array
6. Stack
1. Data Structure:
• Data structure is a storage that is used to store and
organize data.
• It is a way of arranging data on a computer so that it can
be accessed and updated efficiently.
• Depending on the requirement and project, it is important
to choose the right data structure for the project.
Note: Data structure and Data types are slightly
different. Data structure is the collection of data
types arranged in a specific order.
Types of Data Structure
Basically, data structures are divided into two categories:
• Linear data structure
• Non-linear data structure
Linear data structures
• In linear data structures, the elements are arranged in sequence one
after the other.
• Since elements are arranged in particular order, they are easy to
implement.
• However, when the complexity of the program increases, the linear data
structures might not be the best choice because of operational
complexities.
• Performance Bottlenecks: For example, inserting an element in the
middle of an array requires shifting all subsequent elements, which is
time-consuming.
Types of Linear data structures
1. Array
2. Stack
3. Queue
4. Linked List
Arrays
• Fundamental data structures in computer science and programming.
• They provide a way to store and organize multiple elements of the
same type in a contiguous block of memory.
• In array, where each element can be accessed using an index or
position within the array.
• The index starts from zero for the first element and increments by one
for each subsequent element.
• This zero-based indexing allows for direct and constant-time access to
any element in the array.
Types of arrays:
One-Dimensional Array:
• This is the simplest form of an array, which consists of a single row of
elements, all of the same data type. Elements in a 1D array are
accessed using a single index.
Two-Dimensional Array:
• A two-dimensional array, often referred to as a matrix or 2D array, is
an array of arrays. It consists of rows and columns, forming a grid-like
structure. Elements in a 2D array are accessed using two indices, one
for the row and one for the column.
• Multi-Dimensional Array:
Arrays can have more than two dimensions, leading to multi-
dimensional arrays. These are used when data needs to be organized in
a multi-dimensional grid.
Types of Array operations:
• Accessing Elements: Accessing a specific element in an array by its index
is a constant-time operation. It has a time complexity of O(1).
• Insertion: Appending an element to the end of an array is usually a
constant-time operation, O(1) but insertion at the beginning or any
specific index takes O(n) time because it requires shifting all of the
elements.
• Deletion: Same as insertion, deleting the last element is a constant-time
operation, O(1) but deletion of element at the beginning or any specific
index takes O(n) time because it requires shifting all of the elements.
• Searching: Linear Search takes O(n) time which is useful for unsorted
data and Binary Search takes O(logn) time which is useful for sorted data.
Applications of Array:
• Arrays are widely used for various purposes, such as storing
collections of numbers, strings, or objects.
• They are employed in a wide range of applications, including sorting
and searching algorithms, dynamic programming, graph algorithms,
and many more.
2. Stack Data Structure:
In stack data structure, elements are stored in
the LIFO principle. That is, the last element
stored in a stack will be removed first.
In a stack, operations can be perform only from one end (top here).
Basic Operations of Stack
• Push: Add an element to the top of a stack
• Pop: Remove an element from the top of a stack
• IsEmpty: Check if the stack is empty
• IsFull: Check if the stack is full
• Peek: Get the value of the top element without removing it
Working of Stack Data Structure
• A pointer called TOP is used to keep track of the top element in the
stack.
• When initializing the stack, we set its value to -1 so that we can check
if the stack is empty by comparing TOP == -1.
• On pushing an element, we increase the value of TOP and place the
new element in the position pointed to by TOP.
• On popping an element, we return the element pointed to by TOP and
reduce its value.
• Before pushing, we check if the stack is already full
• Before popping, we check if the stack is already empty
Types of Stacks:
Fixed Size Stack:
• As the name suggests, a fixed size stack has a fixed size and cannot
grow or shrink dynamically. If the stack is full and an attempt is made
to add an element to it, an overflow error occurs. If the stack is empty
and an attempt is made to remove an element from it, an underflow
error occurs.
• Dynamic Size Stack:
• A dynamic size stack can grow or shrink dynamically. When the stack is
full, it automatically increases its size to accommodate the new
element, and when the stack is empty, it decreases its size. This type of
stack is implemented using a linked list, as it allows for easy resizing of
the stack.
Stack Time Complexity
For the array-based implementation of a stack, the
push and pop operations take constant time, i.e. O(1).
3. Queue:
Unlike stack, the queue
data structure works in
the FIFO principle where
first element stored in the
queue will be removed
first.
In a queue, addition and removal are performed from separate ends.
Applications of Queue:
• CPU scheduling, Disk Scheduling
• When data is transferred asynchronously between two processes. The
queue is used for synchronization. For example: IO Buffers, pipes, file
IO, etc
• Handling of interrupts in real-time systems.
• Call Center phone systems use Queues to hold people calling them in
order.
4. Linked List
A linked list is a linear data structure that includes a
series of connected nodes. Here, each node stores the
data and the address of the next node.
Linked List Applications:
• Dynamic memory allocation
• Implemented in stack and queue
• In undo functionality of softwares
• Hash tables, Graphs
