Linked List
A linked list is a linear data structure consisting of a series of nodes, where each node contains data and a pointer to the next node. The main advantages of linked lists are the efficiency of insertion and deletion operations, as they do not require moving other elements. Linked lists can be divided into singly linked lists, doubly linked lists, and circular linked lists.
Singly Linked List
A singly linked list is the simplest form of linked list, where each node contains only one pointer to the next node.
Node Definition
typedef struct Node {
int data;
struct Node* next;
} Node;
Create New Node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
Insert Node
Insert a node at the head of the linked list:
void insertAtHead(Node** head, int data) {
Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}
Insert a node at the tail of the linked list:
void insertAtTail(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
Delete Node
Delete a specified node from the linked list:
void deleteNode(Node** head, int key) {
Node* temp = *head;
Node* prev = NULL;
// If the head node is the one to be deleted
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}
// Search for the node to be deleted
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// If the node is not found in the linked list
if (temp == NULL) return;
// Unlink and free memory
prev->next = temp->next;
free(temp);
}
Traverse Linked List
void printList(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
Doubly Linked List
Each node in a doubly linked list contains two pointers: one to the previous node and one to the next node.
Node Definition
typedef struct DoublyNode {
int data;
struct DoublyNode* prev;
struct DoublyNode* next;
} DoublyNode;
Create New Node
DoublyNode* createDoublyNode(int data) {
DoublyNode* newNode = (DoublyNode*)malloc(sizeof(DoublyNode));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
Insert Node
Insert a node at the head of the doubly linked list:
void insertAtHeadDoubly(DoublyNode** head, int data) {
DoublyNode* newNode = createDoublyNode(data);
newNode->next = *head;
if (*head != NULL) {
(*head)->prev = newNode;
}
*head = newNode;
}
Insert a node at the tail of the doubly linked list:
void insertAtTailDoubly(DoublyNode** head, int data) {
DoublyNode* newNode = createDoublyNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
DoublyNode* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
Delete Node
Delete a specified node from the doubly linked list:
void deleteDoublyNode(DoublyNode** head, int key) {
DoublyNode* temp = *head;
// If the head node is the one to be deleted
if (temp != NULL && temp->data == key) {
*head = temp->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(temp);
return;
}
// Search for the node to be deleted
while (temp != NULL && temp->data != key) {
temp = temp->next;
}
// If the node is not found in the linked list
if (temp == NULL) return;
// Unlink and free memory
if (temp->prev != NULL) {
temp->prev->next = temp->next;
}
if (temp->next != NULL) {
temp->next->prev = temp->prev;
}
free(temp);
}
Traverse Linked List
void printDoublyList(DoublyNode* head) {
DoublyNode* temp = head;
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
Circular Linked List
In a circular linked list, the last node points back to the head node, forming a ring.
Node Definition
The node definition for a circular linked list is the same as for a singly linked list:
typedef struct Node {
int data;
struct Node* next;
} Node;
Create Circular Linked List
Insert a node at the head of the circular linked list:
void insertAtHeadCircular(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
newNode->next = *head;
} else {
Node* temp = *head;
while (temp->next != *head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = *head;
*head = newNode;
}
}
Traverse circular linked list:
void printCircularList(Node* head) {
if (head == NULL) return;
Node* temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("(back to head)\n");
}
Stack and Queue
Stacks and queues are two common linear data structures. A stack follows Last-In-First-Out (LIFO), while a queue follows First-In-First-Out (FIFO).
Stack
Array Implementation
#define MAX 100
typedef struct Stack {
int items[MAX];
int top;
} Stack;
void initializeStack(Stack* s) {
s->top = -1;
}
int isFull(Stack* s) {
return s->top == MAX - 1;
}
int isEmpty(Stack* s) {
return s->top == -1;
}
void push(Stack* s, int value) {
if (isFull(s)) {
printf("Stack is full\n");
return;
}
s->items[++(s->top)] = value;
}
int pop(Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty\n");
return -1;
}
return s->items[(s->top)--];
}
int peek(Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty\n");
return -1;
}
return s->items[s->top];
}
Linked List Implementation
typedef struct StackNode {
int data;
struct StackNode* next;
} StackNode;
typedef struct Stack {
StackNode* top;
} Stack;
void initializeStack(Stack* s) {
s->top = NULL;
}
int isEmpty(Stack* s) {
return s->top == NULL;
}
void push(Stack* s, int value) {
StackNode* newNode = createNode(value);
newNode->next = s->top;
s->top = newNode;
}
int pop(Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty\n");
return -1;
}
StackNode* temp = s->top;
int value = temp->data;
s->top = s->top->next;
free(temp);
return value;
}
int peek(Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty\n");
return -1;
}
return s->top->data;
}
Queue
Array Implementation
#define MAX 100
typedef struct Queue {
int items[MAX];
int front;
int rear;
} Queue;
void initializeQueue(Queue* q) {
q->front = -1;
q->rear = -1;
}
int isEmpty(Queue* q) {
return q->front == -1;
}
int isFull(Queue* q) {
return (q->rear + 1) % MAX == q->front;
}
void enqueue(Queue* q, int value) {
if (isFull(q)) {
printf("Queue is full\n");
return;
}
if (isEmpty(q)) {
q->front = 0;
}
q->rear = (q->rear + 1) % MAX;
q->items[q->rear] = value;
}
int dequeue(Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty\n");
return -1;
}
int item = q->items[q->front];
if (q->front == q->rear) {
q->front = q->rear = -1;
} else {
q->front = (q->front + 1) % MAX;
}
return item;
}
int peek(Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty\n");
return -1;
}
return q->items[q->front];
}
Linked List Implementation
typedef struct QueueNode {
int data;
struct QueueNode* next;
} QueueNode;
typedef struct Queue {
QueueNode* front;
QueueNode* rear;
} Queue;
void initializeQueue(Queue* q) {
q->front = q->rear = NULL;
}
int isEmpty(Queue* q) {
return q->front == NULL;
}
void enqueue(Queue* q, int value) {
QueueNode* newNode = createNode(value);
if (q->rear == NULL) {
q->front = q->rear = newNode;
return;
}
q->rear->next = newNode;
q->rear = newNode;
}
int dequeue(Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty\n");
return -1;
}
QueueNode* temp = q->front;
int value = temp->data;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(temp);
return value;
}
int peek(Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty\n");
return -1;
}
return q->front->data;
}
Tree
A tree is a non-linear data structure consisting of nodes and edges connecting the nodes. Common tree structures include binary trees, AVL trees, and red-black trees.
Binary Tree
Node Definition
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
TreeNode* createTreeNode(int data) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Insert Node
Insertion in a binary tree usually requires recursive implementation:
TreeNode* insertTreeNode(TreeNode* root, int data) {
if (root == NULL) {
return createTreeNode(data);
}
if (data < root->data) {
root->left = insertTreeNode(root->left, data);
} else if (data > root->data) {
root->right = insertTreeNode(root->right, data);
}
return root;
}
Traverse Binary Tree
- Pre-order Traversal: Root -> Left -> Right
void preOrderTraversal(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->data);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
}
- In-order Traversal: Left -> Root -> Right
void inOrderTraversal(TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
- Post-order Traversal: Left -> Right -> Root
void postOrderTraversal(TreeNode* root) {
if (root != NULL) {
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->data);
}
}
AVL Tree
An AVL tree is a self-balancing binary search tree that maintains balance through rotation operations.
Node Definition
typedef struct AVLNode {
int data;
struct AVLNode* left;
struct AVLNode* right;
int height;
} AVLNode;
AVLNode* createAVLNode(int data) {
AVLNode* newNode = (AVLNode*)malloc(sizeof(AVLNode));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = data;
newNode->left = newNode->right = NULL;
newNode->height = 1;
return newNode;
}
Get Node Height
int getHeight(AVLNode* node) {
if (node == NULL) return 0;
return node->height;
}
Get Balance Factor
int getBalanceFactor(AVLNode* node) {
if (node == NULL) return 0;
return getHeight(node->left) - getHeight(node->right);
}
Update Node Height
void updateHeight(AVLNode* node) {
if (node == NULL) return;
node->height = 1 + (getHeight(node->left) > getHeight(node->right) ? getHeight(node->left) : getHeight(node->right));
}
Right Rotation
AVLNode* rightRotate(AVLNode* y) {
AVLNode* x = y->left;
AVLNode* T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
updateHeight(y);
updateHeight(x);
return x;
}
Left Rotation
AVLNode* leftRotate(AVLNode* x) {
AVLNode* y = x->right;
AVLNode* T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
updateHeight(x);
updateHeight(y);
return y;
}
Insert Node
AVLNode* insertAVLNode(AVLNode* node, int data) {
if (node == NULL) return createAVLNode(data);
if (data < node->data) {
node->left = insertAVLNode(node->left, data);
} else if (data > node->data) {
node->right = insertAVLNode(node->right, data);
} else {
return node; // Duplicates not allowed
}
// Update height
updateHeight(node);
// Get balance factor
int balance = getBalanceFactor(node);
// Left-Left case
if (balance > 1 && data < node->left->data) {
return rightRotate(node);
}
// Right-Right case
if (balance < -1 && data > node->right->data) {
return leftRotate(node);
}
// Left-Right case
if (balance > 1 && data > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right-Left case
if (balance < -1 && data < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
Red-Black Tree
A red-black tree is a self-balancing binary search tree that maintains balance through color marking and rotation operations. The rules for red-black trees are complex; only the basic definition and insertion operation are provided here.
Node Definition
typedef enum { RED, BLACK } Color;
typedef struct RBNode {
int data;
Color color;
struct RBNode* left;
struct RBNode* right;
struct RBNode* parent;
} RBNode;
RBNode* createRBNode(int data) {
RBNode* newNode = (RBNode*)malloc(sizeof(RBNode));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = data;
newNode->color = RED;
newNode->left = newNode->right = newNode->parent = NULL;
return newNode;
}
Insert Node
The insertion operation for a red-black tree is complex and requires handling multiple cases; only the basic framework is provided here:
void insertRBNode(RBNode** root, int data) {
RBNode* newNode = createRBNode(data);
// Basic insertion logic (similar to binary search tree)
// Then perform red-black tree fix-up operations
// Fix-up includes color adjustments and rotations
}
Graph
A graph is a non-linear data structure consisting of vertices and edges. Common representation methods include adjacency lists and adjacency matrices.
Adjacency List
An adjacency list uses linked lists to represent the edges of a graph.
Graph Definition
typedef struct AdjListNode {
int dest;
struct AdjListNode* next;
} AdjListNode;
typedef struct AdjList {
AdjListNode* head;
} AdjList;
typedef struct Graph {
int numVertices;
AdjList* array;
} Graph;
AdjListNode* createAdjListNode(int dest) {
AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
Graph* createGraph(int vertices) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->numVertices = vertices;
graph->array = (AdjList*)malloc(vertices * sizeof(AdjList));
for (int i = 0; i < vertices; ++i)
graph->array[i].head = NULL;
return graph;
}
void addEdge(Graph* graph, int src, int dest) {
AdjListNode* newNode = createAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
// For undirected graph, add reverse edge
// newNode = createAdjListNode(src);
// newNode->next = graph->array[dest].head;
// graph->array[dest].head = newNode;
}
Traverse Graph
- Depth-First Search (DFS)
void DFSUtil(Graph* graph, int v, int visited[]) {
visited[v] = 1;
printf("%d ", v);
AdjListNode* temp = graph->array[v].head;
while (temp) {
int adjVertex = temp->dest;
if (!visited[adjVertex]) {
DFSUtil(graph, adjVertex, visited);
}
temp = temp->next;
}
}
void DFS(Graph* graph, int startVertex) {
int* visited = (int*)calloc(graph->numVertices, sizeof(int));
DFSUtil(graph, startVertex, visited);
free(visited);
}
- Breadth-First Search (BFS)
void BFS(Graph* graph, int startVertex) {
int* visited = (int*)calloc(graph->numVertices, sizeof(int));
int queue[MAX], front = 0, rear = 0;
visited[startVertex] = 1;
queue[rear++] = startVertex;
while (front < rear) {
int currentVertex = queue[front++];
printf("%d ", currentVertex);
AdjListNode* temp = graph->array[currentVertex].head;
while (temp) {
int adjVertex = temp->dest;
if (!visited[adjVertex]) {
visited[adjVertex] = 1;
queue[rear++] = adjVertex;
}
temp = temp->next;
}
}
free(visited);
}
Adjacency Matrix
An adjacency matrix uses a two-dimensional array to represent the edges of a graph.
Graph Definition
typedef struct GraphMatrix {
int numVertices;
int** matrix;
} GraphMatrix;
GraphMatrix* createGraphMatrix(int vertices) {
GraphMatrix* graph = (GraphMatrix*)malloc(sizeof(GraphMatrix));
graph->numVertices = vertices;
graph->matrix = (int**)malloc(vertices * sizeof(int*));
for (int i = 0; i < vertices; i++) {
graph->matrix[i] = (int*)malloc(vertices * sizeof(int));
for (int j = 0; j < vertices; j++) {
graph->matrix[i][j] = 0;
}
}
return graph;
}
void addEdgeMatrix(GraphMatrix* graph, int src, int dest) {
graph->matrix[src][dest] = 1;
// For undirected graph, add reverse edge
// graph->matrix[dest][src] = 1;
}
Traverse Graph
- Depth-First Search (DFS)
void DFSMatrixUtil(GraphMatrix* graph, int v, int visited[]) {
visited[v] = 1;
printf("%d ", v);
for (int i = 0; i < graph->numVertices; i++) {
if (graph->matrix[v][i] && !visited[i]) {
DFSMatrixUtil(graph, i, visited);
}
}
}
void DFSMatrix(GraphMatrix* graph, int startVertex) {
int* visited = (int*)calloc(graph->numVertices, sizeof(int));
DFSMatrixUtil(graph, startVertex, visited);
free(visited);
}
- Breadth-First Search (BFS)
void BFSMatrix(GraphMatrix* graph, int startVertex) {
int* visited = (int*)calloc(graph->numVertices, sizeof(int));
int queue[MAX], front = 0, rear = 0;
visited[startVertex] = 1;
queue[rear++] = startVertex;
while (front < rear) {
int currentVertex = queue[front++];
printf("%d ", currentVertex);
for (int i = 0; i < graph->numVertices; i++) {
if (graph->matrix[currentVertex][i] && !visited[i]) {
visited[i] = 1;
queue[rear++] = i;
}
}
}
free(visited);
}
Heap
A heap is a special complete binary tree, commonly used to implement priority queues. Heaps are divided into max-heaps and min-heaps.
Max-Heap
In a max-heap, the value of each node is greater than or equal to the values of its child nodes.
Heap Definition
typedef struct MaxHeap {
int* array;
int capacity;
int size;
} MaxHeap;
MaxHeap* createMaxHeap(int capacity) {
MaxHeap* maxHeap = (MaxHeap*)malloc(sizeof(MaxHeap));
maxHeap->capacity = capacity;
maxHeap->size = 0;
maxHeap->array = (int*)malloc(capacity * sizeof(int));
return maxHeap;
}
Insert Element
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapifyUp(MaxHeap* maxHeap, int index) {
while (index > 0 && maxHeap->array[(index - 1) / 2] < maxHeap->array[index]) {
swap(&maxHeap->array[(index - 1) / 2], &maxHeap->array[index]);
index = (index - 1) / 2;
}
}
void insertMaxHeap(MaxHeap* maxHeap, int value) {
if (maxHeap->size == maxHeap->capacity) {
printf("Heap is full\n");
return;
}
maxHeap->array[maxHeap->size] = value;
heapifyUp(maxHeap, maxHeap->size);
maxHeap->size++;
}
Delete Root Element
void heapifyDown(MaxHeap* maxHeap, int index) {
int largest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < maxHeap->size && maxHeap->array[left] > maxHeap->array[largest]) {
largest = left;
}
if (right < maxHeap->size && maxHeap->array[right] > maxHeap->array[largest]) {
largest = right;
}
if (largest != index) {
swap(&maxHeap->array[index], &maxHeap->array[largest]);
heapifyDown(maxHeap, largest);
}
}
int extractMax(MaxHeap* maxHeap) {
if (maxHeap->size <= 0) {
return -1;
}
if (maxHeap->size == 1) {
maxHeap->size--;
return maxHeap->array[0];
}
int root = maxHeap->array[0];
maxHeap->array[0] = maxHeap->array[maxHeap->size - 1];
maxHeap->size--;
heapifyDown(maxHeap, 0);
return root;
}
Min-Heap
In a min-heap, the value of each node is less than or equal to the values of its child nodes. The implementation of a min-heap is similar to a max-heap, only the comparison logic in heapifyUp and heapifyDown needs to be adjusted.
Insert Element
void heapifyUpMin(MaxHeap* minHeap, int index) {
while (index > 0 && minHeap->array[(index - 1) / 2] > minHeap->array[index]) {
swap(&minHeap->array[(index - 1) / 2], &minHeap->array[index]);
index = (index - 1) / 2;
}
}
void insertMinHeap(MaxHeap* minHeap, int value) {
if (minHeap->size == minHeap->capacity) {
printf("Heap is full\n");
return;
}
minHeap->array[minHeap->size] = value;
heapifyUpMin(minHeap, minHeap->size);
minHeap->size++;
}
Delete Root Element
void heapifyDownMin(MaxHeap* minHeap, int index) {
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < minHeap->size && minHeap->array[left] < minHeap->array[smallest]) {
smallest = left;
}
if (right < minHeap->size && minHeap->array[right] < minHeap->array[smallest]) {
smallest = right;
}
if (smallest != index) {
swap(&minHeap->array[index], &minHeap->array[smallest]);
heapifyDownMin(minHeap, smallest);
}
}
int extractMin(MaxHeap* minHeap) {
if (minHeap->size <= 0) {
return -1;
}
if (minHeap->size == 1) {
minHeap->size--;
return minHeap->array[0];
}
int root = minHeap->array[0];
minHeap->array[0] = minHeap->array[minHeap->size - 1];
minHeap->size--;
heapifyDownMin(minHeap, 0);
return root;
}
Heap Sort
Heap sort is a sorting algorithm based on heaps with a time complexity of O(n log n).
Heap Sort Implementation
void heapifyForSort(int* array, int size, int index) {
int largest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < size && array[left] > array[largest]) {
largest = left;
}
if (right < size && array[right] > array[largest]) {
largest = right;
}
if (largest != index) {
swap(&array[index], &array[largest]);
heapifyForSort(array, size, largest);
}
}
void heapSort(int* array, int size) {
// Build max heap
for (int i = size / 2 - 1; i >= 0; i--) {
heapifyForSort(array, size, i);
}
// Extract elements and adjust heap
for (int i = size - 1; i > 0; i--) {
swap(&array[0], &array[i]);
heapifyForSort(array, i, 0);
}
}
Summary
This article provides a detailed introduction to dynamic data structures in C, including linked lists, stacks and queues, trees, graphs, and heaps. For each data structure, basic definitions, operations, and implementation code are provided. Through this content, readers can gain a deep understanding of the principles and application scenarios of these data structures and apply them flexibly in actual programming.
