Data Structure - Linked List

A linked list (Linked List) is a linear data structure made up of several nodes connected sequentially through pointers.

Unlike arrays, the elements in a linked list do not need to be stored contiguously in memory.

Basic Concepts of Linked List and Node Structure

Each node of a linked list contains two parts:Data field (data)Stores the actual data;Pointer field (next)Points to the next node.

链表节点结构与内存中的链式关系

The figure above shows the actual appearance of a linked list in memory. Each node ismallocindependently allocated on the heap, so they can be non-contiguous in memory. Nodes are connected throughnextpointers, and the next pointer of the last node points to NULL to indicate the end of the linked list.

In C, linked list nodes are defined using a structure:

Example

#include <stdio.h>
#include <stdlib.h> /* malloc, free */

/* Linked list node structure
data: data field, stores integer data
next: pointer field, points to the next node of the same type */
struct Node {
int data;
struct Node* next;
};

/* Create a new node
Parameter value: the data value of the node
Return value: pointer to the new node, returns NULL if allocation fails */
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
return NULL;
}
newNode->data = value; /* Set data */
newNode->next = NULL; /* Initialize the next of the new node to NULL */
return newNode;
}

struct Node* nextis a self-referential structure, i.e., the struct contains a pointer to a struct of the same type. This is the core technique for building all chained data structures (linked lists, trees, graphs).

Basic Operations of Singly Linked List

Creating a Linked List and Traversal

Example

#include <stdio.h>
#include <stdlib.h>

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

/* Traverse and print all nodes of the linked list
Start from the head node and visit each node along the next pointers until NULL */
void traverse(struct Node* head) {
struct Node* current = head; /* Start from the head */
printf("Linked list contents: ");
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next; /* Move to the next node */
}
printf("NULL\n");
}

/* Create a linked list containing n nodes (1, 2, 3, ..., n) */
struct Node* createList(int n) {
if (n <= 0) return NULL;

struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = NULL;

struct Node* tail = head; /* tail always points to the last node */
for (int i = 2; i <= n; i++) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = i;
newNode->next = NULL;
tail->next = newNode; /* Connect the new node to the end of the linked list */
tail = newNode; /* Update the tail pointer */
}
return head;
}

int main() {
struct Node* head = createList(5);
traverse(head);
/* Output: Linked list contents: 1 -> 2 -> 3 -> 4 -> 5 -> NULL */
return 0;
}

Insertion Operation

链表插入与删除操作的指针调整过程

The figure above shows the complete process of pointer changes during insertion and deletion in a linked list. Understanding the order of pointer adjustments is crucial: if the order is wrong, it will cause the linked list to break or lead to memory leaks.

Example

#include <stdio.h>
#include <stdlib.h>

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

/* Insert a new node at the head of the linked list (head insertion)
Time complexity: O(1)
Return value: pointer to the new head node */
struct Node* insertAtHead(struct Node* head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = head; /* The new node points to the original head node */
return newNode; /* The new node becomes the new head node */
}

/* Insert a new node at the tail of the linked list (tail insertion)
Time complexity: O(n), requires traversing to the tail */
struct Node* insertAtTail(struct Node* head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;

if (head == NULL) {
return newNode; /* Empty linked list, the new node becomes the head node */
}

struct Node* current = head;
while (current->next != NULL) {
current = current->next; /* Traverse to the last node */
}
current->next = newNode; /* The tail node points to the new node */
return head;
}

/* Insert a new node after the specified position
Time complexity: O(n), requires finding prevNode first */
void insertAfter(struct Node* prevNode, int value) {
if (prevNode == NULL) {
printf("Predecessor node cannot be null\n");
return;
}
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
/* Key: first make the new node point to its successor, then make the predecessor point to the new node */
newNode->next = prevNode->next;
prevNode->next = newNode;
}

void printList(struct Node* head) {
struct Node* cur = head;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}

int main() {
struct Node* head = NULL;

head = insertAtHead(head, 30); /* Linked list: 30 */
head = insertAtHead(head, 20); /* Linked list: 20 -> 30 */
head = insertAtHead(head, 10); /* Linked list: 10 -> 20 -> 30 */

printf("After head insertion: "); printList(head); /* Output: 10 20 30 */

head = insertAtTail(head, 40); /* Linked list: 10 -> 20 -> 30 -> 40 */
printf("After tail insertion: "); printList(head); /* Output: 10 20 30 40 */

insertAfter(head->next, 25); /* Insert 25 after 20 */
printf("After middle insertion: "); printList(head);
/* Output: 10 20 25 30 40 */
return 0;
}

Deletion Operation

Example

#include <stdio.h>
#include <stdlib.h>

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

/* Delete the head node of the linked list
Time complexity: O(1)
Return value: pointer to the new head node */
struct Node* deleteHead(struct Node* head) {
if (head == NULL) return NULL;

struct Node* temp = head; /* Save the old head node */
head = head->next; /* Move the head pointer to the next node */
free(temp); /* Free the memory of the old head node */
return head;
}

/* Delete the first node in the linked list with value target
Time complexity: O(n), requires traversing to find the target node */
struct Node* deleteByValue(struct Node* head, int target) {
if (head == NULL) return NULL;

/* Special case: the target value is at the head node */
if (head->data == target) {
struct Node* temp = head;
head = head->next;
free(temp);
return head;
}

/* Traverse to find the predecessor node of the target node */
struct Node* current = head;
while (current->next != NULL && current->next->data != target) {
current = current->next;
}

/* Find the target node and delete it */
if (current->next != NULL) {
struct Node* temp = current->next;
current->next = current->next->next; /* Skip the target node */
free(temp); /* Free the target node's memory */
}
return head;
}

void printList(struct Node* head) {
struct Node* cur = head;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}

int main() {
/* Build linked list: 10 -> 20 -> 30 -> 40 */
struct Node* head = NULL;
int vals[] = {10, 20, 30, 40};
for (int i = 3; i >= 0; i--) {
struct Node* n = (struct Node*)malloc(sizeof(struct Node));
n->data = vals[i];
n->next = head;
head = n;
}
printf("Original linked list: "); printList(head); /* Output: 10 20 30 40 */

head = deleteHead(head);
printf("After deleting the head: "); printList(head); /* Output: 20 30 40 */

head = deleteByValue(head, 30);
printf("After deleting 30: "); printList(head); /* Output: 20 40 */
return 0;
}

In the deletion operation of a linked list,free()is crucial. If you only adjust pointers without freeing the memory of the deleted node, it will cause a memory leak. In C language, everymallocmust have a correspondingfree。

Comparison of Linked List vs Array

数组与链表全方位对比

Comparison dimension	Array	Linked list
Memory layout	Contiguous storage	Scattered storage, connected via pointers
Random access	O(1)	O(n)
Head insertion/deletion	O(n)	O(1)
Tail insertion/deletion	O(1)	O(1) (with tail pointer) / O(n) (without tail pointer)
Middle insertion/deletion	O(n)	O(1)(known position)
Space overhead	Data only	Data + pointer (8 extra bytes per node (64-bit))
Cache friendliness	High(spatial locality)	Low(nodes scattered)
Capacity	Fixed (static array)	Dynamic growth

Understanding this trade-off is one of the core abilities in data structure selection.

If the data size is known before runtime and does not change frequently, and frequent random access is needed, an array is a better choice.

If the data size changes frequently and its scale is uncertain, dynamic structures such as linked lists are more flexible.

Other extensions