Fundamentals of C++ Development: Overcoming Linked List Confusion with 4 Basic Implementations and Over 10 Application Scenarios (Complete Code Included)

Introduction

The linked list is one of the most fundamental and important data structures in computer science, with wide applications in C++ development. This article will delve into the classification, implementation methods, and various application scenarios of linked lists, helping us make more reasonable data structure choices in practical development.

1. Basic Concepts of Linked Lists

A linked list is a linear data structure that stores data in the form of “nodes”. Each node contains two parts: the data field and the pointer field. Unlike arrays, which require contiguous memory allocation, the nodes in a linked list can be stored at any location in memory, connected by pointers to form a complete data sequence.

1.1 Basic Characteristics of Linked Lists

• • Dynamic Memory Allocation: Linked lists can dynamically allocate memory as needed.
• • Non-contiguous Storage: Nodes do not need to be stored in contiguous memory locations.
• • Efficient Insertion and Deletion: Unlike arrays, there is no need to move large numbers of elements.
• • Inefficient Random Access: Must traverse from the head node to access a node at a specific position.

1.2 Comparison of Linked Lists and Arrays

Characteristic	Linked List	Array
Memory Allocation	Dynamic allocation, allocated during use	Static allocation, determined at compile time or allocated once at runtime
Memory Efficiency	Requires additional pointer space	Compact and contiguous, no extra overhead
Random Access	O(n)	O(1)
Insertion and Deletion	O(1) (if position is known)	O(n) (requires moving elements)
Cache Locality	Poor	Excellent

Have you ever encountered a scenario in a project that required frequent insertions and deletions? In such cases, would you choose to use an array or a linked list?

2. Classification of Linked Lists

Based on the way nodes are connected, linked lists can be classified into the following types:

2.1 Singly Linked List

A singly linked list is the most basic form of linked list, where each node contains data and a pointer to the next node.

Characteristics:

• • Can only be traversed from head to tail
• • Deleting a node requires knowledge of its predecessor node
• • Memory overhead is relatively small

Implementation Example:

#include <iostream>
#include <memory>

class SinglyLinkedList {
private:
    struct Node {
        int data;
        std::unique_ptr<Node> next;
        
        Node(int value) : data(value), next(nullptr) {}
    };
    
    std::unique_ptr<Node> head;
    
public:
    SinglyLinkedList() : head(nullptr) {}
    
    // Insert node at the head of the list
    void pushFront(int value) {
        auto newNode = std::make_unique<Node>(value);
        newNode->next = std::move(head);
        head = std::move(newNode);
    }
    
    // Insert node at the tail of the list
    void pushBack(int value) {
        auto newNode = std::make_unique<Node>(value);
        
        if (!head) {
            head = std::move(newNode);
            return;
        }
        
        Node* current = head.get();
        while (current->next) {
            current = current->next.get();
        }
        
        current->next = std::move(newNode);
    }
    
    // Remove the first node with value
    bool remove(int value) {
        if (!head) return false;
        
        if (head->data == value) {
            head = std::move(head->next);
            return true;
        }
        
        Node* current = head.get();
        while (current->next && current->next->data != value) {
            current = current->next.get();
        }
        
        if (current->next) {
            current->next = std::move(current->next->next);
            return true;
        }
        
        return false;
    }
    
    // Print the list
    void print() const {
        Node* current = head.get();
        while (current) {
            std::cout << current->data << " -> ";
            current = current->next.get();
        }
        std::cout << "nullptr" << std::endl;
    }
};

int main() {
    SinglyLinkedList list;
    
    list.pushBack(1);
    list.pushBack(2);
    list.pushBack(3);
    list.pushFront(0);
    
    std::cout << "Original list: ";
    list.print();  // Output: 0 -> 1 -> 2 -> 3 -> nullptr
    
    list.remove(2);
    std::cout << "After removing node with value 2: ";
    list.print();  // Output: 0 -> 1 -> 3 -> nullptr
    
    return 0;
}

Execution Result:

Application Scenarios:

• • Implementing stack data structures
• • History records (e.g., browser back functionality)
• • Simple memory management (e.g., free memory block lists)
• • Symbol table management

