C++ Data Structures and Algorithms: Linked Lists

In C++, a linked list is a dynamic data structure composed of a series of nodes, each containing a data field and a pointer field (pointing to the next adjacent node). Unlike arrays that use contiguous memory, linked list nodes are stored in non-contiguous memory, linked together by pointers, thus providing flexible insertion/deletion features.

1. Core Structure of Linked Lists

1. Node Definition

The basic unit of a linked list is a node, which contains data and a pointer to the next node:

// Singly linked list node
struct ListNode {
    int val;               // Data field
    ListNode* next;        // Pointer field (points to the next node)
    ListNode(int x) : val(x), next(nullptr) {}  // Constructor
};

2. Common Types of Linked Lists

Singly Linked List Each node points only to the next node, with the tail node’s next being nullptr.
Doubly Linked List Each node contains both prev (previous) andnext (next) pointers, supporting bidirectional traversal.

struct DListNode {
    int val;
    DListNode* prev; // Previous
    DListNode* next; // Next
    DListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};

Circular Linked List The tail node’s next points to the head node, forming a closed loop (suitable for circular buffers and similar scenarios).

2. Basic Operations of Singly Linked Lists (Core)

Singly linked lists are the most commonly used form, and the following operations are based on singly linked lists:

1. Creating a Linked List

Constructing a linked list by adding nodes one by one:

2. Traversing the Linked List (O(n))

Accessing all nodes by moving through pointers:

3. Inserting a Node

Insert after nodep (known predecessor, O(1)): If P is unknown, it needs to be traversed to find P.

4. Deleting a Node

Delete the successor node ofp (known predecessor, O(1)):

5. Destroying the Linked List (to avoid memory leaks)

3. Classic Algorithms for Linked Lists

1. Reversing a Linked List (O(n) time, O(1) space)

2. Detecting a Cycle (Floyd’s Tortoise and Hare algorithm, O(n) time)

3. Finding the Middle Node of a Linked List (Floyd’s Tortoise and Hare algorithm, O(n) time)

4. Merging Two Sorted Linked Lists (O(n+m) time)

4. Comparison of Linked Lists and Arrays

Feature	Linked List	Array
Memory Storage	Non-contiguous, linked by pointers	Contiguous memory block
Random Access	O(n) (requires traversal)	O(1) (via index)
Insertion / Deletion	O(1) (when predecessor is known)	O(n) (requires moving elements)
Size Flexibility	Dynamic expansion, no pre-allocation needed	Static array size fixed, dynamic array needs resizing
Memory Overhead	Extra storage for pointers	No extra overhead
Cache Friendliness	Poor (nodes are scattered)	Good (contiguous storage, locality principle)

5. Suitable Scenarios

Frequent Insertions / Deletions such as implementing linked list-based queues, stacks, adjacency lists, etc. (insertions and deletions do not require moving large numbers of elements).
Uncertain Data Scale No need to pre-allocate fixed-size memory (avoiding performance loss from array resizing).
Acceptable Memory Fragmentation Scenarios where scattered storage of nodes does not significantly impact memory utilization.

6. Linked Lists in the C++ Standard Library

std::list: Doubly linked list, supports O(1) insertion and deletion, does not support random access.

Conclusion

The core advantages of linked lists aredynamicity and efficient insertion/deletion, making them suitable for scenarios where data structures are frequently modified; however, random access performance is poor, and memory overhead is slightly higher. Mastering pointer operations and classic algorithms (reversal, cycle detection, merging, etc.) for linked lists is fundamental to understanding more complex data structures (such as trees and graphs).In actual development, prefer usingstd::list.