This repository contains educational C++ implementations of various data structures for teaching purposes.
Files
Linked Lists
- singly_linked_list.cpp - Single/Singly Linked List
- doubly_linked_list.cpp - Doubly Linked List
- circular_linked_list.cpp - Circular Linked List
Stack
- stack_array.cpp - Stack (Array-based Implementation)
- stack_linked_list.cpp - Stack (Linked List-based Implementation)
Queue
- queue_array.cpp - Queue (Array-based Implementation)
- queue_linked_list.cpp - Queue (Linked List-based Implementation)
Double-ended Queue (Deque)
- deque_array.cpp - Deque (Array-based Implementation)
- deque_linked_list.cpp - Deque (Linked List-based Implementation)
Features
Each implementation includes:
- Node Structure: Clear definition of the node structure
- Basic Operations:
- Insert at beginning
- Insert at end
- Insert at position
- Delete by value
- Delete at position
- Search
- Display
- Get size
- Additional Operations:
- Reverse (for singly and doubly linked lists)
- Forward/Backward display (for doubly linked list)
- Circular verification (for circular linked list)
How to Compile and Run
Using g++:
# Compile singly linked list
g++ -o singly singly_linked_list.cpp
./singly
# Compile doubly linked list
g++ -o doubly doubly_linked_list.cpp
./doubly
# Compile circular linked list
g++ -o circular circular_linked_list.cpp
./circular
# Compile array-based stack
g++ -o stack_array stack_array.cpp
./stack_array
# Compile linked list-based stack
g++ -o stack_linked_list stack_linked_list.cpp
./stack_linked_list
# Compile array-based queue
g++ -o queue_array queue_array.cpp
./queue_array
# Compile linked list-based queue
g++ -o queue_linked_list queue_linked_list.cpp
./queue_linked_list
# Compile array-based deque
g++ -o deque_array deque_array.cpp
./deque_array
# Compile linked list-based deque
g++ -o deque_linked_list deque_linked_list.cpp
./deque_linked_list
Using clang++:
clang++ -o singly singly_linked_list.cpp
./singly
clang++ -o stack_array stack_array.cpp
./stack_array
Key Concepts
Singly Linked List
- Each node has data and a pointer to the next node
- Traversal is only in one direction (forward)
- Last node points to NULL
- Memory efficient but limited traversal
Doubly Linked List
- Each node has data, pointer to next node, and pointer to previous node
- Traversal in both directions (forward and backward)
- Takes more memory but offers more flexibility
- Better for operations that require backward traversal
Circular Linked List
- Similar to singly linked list, but last node points back to the first node
- No NULL pointer at the end
- Useful for round-robin scheduling and circular buffers
- Need to be careful with traversal to avoid infinite loops
Stack (Array-based)
- Uses a fixed-size array to store elements
- Simple and memory-efficient
- Fast operations (O(1) for push, pop, peek)
- Limited by array size (stack overflow)
- LIFO (Last In, First Out) principle
- Operations:
push(): Add element to top - O(1)pop(): Remove element from top - O(1)peek(): View top element without removing - O(1)isEmpty(): Check if stack is empty - O(1)isFull(): Check if stack is full - O(1)
Stack (Linked List-based)
- Uses dynamic memory allocation
- No size limitation (except system memory)
- More flexible than array-based
- Slightly more memory overhead (pointers)
- LIFO (Last In, First Out) principle
- Same operations as array-based stack
- All operations are O(1) time complexity
Queue (Array-based)
- Uses a fixed-size array with circular indexing
- Implements circular queue to avoid wasted space
- Simple and memory-efficient
- Fast operations (O(1) for enqueue, dequeue, peek)
- Limited by array size (queue overflow)
- FIFO (First In, First Out) principle
- Operations:
enqueue(): Add element to rear - O(1)dequeue(): Remove element from front - O(1)peek(): View front element without removing - O(1)isEmpty(): Check if queue is empty - O(1)isFull(): Check if queue is full - O(1)
Queue (Linked List-based)
- Uses dynamic memory allocation
- No size limitation (except system memory)
- More flexible than array-based
- Slightly more memory overhead (pointers)
- FIFO (First In, First Out) principle
- Same operations as array-based queue
- All operations are O(1) time complexity
- Uses both front and rear pointers for efficient operations
Double-ended Queue - Deque (Array-based)
- Uses a fixed-size array with circular indexing
- Allows insertion and deletion at both ends
- More flexible than regular queue
- Fast operations (O(1) for all operations)
- Limited by array size
- Operations:
insertFront(): Add element at front - O(1)insertRear(): Add element at rear - O(1)deleteFront(): Remove element from front - O(1)deleteRear(): Remove element from rear - O(1)getFront(): View front element - O(1)getRear(): View rear element - O(1)
Double-ended Queue - Deque (Linked List-based)
- Uses doubly linked list for bidirectional access
- No size limitation (except system memory)
- Most flexible implementation
- More memory overhead (two pointers per node)
- All operations are O(1) time complexity
- Supports forward and reverse traversal
- Can be used as both stack and queue
Teaching Tips
For Linked Lists:
- Start with Singly Linked List as it's the simplest
- Explain the concept of pointers and dynamic memory allocation
- Compare and contrast the three types
- Discuss time and space complexities: - Insert/Delete at beginning: O(1) - Insert/Delete at end: O(n) for singly, O(1) for doubly (with tail pointer) - Search: O(n) for all
- Discuss use cases for each type
For Stack:
- Start with Array-based Stack as it's simpler and more intuitive
- Explain the LIFO (Last In, First Out) principle with real-world examples: - Stack of plates - Undo operations in editors - Function call stack - Expression evaluation (infix to postfix)
- Compare Array-based vs Linked List-based: - Array: Fixed size, faster, memory efficient - Linked List: Dynamic size, more flexible, uses more memory
- Discuss time complexities (all O(1) for basic operations)
- Explain Stack Overflow and Stack Underflow errors
- Show practical applications: - Balanced parentheses checking - Expression evaluation - Infix to Postfix conversion - Backtracking algorithms
For Queue:
- Start with Array-based Queue (circular queue implementation)
- Explain the FIFO (First In, First Out) principle with real-world examples: - Queue of people waiting in line - Printer job queue - CPU scheduling - Breadth-First Search (BFS)
- Explain Circular Queue concept to avoid wasted space: - Show the problem with linear queue (wasted space) - Demonstrate circular indexing with modulo operator
- Compare Array-based vs Linked List-based: - Array: Fixed size, faster, memory efficient - Linked List: Dynamic size, no overflow, uses more memory
- Discuss time complexities (all O(1) for basic operations)
- Explain Queue Overflow and Queue Underflow errors
- Show practical applications: - BFS in graphs - Level-order traversal in trees - Buffer management - Task scheduling
For Deque (Double-ended Queue):
- Introduce Deque as an extension of Queue
- Explain that Deque allows operations at both ends: - Can be used as both Stack and Queue - More flexible than regular Queue
- Compare Array-based vs Linked List-based: - Array: Fixed size, circular indexing, memory efficient - Linked List: Dynamic size, uses doubly linked list, more flexible
- Discuss use cases: - Palindrome checking - Sliding window problems - Both Stack and Queue operations needed - Double-ended priority queue
- Show that it combines features of both Stack and Queue: - Can insert/delete from front (like Stack) - Can insert/delete from rear (like Queue)
- Demonstrate practical applications: - Undo/Redo functionality - Cache implementation - Browser history (forward/backward navigation)
Memory Management
All implementations use proper memory management:
- Dynamic allocation with new
- Proper cleanup in destructors
- No memory leaks