2.2 Doubly Linked List

Each node in a doubly linked list contains data and two pointers, pointing to the previous and next nodes, respectively.

Characteristics:

• • Can be traversed in both directions
• • Deleting a node does not require knowledge of its predecessor node
• • Memory overhead is larger
• • Certain operations are more efficient (e.g., inserting a node before the current position)

Implementation Example:

#include <iostream>
#include <memory>

class DoublyLinkedList {
private:
    struct Node {
        int data;
        std::unique_ptr<Node> next;
        Node* prev;  // Use raw pointer to avoid circular reference
        
        Node(int value) : data(value), next(nullptr), prev(nullptr) {}
    };
    
    std::unique_ptr<Node> head;
    Node* tail;  // Tail pointer for easy operations from the tail
    
public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}
    
    // Insert node at the head of the list
    void pushFront(int value) {
        auto newNode = std::make_unique<Node>(value);
        
        if (!head) {
            head = std::move(newNode);
            tail = head.get();
            return;
        }
        
        newNode->next = std::move(head);
        newNode->next->prev = newNode.get();
        head = std::move(newNode);
    }
    
    // Insert node at the tail of the list
    void pushBack(int value) {
        auto newNode = std::make_unique<Node>(value);
        
        if (!head) {
            head = std::move(newNode);
            tail = head.get();
            return;
        }
        
        newNode->prev = tail;
        tail->next = std::move(newNode);
        tail = tail->next.get();
    }
    
    // Remove the first node with value
    bool remove(int value) {
        if (!head) return false;
        
        if (head->data == value) {
            if (head.get() == tail) {
                tail = nullptr;
            } else {
                head->next->prev = nullptr;
            }
            
            head = std::move(head->next);
            return true;
        }
        
        Node* current = head.get();
        while (current && current->data != value) {
            current = current->next.get();
        }
        
        if (!current) return false;
        
        if (current == tail) {
            tail = current->prev;
            tail->next = nullptr;
        } else {
            current->next->prev = current->prev;
            current->prev->next = std::move(current->next);
        }
        
        return true;
    }
    
    // Print the list from head to tail
    void printForward() const {
        Node* current = head.get();
        while (current) {
            std::cout << current->data << " <-> ";
            current = current->next.get();
        }
        std::cout << "nullptr" << std::endl;
    }
    
    // Print the list from tail to head
    void printBackward() const {
        Node* current = tail;
        while (current) {
            std::cout << current->data << " <-> ";
            current = current->prev;
        }
        std::cout << "nullptr" << std::endl;
    }
};

int main() {
    DoublyLinkedList list;
    
    list.pushBack(1);
    list.pushBack(2);
    list.pushBack(3);
    list.pushFront(0);
    
    std::cout << "Forward traversal: ";
    list.printForward();  // Output: 0 <-> 1 <-> 2 <-> 3 <-> nullptr
    
    std::cout << "Backward traversal: ";
    list.printBackward();  // Output: 3 <-> 2 <-> 1 <-> 0 <-> nullptr
    
    list.remove(2);
    std::cout << "After removing node with value 2 forward traversal: ";
    list.printForward();  // Output: 0 <-> 1 <-> 3 <-> nullptr
    
    return 0;
}

Execution Result:

Application Scenarios:

• • Scenarios requiring bidirectional traversal (e.g., text editors)
• • Implementing LRU cache (Least Recently Used cache)
• • Browser forward/backward functionality
• • Music player playlists (previous/next)

Why do you think a doubly linked list is more suitable than a singly linked list when implementing a text editor?

2.3 Circular Linked List

A circular linked list is a special type of linked list where the last node points to the first node, forming a loop. Circular linked lists can be either singly or doubly linked.

Characteristics:

• • No clear start and end nodes
• • Can traverse the entire list starting from any node
• • Suitable for scenarios requiring circular processing

Implementation Example (Singly Circular Linked List):

#include <iostream>
#include <memory>

class CircularLinkedList {
private:
    struct Node {
        int data;
        std::shared_ptr<Node> next;  // Use shared_ptr to handle circular references
        
        Node(int value) : data(value), next(nullptr) {}
    };
    
