DATA STRUCTURES - COMPLETE NOTES

Subject: Computer Science (CS301)

Topic: Data Structures and Algorithms
Prepared by: Student Study Group

CHAPTER 1: INTRODUCTION TO DATA STRUCTURES

A data structure is a way of organizing and storing data in a computer so that it can be accessed and
modified efficiently. Different data structures are suited to different kinds of applications, and some are
highly specialized for specific tasks.

The choice of data structure depends on:

1. The type of data to be stored

2. The operations to be performed (search, insert, delete)

3. The memory available

4. The time complexity requirements

CHAPTER 2: ARRAYS
An array is a collection of elements stored at contiguous memory locations. It is the simplest and most
widely used data structure.

Properties of Arrays:

• Fixed size (static allocation)

• Elements are stored sequentially in memory
• Random access in O(1) time using index
• Insertion and deletion at arbitrary positions takes O(n) time
Types of Arrays:

1. One-dimensional array: A linear list of elements (e.g., int arr[10])

2. Two-dimensional array: A matrix or table (e.g., int matrix[3][4])

3. Multi-dimensional array: Arrays of arrays

Time Complexity of Array Operations:

• Access: O(1)
• Search: O(n) for linear search, O(log n) for binary search on sorted array
• Insertion at end: O(1) amortized
• Insertion at arbitrary position: O(n)
• Deletion: O(n)
Applications of Arrays:
 • Storing marks of students
• Image processing (pixel arrays)
• Matrix multiplication
• Implementation of other data structures (stacks, queues)

CHAPTER 3: LINKED LISTS

A linked list is a linear data structure where each element (called a node) contains data and a pointer to
the next node in the sequence.

Unlike arrays, linked lists do not store elements in contiguous memory locations. Each node contains:

• Data field: stores the actual value

• Next pointer: stores the address of the next node
Types of Linked Lists:

1. Singly Linked List

• Each node has one pointer pointing to the next node
• Last node points to NULL
• Traversal is only in one direction
• Example: 10 -> 20 -> 30 -> 40 -> NULL

2. Doubly Linked List

• Each node has two pointers: one to the next node and one to the previous node
• Allows traversal in both directions
• More memory usage per node
• Example: NULL <- 10 <-> 20 <-> 30 -> NULL

3. Circular Linked List

• Last node points back to the first node
• No NULL at the end
• Useful for round-robin scheduling
Operations on Linked List:

• Insertion at beginning: O(1)

• Insertion at end: O(n) for singly, O(1) for doubly with tail pointer
• Deletion: O(n)
• Search: O(n)
Advantages of Linked Lists over Arrays:

• Dynamic size (can grow or shrink at runtime)

• Efficient insertion and deletion at the beginning
• No memory wastage due to pre-allocation
Disadvantages:

• No random access (must traverse from the beginning)

• Extra memory for pointers
 • Cache performance is worse than arrays

CHAPTER 4: STACKS
A stack is a linear data structure that follows the Last In First Out (LIFO) principle. The element inserted
last is the first one to be removed.

Think of a stack of plates: you add plates on top and remove from the top.

Primary Operations:

1. Push: Add an element to the top of the stack

2. Pop: Remove the top element from the stack

3. Peek/Top: View the top element without removing it

4. isEmpty: Check if the stack is empty

5. isFull: Check if the stack is full (for array implementation)

All stack operations run in O(1) time.

Applications of Stack:

• Function call management (call stack in programming)

• Undo/Redo operations in editors
• Expression evaluation (infix to postfix conversion)
• Backtracking algorithms (maze solving, DFS)
• Browser's back button
• Syntax checking (matching parentheses)
Example - Balanced Parentheses Check:

Given string: "{ [ ( ) ] }"

