Table of Contents
Implementing custom data structures is essential for efficient programming in C and C++. This guide provides a step-by-step approach to creating and managing data structures such as linked lists, stacks, and trees. Understanding these implementations helps optimize code and solve complex problems.
Understanding Data Structures
Data structures organize data to enable efficient access and modification. Common structures include arrays, linked lists, stacks, queues, and trees. Choosing the right structure depends on the specific requirements of the application.
Implementing a Linked List in C
A linked list consists of nodes, each containing data and a pointer to the next node. It allows dynamic memory allocation and efficient insertion or deletion of elements.
Below is a basic implementation of a singly linked list in C:
Node structure:
struct Node {
int data;
struct Node* next;
};
Creating and inserting nodes:
void insertAtHead(struct Node** head, int newData) {
struct Node* newNode = malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = *head;
*head = newNode;
}
Implementing a Stack in C++
A stack follows the Last-In-First-Out (LIFO) principle. It can be implemented using arrays or linked lists. Here, a simple class-based implementation using a vector is shown.
Stack class:
class Stack {
private:
std::vector elements;
public:
void push(int value) { elements.push_back(value); }
void pop() { if (!elements.empty()) elements.pop_back(); }
int top() { return elements.back(); }
bool empty() { return elements.empty(); }
};
Implementing a Binary Tree in C
A binary tree consists of nodes with up to two children. It is useful for hierarchical data and efficient searching.
Node structure:
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
Inserting nodes:
struct TreeNode* insert(struct TreeNode* root, int data) {
if (root == NULL) {
struct TreeNode* newNode = malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
if (data data)
root->left = insert(root->left, data);
else
root->right = insert(root->right, data);
return root;
}