    std::shared_ptr<Node> head;
    
public:
    CircularLinkedList() : head(nullptr) {}
    
    // Insert node at the tail of the list
    void insert(int value) {
        auto newNode = std::make_shared<Node>(value);
        
        if (!head) {
            head = newNode;
            head->next = head;  // Point to itself to form a loop
            return;
        }
        
        std::shared_ptr<Node> current = head;
        while (current->next != head) {
            current = current->next;
        }
        
        current->next = newNode;
        newNode->next = head;  // New node points to head to form a loop
    }
    
    // Remove the first node with value
    bool remove(int value) {
        if (!head) return false;
        
        // If there is only one node
        if (head->next == head) {
            if (head->data == value) {
                head = nullptr;
                return true;
            }
            return false;
        }
        
        // If the head node is to be deleted
        if (head->data == value) {
            std::shared_ptr<Node> current = head;
            while (current->next != head) {
                current = current->next;
            }
            
            current->next = head->next;
            head = head->next;
            return true;
        }
        
        // Remove a middle node
        std::shared_ptr<Node> current = head;
        while (current->next != head && current->next->data != value) {
            current = current->next;
        }
        
        if (current->next != head) {
            current->next = current->next->next;
            return true;
        }
        
        return false;
    }
    
    // Print the list (starting from the head node, traversing one loop)
    void print() const {
        if (!head) {
            std::cout << "Empty list" << std::endl;
            return;
        }
        
        std::shared_ptr<Node> current = head;
        do {
            std::cout << current->data << " -> ";
            current = current->next;
        } while (current != head);
        
        std::cout << "(Back to head node: " << head->data << ")" << std::endl;
    }
};

int main() {
    CircularLinkedList list;
    
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.insert(4);
    
    std::cout << "Original circular linked list: ";
    list.print();  // Output: 1 -> 2 -> 3 -> 4 -> (Back to head node: 1)
    
    list.remove(2);
    std::cout << "After removing node with value 2: ";
    list.print();  // Output: 1 -> 3 -> 4 -> (Back to head node: 1)
    
    list.remove(1);  // Remove head node
    std::cout << "After removing head node: ";
    list.print();  // Output: 3 -> 4 -> (Back to head node: 3)
    
    return 0;
}

Execution Result:

Application Scenarios:

• • Round-robin scheduling algorithms
• • Circular buffers
• • Process scheduling in operating systems
• • Turn-based systems in multiplayer games

2.4 Skip List

A skip list is a data structure that allows for fast searching by adding multiple levels of indexing on top of a linked list to speed up the search process.

Characteristics:

• • Average search time is O(log n)
• • Insertion and deletion operations are also O(log n)
• • Relatively complex to implement
• • Space complexity is O(n)

Implementation Example:

#include <iostream>
#include <vector>
#include <memory>
#include <cstdlib>
#include <ctime>
#include <limits>

class SkipList {
private:
    static constexpr int MAX_LEVEL = 16;  // Maximum number of levels
    static constexpr float P = 0.5f;      // Probability of level promotion
    
    struct Node {
        int data;
        std::vector<std::shared_ptr<Node>> forward;  // Forward pointers for each level
        
        Node(int value, int level) : data(value), forward(level, nullptr) {}
    };
    
    std::shared_ptr<Node> head;  // Head node
    int level;                   // Current maximum level
    