Step 1: Push '{' → Stack: {

Step 2: Push '[' → Stack: { [

Step 3: Push '(' → Stack: { [ (

Step 4: ')' found, pop '(' → Stack: { [

Step 5: ']' found, pop '[' → Stack: {

Step 6: '}' found, pop '{' → Stack: empty

Result: Balanced!

CHAPTER 5: QUEUES
A queue is a linear data structure that follows the First In First Out (FIFO) principle. The element
inserted first is the first one to be removed.

Think of a queue at a ticket counter: the person who arrives first gets served first.

Primary Operations:
1. Enqueue: Add an element at the rear of the queue

2. Dequeue: Remove an element from the front of the queue

3. Front: Get the front element

4. Rear: Get the rear element

5. isEmpty: Check if the queue is empty

Types of Queues:

1. Simple Queue: Basic FIFO queue

2. Circular Queue: Rear connects back to front to reuse empty spaces

3. Priority Queue: Elements are dequeued based on priority, not arrival order

4. Double-ended Queue (Deque): Elements can be added/removed from both ends

Applications of Queue:
• CPU scheduling (Round Robin)
• Printer spooling
• BFS (Breadth First Search) algorithm
• Handling of requests on a web server
• Call center phone systems

CHAPTER 6: TREES
A tree is a non-linear hierarchical data structure consisting of nodes connected by edges. Unlike linked
lists, trees are not linear — they have a root node at the top and child nodes branching below.

Key Terminology:

• Root: The topmost node (has no parent)

• Parent: A node that has child nodes
• Child: Nodes directly connected below a parent
• Leaf: A node with no children
• Height: The length of the longest path from root to a leaf
• Depth: The distance from root to a given node
• Degree: Number of children of a node
Binary Tree:

A tree where each node has at most two children, called left child and right child.

Types of Binary Trees:

1. Full Binary Tree: Every node has 0 or 2 children

2. Complete Binary Tree: All levels are completely filled except possibly the last level

3. Perfect Binary Tree: All internal nodes have 2 children and all leaves are at the same
level
4. Balanced Binary Tree: Height is O(log n)
Binary Search Tree (BST):

A binary tree with the property:

• Left subtree contains nodes with keys less than the parent
• Right subtree contains nodes with keys greater than the parent
BST Operations:

• Search: O(log n) average, O(n) worst case

• Insert: O(log n) average
• Delete: O(log n) average
Tree Traversals:

1. Inorder (Left, Root, Right): Gives sorted output for BST

2. Preorder (Root, Left, Right): Used for copying a tree

3. Postorder (Left, Right, Root): Used for deleting a tree

CHAPTER 7: HASHING
Hashing is a technique that maps data of arbitrary size to fixed-size values (hash values or hash codes)
using a hash function. It enables O(1) average time for search, insert, and delete operations.

Hash Function: A function that converts a key to an index in the hash table.

A good hash function should be:

• Fast to compute
• Distribute keys uniformly across the table
• Minimize collisions
Collision: When two different keys map to the same index in the hash table.

Collision Resolution Techniques:

1. Chaining: Each index in the table stores a linked list of all elements with the same
hash value

2. Open Addressing: Find another empty slot in the table using probing
• Linear Probing: Check next slot sequentially
• Quadratic Probing: Check slots at quadratic distances
• Double Hashing: Use a second hash function to find the next slot
Applications of Hashing:

• Database indexing
• Implementing hash maps (Python dict, Java HashMap)
• Password storage (cryptographic hashing)
• Caches (e.g., DNS cache)
• Detecting duplicate records
IMPORTANT FORMULAS & COMPLEXITIES
Data Structure | Access | Search | Insert | Delete

Array | O(1) | O(n) | O(n) | O(n)

Linked List | O(n) | O(n) | O(1) | O(1)

Stack | O(n) | O(n) | O(1) | O(1)

Queue | O(n) | O(n) | O(1) | O(1)

BST (average) | O(log n)| O(log n)| O(log n)| O(log n)

Hash Table (avg) | N/A | O(1) | O(1) | O(1)

END OF NOTES - Data Structures (CS301)