C Programming: Implementing Data Structures - Linked Lists, Trees, and Hash Tables
Programming data structures is a fundamental skill that every computer programmer should master. Understanding how these structures work at a low level, like in C, gives you a deeper insight into memory management, algorithm efficiency, and the principles of computer science. Linked lists, trees, and hash tables are commonly used data structures, each with specific advantages and use cases.
1. Linked Lists
A linked list is a linear collection of data elements, where each element (often referred to as a node) contains a reference (or link) to the next node in the sequence. The primary advantage of linked lists over arrays is their dynamic sizing—nodes can be added and removed as needed without having to specify a fixed size beforehand.
Single Linked List Implementation
Step 1: Define the Node Structure
Start by defining a node structure that will hold the data and the pointer to the next node.
struct node {
int data; // Data part of the node
struct node* next; // Pointer to the next node
};
Step 2: Create Functions to Manipulate Nodes
Insert at the Beginning
This function creates a new node and sets it as the head of the list.
void insertAtBeginning(struct node** headRef, int val) { struct node* newNode = (struct node*)malloc(sizeof(struct node)); newNode->data = val; newNode->next = *headRef; *headRef = newNode; }Insert at the End
Insert a node at the end of the linked list.
void insertAtEnd(struct node** headRef, int val) { struct node* newNode = (struct node*)malloc(sizeof(struct node)); newNode->data = val; newNode->next = NULL; if (*headRef == NULL) { *headRef = newNode; return; } struct node* temp = *headRef; while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; }Delete a Node from the Front
Delete the first node of the linked list.
void deleteFront(struct node** headRef) { if (*headRef == NULL) { return; } struct node* temp = *headRef; *headRef = (*headRef)->next; free(temp); }Display the List
A simple traversal function to display all the elements of the linked list.
void displayList(struct node* head) { struct node* temp = head; while (temp != NULL) { printf("%d -> ", temp->data); temp = temp->next; } printf("NULL\n"); }
Double Linked List Implementation
In a double-linked list, each node contains two pointers, one pointing to the next node and another pointing to the previous node.
Step 1: Define the Node Structure
Here, we define the additional prev pointer.
struct DNode {
int data;
struct DNode* next;
struct DNode* prev;
};
Step 2: Create Functions to Manipulate Nodes
Insert at the Beginning
void dInsertAtBeginning(struct DNode** headRef, int val) { struct DNode* newNode = (struct DNode*)malloc(sizeof(struct DNode)); newNode->data = val; newNode->next = *headRef; newNode->prev = NULL; if (*headRef != NULL) { (*headRef)->prev = newNode; } *headRef = newNode; }Delete a Node from the Front
void dDeleteFront(struct DNode** headRef) { if (*headRef == NULL) { return; } struct DNode* temp = *headRef; *headRef = (*headRef)->next; if (*headRef != NULL) { (*headRef)->prev = NULL; } free(temp); }Display the List
void ddisplayList(struct DNode* head) { struct DNode* temp = head; while (temp != NULL) { printf("%d <--> ", temp->data); temp = temp->next; } printf("NULL\n"); }
2. Trees
Trees are hierarchical data structures composed of nodes, where each node has a value and a list of references to its child nodes. Binary trees, particularly binary search trees (BST), are commonly used due to their logarithmic time complexity for operations.
Binary Tree Implementation
Step 1: Define the Structure
Define a structure for a node in a binary tree.
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
Step 2: Create Functions to Manipulate Nodes
Insert a New Node
Insert a new node following the properties of a BST.
struct TreeNode* insertNode(struct TreeNode* root, int val) { if (root == NULL) { struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode)); newNode->data = val; newNode->left = NULL; newNode->right = NULL; return newNode; } if (val < root->data) { root->left = insertNode(root->left, val); } else { root->right = insertNode(root->right, val); } return root; }Search a Node
Search for a value in the BST.
struct TreeNode* searchNode(struct TreeNode* root, int val) { if (root == NULL || root->data == val) { return root; } if (val < root->data) { return searchNode(root->left, val); } return searchNode(root->right, val); }Display In-Order
Display the values of the tree in sorted order (for BST).
void inorderTraversal(struct TreeNode* root) { if (root != NULL) { inorderTraversal(root->left); printf("%d ", root->data); inorderTraversal(root->right); } }
3. Hash Tables
Hash tables provide fast access, insertion, and deletion of records by using a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
Hash Table Implementation
Step 1: Define the Structure
A basic hash table could consist of a dynamically allocated array of pointers, where each pointer leads to a linked list of entries (to resolve collisions via chaining).
#include <stdlib.h>
#include <string.h>
#define SIZE 1000
typedef struct HashItem {
char* key;
int value;
struct HashItem* next;
} HashItem;
typedef struct HashTable {
HashItem** items;
} HashTable;
HashTable* createHashTable() {
HashTable* table = (HashTable*)malloc(sizeof(HashTable));
table->items = (HashItem**)calloc(SIZE, sizeof(HashItem*));
return table;
}
Step 2: Create Functions to Manipulate Nodes
Hash Function
The hash function maps the keys to indices in the array.
unsigned long hash(char* str) { unsigned long hash = 5381; int c; while ((c = *str++)) { hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ } return hash % SIZE; }Create a New Node
HashItem* createNode(char* key, int value) { HashItem* item = (HashItem*)malloc(sizeof(HashItem)); item->key = strdup(key); item->value = value; item->next = NULL; return item; }Insert a Value
Insert a value into the hash table. If there's already a node with the same key, update the value.
void insertToHashTable(HashTable* table, char* key, int value) { unsigned long index = hash(key); HashItem* existingItem = table->items[index]; if (existingItem == NULL) { HashItem* newItem = createNode(key, value); table->items[index] = newItem; return; } if (strcmp(existingItem->key, key) == 0) { existingItem->value = value; return; } HashItem* current = existingItem; while (current->next != NULL) { if (strcmp(current->next->key, key) == 0) { current->next->value = value; return; } current = current->next; } current->next = createNode(key, value); }Retrieve a Value
Retrieve the value associated with a key from the hash table.
int retrieveFromHashTable(HashTable* table, char* key) { unsigned long index = hash(key); HashItem* current = table->items[index]; while (current != NULL) { if (strcmp(current->key, key) == 0) { return current->value; } current = current->next; } return -1; }
Summary of Key Concepts
Linked Lists: They are dynamic arrays of nodes, which can be singly or doubly linked, allowing for efficient insertions and deletions.
Trees: Binary trees, especially binary search trees, allow for logarithmic searches, insertions, and deletions through organized node placement based on their values.
Hash Tables: They provide average-case constant time complexity for insertions, deletions, and lookups by mapping keys to array indices with a hash function. Collisions are handled via chaining.
Understanding these structures deeply and being able to implement them in languages like C equips you with valuable tools for solving computational problems. Each structure has different scenarios where it is most effective, making them indispensable in programming.
Practice and Further Reading
Implementing these data structures can initially appear daunting but practice makes perfect. Start small by writing individual functions to handle each aspect of each structure before combining them into a working program. Consider reading books such as "The C Programming Language" by Brian W. Kernighan and Dennis M. Ritchie for deeper understanding of language features that can aid in building these structures. Online platforms like LeetCode, HackerRank, and GeeksforGeeks offer numerous coding exercises that cover these topics as well.
Remember, building good foundations is essential before diving into advanced concepts. Happy coding!