    // Randomly generate level
    int randomLevel() {
        int lvl = 1;
        while ((static_cast<float>(std::rand()) / RAND_MAX) < P && lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }
    
public:
    SkipList() : level(1) {
        // Create head node with minimum value
        head = std::make_shared<Node>(std::numeric_limits<int>::min(), MAX_LEVEL);
        std::srand(static_cast<unsigned int>(std::time(nullptr)));
    }
    
    // Search for a node
    bool search(int value) const {
        std::shared_ptr<Node> current = head;
        
        // Start searching from the highest level
        for (int i = level - 1; i >= 0; i--) {
            // Move forward in the current level until the next node's value is greater than or equal to the target value
            while (current->forward[i] && current->forward[i]->data < value) {
                current = current->forward[i];
            }
        }
        
        // Move to the next node at level 0
        current = current->forward[0];
        
        // Check if the target value is found
        return current && current->data == value;
    }
    
    // Insert a node
    void insert(int value) {
        std::vector<std::shared_ptr<Node>> update(MAX_LEVEL, head);
        std::shared_ptr<Node> current = head;
        
        // Start searching for the insertion position from the highest level
        for (int i = level - 1; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->data < value) {
                current = current->forward[i];
            }
            update[i] = current;
        }
        
        // Move to the next node at level 0
        current = current->forward[0];
        
        // If the current node does not exist or the value is not equal to the value to be inserted, create a new node
        if (!current || current->data != value) {
            int newLevel = randomLevel();
            
            // If the new level is greater than the current level, update the forward pointers of the head node
            if (newLevel > level) {
                for (int i = level; i < newLevel; i++) {
                    update[i] = head;
                }
                level = newLevel;
            }
            
            // Create a new node
            auto newNode = std::make_shared<Node>(value, newLevel);
            
            // Update pointers
            for (int i = 0; i < newLevel; i++) {
                newNode->forward[i] = update[i]->forward[i];
                update[i]->forward[i] = newNode;
            }
        }
    }
    
    // Remove a node
    bool remove(int value) {
        std::vector<std::shared_ptr<Node>> update(MAX_LEVEL, nullptr);
        std::shared_ptr<Node> current = head;
        
        // Start searching for the node to be deleted from the highest level
        for (int i = level - 1; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->data < value) {
                current = current->forward[i];
            }
            update[i] = current;
        }
        
        current = current->forward[0];
        
        // If the node to be deleted is found
        if (current && current->data == value) {
            // Update pointers for all levels
            for (int i = 0; i < level; i++) {
                if (update[i]->forward[i] != current) {
                    break;
                }
                update[i]->forward[i] = current->forward[i];
            }
            
            // Update level
            while (level > 1 && !head->forward[level - 1]) {
                level--;
            }
            
            return true;
        }
        
        return false;
    }
    
    // Print the skip list
    void print() const {
        for (int i = level - 1; i >= 0; i--) {
            std::cout << "Level " << i << ": ";
            std::shared_ptr<Node> node = head->forward[i];
            while (node) {
                std::cout << node->data << " -> ";
                node = node->forward[i];
            }
            std::cout << "nullptr" << std::endl;
        }
    }
};

int main() {
    SkipList skipList;
    
    skipList.insert(3);
    skipList.insert(6);
    skipList.insert(7);
    skipList.insert(9);
    skipList.insert(12);
    skipList.insert(19);
    skipList.insert(17);
    skipList.insert(26);
    skipList.insert(21);
    skipList.insert(25);
    
    std::cout << "Skip list structure:" << std::endl;
    skipList.print();
    
    std::cout << "\nSearch operation:" << std::endl;
    std::cout << "Search 19: " << (skipList.search(19) ? "Found" : "Not Found") << std::endl;
    std::cout << "Search 15: " << (skipList.search(15) ? "Found" : "Not Found") << std::endl;
    
    std::cout << "\nDelete operation:" << std::endl;
    skipList.remove(19);
    std::cout << "After deleting 19:" << std::endl;
    skipList.print();
    
    return 0;
}

Execution Result:

Application Scenarios:

• • Efficient search operations (e.g., database indexing)
• • Sorted sets in Redis
• • Scenarios requiring fast searching and maintaining ordered data

3. Advanced Applications of Linked Lists

3.1 Custom Memory Allocator

Linked lists can be used to implement custom memory allocators, managing free blocks in a memory pool.

#include <iostream>
#include <cstddef>
#include <vector>

class SimpleMemoryPool {
private:
    struct MemoryBlock {
        size_t size;           // Size of the memory block
        bool isFree;           // Is it free
        MemoryBlock* next;     // Pointer to the next memory block
        void* data;            // Starting position of the actual data
        
        MemoryBlock(size_t blockSize) : size(blockSize), isFree(true), next(nullptr) {}
    };
    
