Exploring Pointers in C Language (Part 5) — Linked Lists: A Perfect Interpretation of Pointer Art

After a few busy days, I haven’t had the chance to focus on this topic. Today, on my business trip back to Beijing, I reflected on it and thought it was necessary to back up the linked list.

1. What is a Linked List?

A linked list is a data structure composed of a series of nodes, where each node contains a data field and a pointer field, connecting the nodes through pointers. Unlike arrays, linked lists are stored non-contiguously in memory, which gives them unique advantages.

1. Singly Linked List

The singly linked list is the simplest form of a linked list, where each node points only to the next node, suitable for most simple scenarios. Structure example:

2. Doubly Linked List

The doubly linked list can be traversed both forwards and backwards. Although it requires more memory, it is more efficient in scenarios where frequent forward and backward movements are needed.

3. Circular Linked List

A circular linked list can be divided into circular singly linked lists and circular doubly linked lists:

Circular singly linked list: The tail node points to the head node.
Circular doubly linked list: The head node’s prev points to the tail node, and the tail node’s next points to the head node.

Circular linked lists are suitable for scenarios that require cyclic data access, such as round-robin scheduling algorithms.

2. Core Operations of Linked Lists:

The operations of a linked list include adding, deleting, modifying, and querying. Below is a simple example of linked list operations using a singly linked list.

1. Creating a Node

malloc(sizeof(struct Node)): Dynamically allocate memory to create a new node.
node->data = data: Store the incoming data in the node’s data field.
node->next = NULL: Initialize the next pointer to NULL, indicating this is the end of the linked list.
Return the pointer to the newly created node; if memory allocation fails, return NULL.

2. Linked List Management Structure

head pointer: Points to the first node of the linked list.
size variable: Records the number of nodes in the linked list to avoid recalculating during traversal.
create_linked_list(): Initializes an empty linked list with head as NULL and size as 0.

3. Insertion Operations

3.1 Insertion at the Head

Time Complexity: O(1) – Constant time operation.
Steps:

Create a new node.
Set the new node’s next to the current head.
Update head to point to the new node.
Increase the size of the linked list.

3.2 Insertion at the Tail

Time Complexity: O(n) – Requires traversal to the end of the linked list.
Steps:

If the linked list is empty, directly set head to the new node.
Otherwise, traverse to the last node (current->next == NULL).
Set the last node’s next to the new node.
Increase the size of the linked list.

3.3 Insertion at a Specified Position

Time Complexity: O(n) – In the worst case, requires traversal to the specified position.
Steps:

Check if the position is valid (0 ≤ position ≤ size).
If the insertion position is 0, call the head insertion function.
Otherwise, traverse to the position – 1.
Insert the new node after the current node.
Increase the size of the linked list.

4. Deletion Operations

4.1 Deletion at the Head

Time Complexity: O(1) – Constant time operation.
Steps:

Check if the linked list is empty.
Save the current head to a temporary variable.
Set head to point to the next node.
Free the memory of the original head node.
Decrease the size of the linked list.

4.2 Deletion at the Tail

Time Complexity: O(n) – Requires traversal to the second-to-last node.
Steps:

Check if the linked list is empty.
If there is only one node, directly delete it and set head to NULL.
Otherwise, traverse to the second-to-last node.
Free the memory of the last node.
Set the second-to-last node’s next to NULL.
Decrease the size of the linked list.

4.3 Deletion at a Specified Position

Time Complexity: O(n) – Requires traversal to the specified position.
Steps:

Check if the position is valid (0 ≤ position ≤ size).
Traverse to find the previous node.
Save the pointer to the node to be deleted.
Set the previous node’s next to point to the next node of the node to be deleted.
Free the saved node to be deleted.
Decrease the size of the linked list.

5. Searching and Traversal

find_node(): Time complexity O(n), linear search for a specific value in the linked list.
print_list(): Time complexity O(n), traverses and prints the values of all nodes.
Traversal tip: Use current = current->next to move to the next node until current == NULL.

6. Complete Release of the Linked List

Correctly releasing the entire linked list is key to preventing memory leaks:

Start traversing from the head node of the linked list.
First, save the current node pointer to temp, then move to the next node, and finally free temp.

Why use temp: If you directly free(current), you will lose access to current->next, leading to memory leaks.

After freeing all nodes, free the memory of the LinkedList structure itself.

7. Common Problems and Solutions

7.1 Null Pointer Dereference: Preventing Crashes

If you look closely at the code above, you should see that I added a check in each function:

if (list == NULL) return;

This is actually a good habit. Always check if the pointer is NULL before accessing it. Of course, if you use the linked list functions properly, there generally won’t be any issues, but without this check, you can easily encounter null pointer dereference problems.

This issue is easy to avoid; just add a check before accessing unknown pointers, and everything will be fine.

7.2 Cycle Detection Method: Floyd’s Cycle-Finding Algorithm

A cycle in a linked list occurs when a node’s `next` pointer points to a previous node in the list, creating a circular structure instead of a linear structure ending with `NULL`. This circular structure is not a designed circular linked list but rather an unintended cycle caused by complex linked list operations.

This can lead to infinite loops, program crashes, memory leaks, resource exhaustion, and a series of other problems. Therefore, detecting unintended cycles during the development phase can reduce many issues.

At this point, you can use the classic algorithm Floyd’s Cycle-Finding Algorithm:

Algorithm Principle:

Assume:

The length of the part of the linked list before the cycle is L.
The circumference of the cycle is C.
When they meet, the tortoise has taken k steps, and the hare has taken 2k steps.

When the tortoise enters the cycle:

Tortoise position: L (mod C).
Hare position: 2L (mod C).

The speed of the hare relative to the tortoise is 1 step/unit time, so the hare will catch up to the tortoise after C – (2L – L) mod C steps.

3. Advanced Applications of Linked Lists

1. Reversing a Linked List (Iterative Reverse)

Algorithm Idea:Use three pointers to reverse the direction of each node one by one, processing each node from front to back.

Step-by-step Analysis:

2. Merge Sort for Linked Lists

Algorithm Idea:Use a divide-and-conquer strategy: find the middle node, split the linked list, recursively sort the left and right parts, and merge the two sorted linked lists.

Example: 4 → 2 → 1 → 3 → NULL. The recursive call stack for merge sort is as follows:

This is a summary of some aspects of linked lists; the basics should be covered. I hope this helps everyone. Any questions are welcome for criticism and correction.Personal opinion, for reference only.