Data Structures Theory Notes
This document covers Lists, Linked Lists, Stack, and Queue, including operations, differences, principles,
and key points for theory exams.
1. List (Array / Dynamic Array)
Topic Explanation / Logic
Definition A list is a collection of elements stored sequentially in memory.
Access Direct access possible by index (O(1)).
Inserting at the end is fast (O(1) amortized for dynamic arrays), but at beginning/
Insertion
middle requires shifting elements (O(n)).
Deletion Deleting an element requires shifting elements to fill the gap (O(n)).
Dynamic arrays expand automatically when full (usually double the size). Expansion
Expansion
involves creating a new larger array and copying old elements.
Advantages Fast access, simple implementation.
Disadvantages Slow insertion/deletion in middle or beginning, may waste memory after expansion.
Example Insert 5 at position 2 in [1,2,3,4] → [1,2,5,3,4] .
2. Linked List
Topic Singly Doubly Circular
Collection of nodes, each Each node has data, Last node points to first
Definition with data and a pointer to next, and previous node; can be singly or
the next node. pointer. doubly.
Sequential (O(n)) but
Access Sequential only (O(n)) Sequential only (O(n))
can traverse circularly
O(1) at beginning, O(n) at
O(1) at beginning or O(1) at beginning/end if
Insertion end/middle (unless tail
end if tail known tail known
known)
Same as singly, but
O(1) if node known; else Same as doubly, but
Deletion extra prev pointer
O(n) to search careful with circular link
update
1
Topic Singly Doubly Circular
Dynamic size, easy Easy forward/ Efficient rotation, can
Advantages
insertion/deletion backward traversal easily implement queue
No direct access, uses extra Extra memory for Complexity in
Disadvantages
memory (pointer) prev pointer managing circular link
Example Singly: 1->2->3->None
Doubly: 1<->2<-
>3<->None
Circular:
1->2->3->1
Other Key Points: - Detecting loop: Floyd’s cycle algorithm. - Insertion types: at beginning, at end, after a
specific node. - Deletion types: delete first, last, or a given node. - Reversal: iterative and recursive.
3. Stack
Topic Explanation / Logic
Principle LIFO – Last In, First Out.
Operations push (insert at top), pop (remove from top), peek/top (view top element).
Implementation Array or Linked List.
Insertion Always at top ( push ).
Deletion Always from top ( pop ).
Overflow Pushing on a full stack (array implementation).
Underflow Popping from an empty stack.
Advantages Easy to implement, fast insertion/deletion at top.
Disadvantages Limited access (top only).
Applications Undo/Redo, function call stack, expression evaluation, backtracking.
Example Push sequence: 5, 10, 15 → Stack top = 15; Pop → removes 15
2
4. Queue
Topic Explanation / Logic
Principle FIFO – First In, First Out.
Types Simple Queue (linear), Circular Queue, Deque, Priority Queue
Operations enqueue (insert at rear), dequeue (remove from front), peek/front
Insertion At rear ( enqueue )
Deletion From front ( dequeue )
Circular
Rear wraps to beginning; solves memory wastage problem.
Queue
Overflow Inserting into full queue.
Underflow Removing from empty queue.
Advantages Fair processing, easy to implement with arrays or linked lists.
Disadvantages Sequential access; linear queue wastes space unless circular.
Applications Print jobs, CPU scheduling, resource management, buffering.
Queue: [1,2,3] → Enqueue 4 → [1,2,3,4] ; Dequeue → removes 1 →
Example
[2,3,4]
5. Quick Differences
Feature List Linked List Stack Queue
Non- Non-contiguous Non-contiguous (if
Memory Contiguous
contiguous (if linked) linked)
Access Direct (index) Sequential Top only Front/Rear only
Insertion/ Expensive at middle/ Easy at any
Top only Front/Rear only
Deletion beginning position
Automatic in dynamic Dynamic by Stack grows/ Queue grows/
Expansion
array nature shrinks shrinks
Principle None None LIFO FIFO
Overflow/ Only dynamic arrays Push on full / Enqueue on full /
Not applicable
Underflow may need expansion Pop on empty Dequeue on empty
3
6. Important Notes for Exams
• Always mention LIFO/FIFO principle where applicable.
• Give real-life examples (Undo stack, Printer queue, Music playlist).
• Mention advantages/disadvantages and time complexity for insertion, deletion, access.
• Be ready to compare data structures in theory questions.
• Know types of linked lists and queue variations.
• Understand expansion, insertion, deletion, push/pop, enqueue/dequeue logically.
Prepared by: Emaan Fatima Date: 18-10-2025