    void* poolStart;          // Starting position of the memory pool
    size_t poolSize;          // Total size of the memory pool
    MemoryBlock* freeList;    // Free block linked list
    
public:
    SimpleMemoryPool(size_t size) : poolSize(size) {
        // Allocate memory pool
        poolStart = ::operator new(size);
        
        // Create initial memory block
        freeList = new MemoryBlock(size);
        freeList->data = poolStart;
    }
    
    ~SimpleMemoryPool() {
        // Release memory pool
        ::operator delete(poolStart);
        
        // Release memory block management structures
        MemoryBlock* current = freeList;
        while (current) {
            MemoryBlock* next = current->next;
            delete current;
            current = next;
        }
    }
    
    // Allocate memory
    void* allocate(size_t size) {
        // Align size (simplified version)
        size = (size + 7) && ~7;  // 8-byte alignment
        
        MemoryBlock* prev = nullptr;
        MemoryBlock* current = freeList;
        
        // Find a sufficiently large free block
        while (current) {
            if (current->isFree && current->size >= size) {
                // Found a suitable block
                
                // If the block is large enough, it can be split
                if (current->size > size + sizeof(MemoryBlock) + 8) {
                    // Create a new free block
                    MemoryBlock* newBlock = new MemoryBlock(current->size - size - sizeof(MemoryBlock));
                    newBlock->data = static_cast<char*>(current->data) + size;
                    
                    // Update the current block
                    current->size = size;
                    
                    // Insert the new block into the linked list
                    newBlock->next = current->next;
                    current->next = newBlock;
                }
                
                // Mark as used
                current->isFree = false;
                
                return current->data;
            }
            
            prev = current;
            current = current->next;
        }
        
        // No suitable block found
        return nullptr;
    }
    
    // Free memory
    void deallocate(void* ptr) {
        if (!ptr) return;
        
        MemoryBlock* current = freeList;
        
        // Find the block containing this pointer
        while (current) {
            if (current->data == ptr) {
                // Mark as free
                current->isFree = true;
                
                // Merge adjacent free blocks (simplified version)
                mergeAdjacentFreeBlocks();
                return;
            }
            current = current->next;
        }
    }
    
    // Merge adjacent free blocks
    void mergeAdjacentFreeBlocks() {
        MemoryBlock* current = freeList;
        
        while (current && current->next) {
            if (current->isFree && current->next->isFree) {
                // Merge two blocks
                current->size += current->next->size + sizeof(MemoryBlock);
                
                // Remove the next block
                MemoryBlock* toDelete = current->next;
                current->next = toDelete->next;
                delete toDelete;
            } else {
                current = current->next;
            }
        }
    }
    
    // Print memory pool status (for debugging)
    void printStatus() const {
        MemoryBlock* current = freeList;
        int blockCount = 0;
        
        std::cout << "Memory pool status:" << std::endl;
        while (current) {
            std::cout << "Block " << blockCount++ << ": ";
            std::cout << "Size = " << current->size << " bytes, ";
            std::cout << "Status = " << (current->isFree ? "Free" : "Used") << std::endl;
            current = current->next;
        }
    }
};

int main() {
    // Create a 1KB memory pool
    SimpleMemoryPool pool(1024);
    
    std::cout << "Initial status:" << std::endl;
    pool.printStatus();
    
    // Allocate some memory
    void* p1 = pool.allocate(100);
    void* p2 = pool.allocate(200);
    void* p3 = pool.allocate(300);
    
    std::cout << "\nStatus after allocation:" << std::endl;
    pool.printStatus();
    
    // Free some memory
    pool.deallocate(p2);
    
    std::cout << "\nStatus after freeing p2:" << std::endl;
    pool.printStatus();
    
    // Allocate again
    void* p4 = pool.allocate(150);
    
    std::cout << "\nStatus after allocating again:" << std::endl;
    pool.printStatus();
    
    return 0;
}

3.2 LRU Cache Implementation

Using a doubly linked list and a hash table to implement an efficient LRU (Least Recently Used) cache.

#include <iostream>
#include <unordered_map>
#include <memory>

template<typename K, typename V>
class LRUCache {
private:
    struct Node {
        K key;
        V value;
        Node* prev;
        Node* next;
        
        Node(K k, V v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };
    
