9

memory usage, and complicated code.

C++ provides a rich set of built-in data structures through its Standard Template Library
(STL), but as the complexity of your projects increases, you will often need to go beyond these
and implement more specialized data structures. This booklet covers both fundamental data
structures such as arrays, linked lists, and trees, as well as more advanced ones like heaps, tries,
and suffix trees, all tailored to C++ programming.

What You’ll Learn

Throughout this booklet, we’ll explore the following key topics:

• Fundamental data structures like arrays, linked lists, stacks, and queues.

• Advanced structures including heaps, tries, and suffix trees.

• Built-in STL structures, such as std::vector, std::map, and

std::unordered map.

• How to analyze the time and space complexity of different data structures.

• Best practices for selecting, implementing, and optimizing data structures in C++.

By the end of this booklet, you will have a solid understanding of when and how to use these
data structures effectively, equipping you to write better, more efficient C++ code.

A Practical Approach to Data Structures

This booklet doesn’t just focus on theory—it provides practical, hands-on examples and tips
that are directly applicable to real-world projects. Each chapter is filled with clear explanations,
code examples, and insights that will help you tackle programming challenges more efficiently.
10

With this resource, you’ll not only understand the inner workings of data structures, but you’ll
also develop the skills to apply them in solving complex problems.
Let’s dive into the world of data structures, and start building the foundation for becoming a
more skilled, efficient, and effective C++ programmer.
Chapter 1

Arrays

1.1 Definition and Usage

An array is a collection of elements, all of the same data type, stored in contiguous memory
locations. Arrays are one of the simplest and most fundamental data structures in programming.
They provide fast access to elements through indexing, making them ideal for scenarios
requiring direct access to data.
Key Features:

• Static Nature: The size of an array is fixed during its declaration.

• Contiguous Memory: This property ensures efficient traversal and better performance
when accessing elements.

• Indexed Access: Elements can be accessed in constant time using their index.

Example:

11
12

#include <iostream>
using namespace std;

int main() {
int arr[5] = {1, 2, 3, 4, 5}; // Declaration and initialization

// Accessing and modifying elements

arr[2] = 10;
for (int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
return 0;
}

Advantages of Arrays:

• Fast access using indices.

• Efficient for operations where the size of the data set is known beforehand.

• Compact and straightforward implementation.

Limitations of Static Arrays:

• Fixed size, leading to potential wastage of memory or insufficient storage.

• Insertion and deletion operations are inefficient as they require shifting elements.

1.2 Dynamic Arrays

Unlike static arrays, dynamic arrays can change their size during runtime, allowing for more
flexible and efficient memory usage. In C++, dynamic arrays can be implemented using pointers
or leveraging the Standard Template Library (STL) std::vector.
13

1. Dynamic Arrays Using Pointers:

A dynamic array can be manually created and resized using memory allocation functions
like new and delete.

Example:

#include <iostream>
using namespace std;

int main() {
int n = 5;
int* arr = new int[n]; // Dynamically allocate memory

// Initializing and resizing

for (int i = 0; i < n; i++) {
arr[i] = i + 1;
}

// Resize the array

int new_size = 10;
int* new_arr = new int[new_size];
for (int i = 0; i < n; i++) {
new_arr[i] = arr[i];
}
delete[] arr; // Free old memory
arr = new_arr;

// Print new array

for (int i = 0; i < new_size; i++) {
cout << arr[i] << " ";
}

delete[] arr; // Free allocated memory

14

return 0;
}

Advantages:

• Enables manual control of memory allocation.

• Supports resizing at runtime.

Challenges:

• Manual memory management can lead to errors, such as memory leaks or dangling
pointers.

2. Dynamic Arrays Using std::vector:

The std::vector in C++ is a dynamic array implementation provided by the STL. It
automatically manages memory and resizing, simplifying the programmer’s workload.
Example:

#include <iostream>
#include <vector>
using namespace std;

int main() {
vector<int> vec = {1, 2, 3, 4, 5};

// Add elements dynamically

vec.push_back(6);
vec.push_back(7);

// Access and modify elements

15

vec[2] = 10;

// Print elements
for (int i = 0; i < vec.size(); i++) {
cout << vec[i] << " ";
}

return 0;
}

Advantages of std::vector:

• Automatic memory management and resizing.

• Extensive functionality, including insertion, deletion, and iteration.

• Seamless integration with other STL algorithms.

1.3 Comparison: Static Arrays vs. Dynamic Arrays

Comparison of Static and Dynamic Arrays

Feature Static Arrays Dynamic Arrays (std::vector)
Size Fixed at compile-time Resizable at runtime
Memory Management Manual Automatic
Ease of Use Simple but limited Flexible and feature-rich
Performance Faster due to static size Slight overhead due to resizing

Best Practices When Using Arrays in C++:

16

(a) Use std::vector for Flexibility: Whenever possible, prefer std::vector

for dynamic arrays to avoid manual memory management.
(b) Bounds Checking: Ensure that array indices are within bounds to prevent undefined
behavior.
(c) Memory Management: When using pointers for dynamic arrays, always release
memory using delete[].
(d) Performance Considerations: Use static arrays when size is known and
performance is critical.

Conclusion
Arrays, both static and dynamic, form the foundation for many advanced data structures.
Understanding their behavior, limitations, and best practices is essential for any programmer
aiming to write efficient C++ code. Mastery of arrays sets the stage for exploring more complex
structures like linked lists, stacks, and trees, which will be covered in subsequent chapters of this
booklet.
Chapter 2

Linked Lists

Linked lists are dynamic data structures consisting of nodes connected through pointers. Unlike
arrays, they do not require contiguous memory allocation, offering flexibility in size and efficient
insertion and deletion of elements. This chapter introduces the three main types of linked
lists—singly, doubly, and circular—and provides detailed examples, advantages, and use cases
for each.

What is a Linked List?

A linked list is a collection of nodes where each node contains two parts:

1. Data: The actual information stored in the node.

2. Pointer: A reference to the next node in the sequence (or to both the previous and next
nodes in doubly linked lists).

Advantages of Linked Lists:

• Dynamic Size: No need to declare a fixed size during initialization.

• Efficient Insertions/Deletions: No need to shift elements as in arrays.

17
18

• Memory Usage: Memory is allocated as needed.

Disadvantages:

• Access Time: Requires traversal to access elements (O(n)).

• Memory Overhead: Each node requires extra memory for pointers.

2.1 Singly Linked List

A singly linked list is the simplest type, where each node contains data and a pointer to the next
node. The last node’s pointer is set to nullptr, indicating the end of the list.
Structure of a Singly Linked List:

struct Node {
int data;
Node* next; // Pointer to the next node
};

Operations:
Creation and Traversal:

#include <iostream>
using namespace std;

struct Node {
int data;
Node* next;
};

void printList(Node* head) {

19

while (head != nullptr) {

cout << head->data << " -> ";
head = head->next;
}
cout << "nullptr" << endl;
}

int main() {
Node* head = new Node{1, nullptr};
head->next = new Node{2, nullptr};
head->next->next = new Node{3, nullptr};

printList(head);
return 0;
}

Insertion at the Beginning:

Node* insertAtBeginning(Node* head, int value) {

Node* newNode = new Node{value, head};
return newNode;
}

Deletion:

Node* deleteNode(Node* head, int value) {

if (head == nullptr) return nullptr;
if (head->data == value) {
Node* temp = head->next;
delete head;
return temp;
}