Real Projects: Data Structures Implementation
In the world of software development, data structures are the backbone of efficient and scalable applications. While many tutorials focus on abstract theory, real projects demand practical implementations. This section demonstrates how to build three essential data structures — linked lists, stacks, and queues — with concrete examples that you can integrate into your next project.
Linked List
In real-world applications, linked lists are often used for dynamic collections where the size is unknown or changes frequently. For instance, a task management system might use a linked list to handle to-do items that can be added or removed at any time.
Here’s a minimal implementation of a linked list that supports adding tasks and printing the list:
<code class="language-cpp">#include <iostream>
<p>#include <string></p>
<p>class TaskList {</p>
<p>private:</p>
<p> struct Node {</p>
<p> std::string task;</p>
<p> Node* next;</p>
<p> };</p>
<p> Node* head;</p>
<p>public:</p>
<p> TaskList() : head(nullptr) {}</p>
<p> void addTask(const std::string& task) {</p>
<p> Node* newNode = new Node{task, nullptr};</p>
<p> if (head == nullptr) {</p>
<p> head = newNode;</p>
<p> } else {</p>
<p> Node* current = head;</p>
<p> while (current->next != nullptr) {</p>
<p> current = current->next;</p>
<p> }</p>
<p> current->next = newNode;</p>
<p> }</p>
<p> }</p>
<p> void printTasks() const {</p>
<p> Node* current = head;</p>
<p> while (current != nullptr) {</p>
<p> std::cout << "Task: " << current->task << std::endl;</p>
<p> current = current->next;</p>
<p> }</p>
<p> }</p>
<p>};</p>
<p>int main() {</p>
<p> TaskList todoList;</p>
<p> todoList.addTask("Write report");</p>
<p> todoList.addTask("Fix bugs");</p>
<p> todoList.printTasks();</p>
<p> return 0;</p>
<p>}</code>
This implementation efficiently handles dynamic task lists. The linked list structure allows for O(1) addition at the end and O(n) traversal, making it ideal for applications where items are frequently added but rarely removed.
Stack
Stacks are critical for operations requiring LIFO (Last-In-First-Out) behavior. A common real-world application is undo functionality in text editors, where each action (e.g., typing) is pushed onto the stack, and the previous state can be popped when undoing.
Here’s a stack implementation using a linked list that supports undo operations:
<code class="language-cpp">#include <iostream>
<p>#include <string></p>
<p>class UndoStack {</p>
<p>private:</p>
<p> struct Node {</p>
<p> std::string state;</p>
<p> Node* next;</p>
<p> };</p>
<p> Node* top;</p>
<p>public:</p>
<p> UndoStack() : top(nullptr) {}</p>
<p> void pushState(const std::string& state) {</p>
<p> Node* newNode = new Node{state, top};</p>
<p> top = newNode;</p>
<p> }</p>
<p> std::string popState() {</p>
<p> if (top == nullptr) {</p>
<p> throw std::runtime_error("Stack is empty");</p>
<p> }</p>
<p> Node* temp = top;</p>
<p> top = top->next;</p>
<p> return temp->state;</p>
<p> }</p>
<p>};</p>
<p>int main() {</p>
<p> UndoStack undoStack;</p>
<p> undoStack.pushState("Initial state");</p>
<p> undoStack.pushState("After typing");</p>
<p> std::cout << "Undoing: " << undoStack.popState() << std::endl;</p>
<p> return 0;</p>
<p>}</code>
This implementation efficiently manages undo operations. The linked list ensures O(1) push/pop operations, critical for real-time applications like text editors where undo operations must be fast and reliable.
Queue
Queues are fundamental for processing tasks in FIFO (First-In-First-Out) order. A practical example is a print spooler, where print jobs are added to the queue and processed one by one.
Here’s a queue implementation using a linked list:
<code class="language-cpp">#include <iostream>
<p>#include <string></p>
<p>class PrintQueue {</p>
<p>private:</p>
<p> struct Node {</p>
<p> std::string job;</p>
<p> Node* next;</p>
<p> };</p>
<p> Node* front;</p>
<p> Node* back;</p>
<p>public:</p>
<p> PrintQueue() : front(nullptr), back(nullptr) {}</p>
<p> void addJob(const std::string& job) {</p>
<p> Node* newNode = new Node{job, nullptr};</p>
<p> if (front == nullptr) {</p>
<p> front = newNode;</p>
<p> back = newNode;</p>
<p> } else {</p>
<p> back->next = newNode;</p>
<p> back = newNode;</p>
<p> }</p>
<p> }</p>
<p> std::string nextJob() {</p>
<p> if (front == nullptr) {</p>
<p> throw std::runtime_error("Queue is empty");</p>
<p> }</p>
<p> Node* temp = front;</p>
<p> front = front->next;</p>
<p> if (front == nullptr) {</p>
<p> back = nullptr;</p>
<p> }</p>
<p> return temp->job;</p>
<p> }</p>
<p>};</p>
<p>int main() {</p>
<p> PrintQueue printQueue;</p>
<p> printQueue.addJob("Report.pdf");</p>
<p> printQueue.addJob("Invoice.pdf");</p>
<p> std::cout << "Printing: " << printQueue.nextJob() << std::endl;</p>
<p> return 0;</p>
<p>}</code>
This implementation handles print job processing with O(1) add and O(1) removal operations. The queue structure ensures that the oldest job is processed first, critical for systems where task order must be preserved.
Summary
In this section, we’ve built three foundational data structures with real-world applications:
- Linked lists for dynamic task management
- Stacks for undo functionality
- Queues for print job processing
Each implementation is designed to be immediately usable in production code. Remember to handle edge cases (like empty queues) and memory management in real-world applications. These patterns form the backbone of efficient and scalable software systems.
🌟 Key Takeaway: Start with these core data structures and gradually add optimizations (e.g., circular buffers for queues, memory pooling for stacks) as your application grows. Always prioritize correctness and performance over complexity.