    int capacity;                          // Cache capacity
    Node* head;                            // Head node (most recently used)
    Node* tail;                            // Tail node (least recently used)
    std::unordered_map<K, Node*> cache;    // Hash table for O(1) lookup
    
    // Move node to the head of the list (mark as most recently used)
    void moveToHead(Node* node) {
        if (node == head) return;
        
        // Remove from current position
        if (node == tail) {
            tail = node->prev;
            tail->next = nullptr;
        } else {
            node->prev->next = node->next;
            node->next->prev = node->prev;
        }
        
        // Insert at head
        node->next = head;
        node->prev = nullptr;
        head->prev = node;
        head = node;
    }
    
    // Add new node to head
    void addToHead(Node* node) {
        if (!head) {
            head = tail = node;
        } else {
            node->next = head;
            head->prev = node;
            head = node;
        }
    }
    
    // Remove tail node (least recently used)
    void removeTail() {
        if (!tail) return;
        
        Node* oldTail = tail;
        
        if (head == tail) {
            head = tail = nullptr;
        } else {
            tail = tail->prev;
            tail->next = nullptr;
        }
        
        cache.erase(oldTail->key);
        delete oldTail;
    }
    
public:
    LRUCache(int cap) : capacity(cap), head(nullptr), tail(nullptr) {}
    
    ~LRUCache() {
        Node* current = head;
        while (current) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }
    
    // Get value, if exists mark as most recently used
    V get(K key) {
        if (cache.find(key) == cache.end()) {
            throw std::runtime_error("Key not found");
        }
        
        Node* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    // Check if key exists
    bool contains(K key) {
        return cache.find(key) != cache.end();
    }
    
    // Insert or update value
    void put(K key, V value) {
        if (cache.find(key) != cache.end()) {
            // Update existing node
            Node* node = cache[key];
            node->value = value;
            moveToHead(node);
        } else {
            // Create new node
            Node* newNode = new Node(key, value);
            cache[key] = newNode;
            addToHead(newNode);
            
            // If exceeds capacity, remove least recently used node
            if (cache.size() > capacity) {
                removeTail();
            }
        }
    }
    
    // Print cache contents (from most recently used to least recently used)
    void printCache() const {
        Node* current = head;
        std::cout << "LRU Cache Contents (Most Recently Used -> Least Recently Used): ";
        while (current) {
            std::cout << "[" << current->key << ": " << current->value << "]";
            if (current->next) std::cout << " -> ";
            current = current->next;
        }
        std::cout << std::endl;
    }
};

int main() {
    LRUCache<std::string, int> cache(3);
    
    cache.put("one", 1);
    cache.put("two", 2);
    cache.put("three", 3);
    
    std::cout << "Initial cache:" << std::endl;
    cache.printCache();  // [three: 3] -> [two: 2] -> [one: 1]
    
    // Access existing element
    std::cout << "\nGet 'one': " << cache.get("one") << std::endl;
    cache.printCache();  // [one: 1] -> [three: 3] -> [two: 2]
    
    // Add new element, exceeding capacity
    cache.put("four", 4);
    std::cout << "\nAfter adding 'four': " << std::endl;
    cache.printCache();  // [four: 4] -> [one: 1] -> [three: 3]
    
    // Check evicted element
    std::cout << "'two' exists: " << (cache.contains("two") ? "Yes" : "No") << std::endl;
    
    return 0;
}

3.3 Polynomial Representation and Calculation

Linked lists can be used to represent polynomials, with each node storing the coefficient and exponent of a term.

#include <iostream>
#include <memory>
#include <sstream>
#include <cmath>

class Polynomial {
private:
    struct Term {
        double coefficient;  // Coefficient
        int exponent;        // Exponent
        std::unique_ptr<Term> next;
        
        Term(double coef, int exp) : coefficient(coef), exponent(exp), next(nullptr) {}
    };
    
    std::unique_ptr<Term> head;
    
    // Insert term, maintaining descending order of exponents
    void insertTerm(double coef, int exp) {
        if (std::abs(coef) < 1e-10) return;  // Ignore terms with coefficient 0
        
        auto newTerm = std::make_unique<Term>(coef, exp);
        
        if (!head || exp > head->exponent) {
            // Insert at head
            newTerm->next = std::move(head);
            head = std::move(newTerm);
            return;
        }
        
        // Find insertion position
        Term* current = head.get();
        while (current->next && current->next->exponent > exp) {
            current = current->next.get();
        }
        
        // If a term with the same exponent already exists, merge coefficients
        if (current->exponent == exp) {
            current->coefficient += coef;
            // If merged coefficient is 0, remove the term
            if (std::abs(current->coefficient) < 1e-10) {
                if (current == head.get()) {
                    head = std::move(head->next);
                } else {
                    Term* prev = head.get();
                    while (prev->next.get() != current) {
                        prev = prev->next.get();
                    }
                    prev->next = std::move(current->next);
                }
            }
        } else if (current->next && current->next->exponent == exp) {
            current->next->coefficient += coef;
            // If merged coefficient is 0, remove the term
            if (std::abs(current->next->coefficient) < 1e-10) {
                current->next = std::move(current->next->next);
            }
        } else {
            // Insert new term
            newTerm->next = std::move(current->next);
            current->next = std::move(newTerm);
        }
    }
    
public:
    Polynomial() : head(nullptr) {}
    
    // Parse polynomial from string
    static Polynomial parse(const std::string&amp; str) {
        Polynomial poly;
        std::istringstream iss(str);
        
        double coef;
        char var;
        char op;
        int exp;
        
        while (iss >> coef) {
            if (iss.peek() == '*') {
                iss >> op >> var >> op >> exp;
                poly.insertTerm(coef, exp);
            } else {
                poly.insertTerm(coef, 0);  // Constant term
            }
            
            if (iss.peek() == '+' || iss.peek() == '-') {
                if (iss.peek() == '+') {
                    iss >> op;
                } else {
                    iss >> op;
                    iss >> coef;
                    coef = -coef;
                    if (iss.peek() == '*') {
                        iss >> op >> var >> op >> exp;
                        poly.insertTerm(coef, exp);
                    } else {
                        poly.insertTerm(coef, 0);  // Constant term
                    }
                }
            }
        }
        
        return poly;
    }
    
    // Addition operation
    Polynomial operator+(const Polynomial&amp; other) const {
        Polynomial result;
        
        // Copy all terms from the current polynomial
        Term* current = head.get();
        while (current) {
            result.insertTerm(current->coefficient, current->exponent);
            current = current->next.get();
        }
        
        // Add all terms from the other polynomial
        current = other.head.get();
        while (current) {
            result.insertTerm(current->coefficient, current->exponent);
            current = current->next.get();
        }
        
        return result;
    }
    
    // Subtraction operation
    Polynomial operator-(const Polynomial&amp; other) const {
        Polynomial result;
        
        // Copy all terms from the current polynomial
        Term* current = head.get();
        while (current) {
            result.insertTerm(current->coefficient, current->exponent);
            current = current->next.get();
        }
        
        // Subtract all terms from the other polynomial
        current = other.head.get();
        while (current) {
            result.insertTerm(-current->coefficient, current->exponent);
            current = current->next.get();
        }
        
        return result;
    }
    
    // Multiplication operation
    Polynomial operator*(const Polynomial&amp; other) const {
        Polynomial result;
        
        // Traverse all terms of the current polynomial
        Term* term1 = head.get();
        while (term1) {
            // Traverse all terms of the other polynomial
            Term* term2 = other.head.get();
            while (term2) {
                // Calculate product term
                double newCoef = term1->coefficient * term2->coefficient;
                int newExp = term1->exponent + term2->exponent;
                result.insertTerm(newCoef, newExp);
                
                term2 = term2->next.get();
            }
            
            term1 = term1->next.get();
        }
        
        return result;
    }
    
    // Calculate the value of the polynomial at a given x
    double evaluate(double x) const {
        double result = 0.0;
        Term* current = head.get();
        
        while (current) {
            result += current->coefficient * std::pow(x, current->exponent);
            current = current->next.get();
        }
        
        return result;
    }
    
    // Convert to string representation
    std::string toString() const {
        if (!head) return "0";
        
        std::ostringstream oss;
        Term* current = head.get();
        bool isFirst = true;
        
        while (current) {
            // Handle coefficient
            if (current->coefficient > 0) {
                if (!isFirst) oss << " + ";
            } else {
                if (isFirst) oss << "-";
                else oss << " - ";
            }
            
            double absCoef = std::abs(current->coefficient);
            
            // Handle exponent
            if (current->exponent == 0) {
                // Constant term
                oss << absCoef;
            } else if (current->exponent == 1) {
                // Linear term
                if (std::abs(absCoef - 1.0) < 1e-10) {
                    oss << "x";
                } else {
                    oss << absCoef << "*x";
                }
            } else {
                // Higher order term
                if (std::abs(absCoef - 1.0) < 1e-10) {
                    oss << "x^" << current->exponent;
                } else {
                    oss << absCoef << "*x^" << current->exponent;
                }
            }
            
            isFirst = false;
            current = current->next.get();
        }
        
        return oss.str();
    }
};

int main() {
    // Create polynomial p1 = 3*x^2 + 2*x + 1
    Polynomial p1 = Polynomial::parse("3*x^2 + 2*x + 1");
    std::cout << "p1(x) = " << p1.toString() << std::endl;
    
    // Create polynomial p2 = x^3 - 2*x + 5
    Polynomial p2 = Polynomial::parse("1*x^3 - 2*x + 5");
    std::cout << "p2(x) = " << p2.toString() << std::endl;
    
    // Polynomial addition
    Polynomial sum = p1 + p2;
    std::cout << "p1(x) + p2(x) = " << sum.toString() << std::endl;
    
    // Polynomial subtraction
    Polynomial diff = p1 - p2;
    std::cout << "p1(x) - p2(x) = " << diff.toString() << std::endl;
    
    // Polynomial multiplication
    Polynomial product = p1 * p2;
    std::cout << "p1(x) * p2(x) = " << product.toString() << std::endl;
    
    // Calculate the value of the polynomial at x=2
    double x = 2.0;
    std::cout << "p1(" << x << ") = " << p1.evaluate(x) << std::endl;
    std::cout << "p2(" << x << ") = " << p2.evaluate(x) << std::endl;
    
    return 0;
}

4. Performance Optimization of Linked Lists

4.1 Memory Pool Optimization

Frequent dynamic memory allocation and deallocation can affect the performance of linked lists. Using a memory pool can significantly improve the efficiency of linked list operations.

4.2 Cache-Friendly Linked Lists

Traditional linked list nodes are scattered in memory, leading to low cache hit rates. Optimization can be achieved through the following methods:

1. 1. Block Linked Lists: Each node contains multiple elements, improving cache locality.
2. 2. Compact Linked Lists: Store nodes in contiguous memory areas.

4.3 Lock-Free Linked Lists

In a multithreaded environment, using lock-free algorithms to implement linked lists can avoid lock contention and improve concurrent performance.

5. Recommendations for Choosing and Practicing Linked Lists

5.1 When to Choose Linked Lists

• • Frequent insertions and deletions are required
• • The number of elements is uncertain or frequently changes
• • Random access is not required
• • Limited memory space, requiring dynamic allocation

5.2 When to Avoid Using Linked Lists

• • Frequent random access is required
• • Data volume is small and fixed
• • Scenarios where cache locality is important
• • Scenarios sensitive to memory overhead

5.3 Practical Recommendations

1. 1. Choose the appropriate type of linked list: Select singly, doubly, or circular linked lists based on the application scenario.
2. 2. Use smart pointers: Avoid memory leaks and dangling pointer issues.
3. 3. Consider using the standard library: C++ STL provides ready-made implementations like <span>std::forward_list</span> and <span>std::list</span>.
4. 4. Pay attention to boundary conditions: Handle special cases like empty lists and single-node lists.
5. 5. Optimize frequent operations: Optimize the most commonly used operations.

6. Conclusion

As a fundamental data structure, linked lists have wide applications in C++ development. Through this article, we have learned about the characteristics, implementation methods, and application scenarios of different types of linked lists. In practical development, it is essential to choose the appropriate type of linked list based on specific needs and consider performance optimization and memory management factors.

Have you used linked lists in your actual projects? What challenges did you encounter? Feel free to share your experiences and insights in the comments!