链表 vs 数组：为什么需要链表？

在编程中，我们经常需要在数据集合中进行增删查改操作。数组是最基础的数据结构，但它有一个致命缺陷：大小固定，插入删除效率低。链表应运而生，解决了这些问题。

内存布局对比

数组：连续内存块

[元素1][元素2][元素3][元素4][元素5]
  ↑
 首地址

链表：分散内存通过指针连接

[元素1] -> [元素2] -> [元素3] -> [元素4] -> [元素5]
  ↑          ↑          ↑          ↑          ↑
不同内存地址   通过next指针连接

链表的核心优势

1. 动态大小：不需要预先分配固定空间
2. 高效插入删除：O(1)时间复杂度（如果已知位置）
3. 内存利用率高：节点可以分散在内存各处

链表节点定义

力扣式单链表节点（简化版）

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

实际开发中的链表节点（完整版）

template <typename E>
class Node {
public:
    E val;
    Node* next;
    Node* prev;  // 双链表特有

    Node(Node* prev, E element, Node* next) {
        this->val = element;
        this->next = next;
        this->prev = prev;
    }
};

单链表的基本操作

创建单链表工具函数

ListNode* createLinkedList(std::vector<int> arr) {
    if (arr.empty()) return nullptr;
    
    ListNode* head = new ListNode(arr[0]);
    ListNode* cur = head;
    for (int i = 1; i < arr.size(); i++) {
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }
    return head;
}

遍历和查找

// 遍历单链表
ListNode* head = createLinkedList({1, 2, 3, 4, 5});
for (ListNode* p = head; p != nullptr; p = p->next) {
    std::cout << p->val << std::endl;
}

插入操作

头部插入

ListNode* head = createLinkedList({1, 2, 3, 4, 5});

// 在头部插入新节点 0
ListNode* newNode = new ListNode(0);
newNode->next = head;
head = newNode;
// 结果：0 -> 1 -> 2 -> 3 -> 4 -> 5

尾部插入

ListNode* head = createLinkedList({1, 2, 3, 4, 5});

// 在尾部插入新节点 6
ListNode* p = head;
while (p->next != nullptr) {
    p = p->next;
}
p->next = new ListNode(6);
// 结果：1 -> 2 -> 3 -> 4 -> 5 -> 6

中间插入

ListNode* head = createLinkedList({1, 2, 3, 4, 5});

// 在第3个节点后插入66
ListNode* p = head;
for (int i = 0; i < 2; i++) {
    p = p->next;
}

ListNode* newNode = new ListNode(66);
newNode->next = p->next;
p->next = newNode;
// 结果：1 -> 2 -> 3 -> 66 -> 4 -> 5

删除操作

头部删除

ListNode* head = createLinkedList({1, 2, 3, 4, 5});

// 删除头节点
head = head->next;
// 结果：2 -> 3 -> 4 -> 5

尾部删除

ListNode* head = createLinkedList({1, 2, 3, 4, 5});

// 删除尾节点
ListNode* p = head;
while (p->next->next != nullptr) {
    p = p->next;
}
p->next = nullptr;
// 结果：1 -> 2 -> 3 -> 4

中间删除

ListNode* head = createLinkedList({1, 2, 3, 4, 5});

// 删除第4个节点
ListNode* p = head;
for (int i = 0; i < 2; i++) {
    p = p->next;
}
p->next = p->next->next;
// 结果：1 -> 2 -> 3 -> 5

双链表的基本操作

创建双链表工具函数

class DoublyListNode {
public:
    int val;
    DoublyListNode *next, *prev;
    DoublyListNode(int x) : val(x), next(NULL), prev(NULL) {}
};

DoublyListNode* createDoublyLinkedList(const std::vector<int>& arr) {
    if (arr.empty()) return NULL;
    
    DoublyListNode* head = new DoublyListNode(arr[0]);
    DoublyListNode* cur = head;
    for (int i = 1; i < arr.size(); i++) {
        DoublyListNode* newNode = new DoublyListNode(arr[i]);
        cur->next = newNode;
        newNode->prev = cur;
        cur = cur->next;
    }
    return head;
}

双向遍历

DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});

// 正向遍历
for (DoublyListNode* p = head; p != nullptr; p = p->next) {
    std::cout << p->val << " ";
}

// 反向遍历（需要先找到尾部）
DoublyListNode* tail = head;
while (tail->next != nullptr) tail = tail->next;

for (DoublyListNode* p = tail; p != nullptr; p = p->prev) {
    std::cout << p->val << " ";
}

完整链表实现：关键设计要点

关键点一：同时持有头尾节点引用

在实际开发中，我们同时维护头尾指针：

template<typename E>
class MyLinkedList {
private:
    Node* head;  // 头指针
    Node* tail;  // 尾指针
    int size;    // 元素数量
};

这样可以在O(1)时间内完成尾部操作，而不需要每次遍历整个链表。

关键点二：虚拟头尾节点技巧

虚拟节点是链表实现中的重要技巧，可以极大简化边界条件处理：

// 空双链表结构：
dummyHead <-> dummyTail

// 包含元素的双链表：
dummyHead <-> 1 <-> 2 <-> 3 <-> dummyTail

优势：

• 避免空指针异常
• 统一头尾操作逻辑
• 简化代码复杂度

关键点三：内存管理

在删除节点时，正确处理指针关系：

// 正确做法：断开被删除节点的所有引用
node->prev->next = node->next;
node->next->prev = node->prev;
node->prev = nullptr;  // 好习惯
node->next = nullptr;  // 好习惯
delete node;

完整双链表实现

#include <iostream>
#include <stdexcept>

template<typename E>
class MyLinkedList {
private:
    struct Node {
        E val;
        Node* next;
        Node* prev;
        Node(E value) : val(value), next(nullptr), prev(nullptr) {}
    };

    Node* head;  // 虚拟头节点
    Node* tail;  // 虚拟尾节点
    int size;

public:
    // 构造函数
    MyLinkedList() {
        head = new Node(E());
        tail = new Node(E());
        head->next = tail;
        tail->prev = head;
        size = 0;
    }

    // 析构函数
    ~MyLinkedList() {
        while (size > 0) {
            removeFirst();
        }
        delete head;
        delete tail;
    }

    // ***** 增操作 *****
    void addLast(E e) {
        Node* x = new Node(e);
        Node* temp = tail->prev;

        // 连接新节点
        temp->next = x;
        x->prev = temp;
        x->next = tail;
        tail->prev = x;
        
        size++;
    }

    void addFirst(E e) {
        Node* x = new Node(e);
        Node* temp = head->next;

        // 连接新节点
        temp->prev = x;
        x->next = temp;
        head->next = x;
        x->prev = head;
        
        size++;
    }

    void add(int index, E element) {
        checkPositionIndex(index);
        
        if (index == size) {
            addLast(element);
            return;
        }

        // 找到插入位置
        Node* p = getNode(index);
        Node* temp = p->prev;
        
        // 创建并插入新节点
        Node* x = new Node(element);
        p->prev = x;
        temp->next = x;
        x->prev = temp;
        x->next = p;

        size++;
    }

    // ***** 删操作 *****
    E removeFirst() {
        if (size < 1) {
            throw std::out_of_range("No elements to remove");
        }
        
        Node* x = head->next;
        Node* temp = x->next;
        
        // 绕过被删除节点
        head->next = temp;
        temp->prev = head;

        E val = x->val;
        delete x;
        size--;
        
        return val;
    }

    E removeLast() {
        if (size < 1) {
            throw std::out_of_range("No elements to remove");
        }
        
        Node* x = tail->prev;
        Node* temp = x->prev;
        
        // 绕过被删除节点
        tail->prev = temp;
        temp->next = tail;

        E val = x->val;
        delete x;
        size--;
        
        return val;
    }

    E remove(int index) {
        checkElementIndex(index);
        
        Node* x = getNode(index);
        Node* prev = x->prev;
        Node* next = x->next;
        
        // 绕过被删除节点
        prev->next = next;
        next->prev = prev;

        E val = x->val;
        delete x;
        size--;
        
        return val;
    }

    // ***** 查操作 *****
    E get(int index) {
        checkElementIndex(index);
        return getNode(index)->val;
    }

    E getFirst() {
        if (size < 1) throw std::out_of_range("No elements");
        return head->next->val;
    }

    E getLast() {
        if (size < 1) throw std::out_of_range("No elements");
        return tail->prev->val;
    }

    // ***** 改操作 *****
    E set(int index, E val) {
        checkElementIndex(index);
        Node* p = getNode(index);
        E oldVal = p->val;
        p->val = val;
        return oldVal;
    }

    // ***** 工具函数 *****
    int getSize() const { return size; }
    bool isEmpty() const { return size == 0; }

    void display() {
        std::cout << "size = " << size << std::endl;
        for (Node* p = head->next; p != tail; p = p->next) {
            std::cout << p->val << " <-> ";
        }
        std::cout << "null" << std::endl;
    }

private:
    Node* getNode(int index) {
        checkElementIndex(index);
        Node* p = head->next;
        for (int i = 0; i < index; i++) {
            p = p->next;
        }
        return p;
    }

    bool isElementIndex(int index) const {
        return index >= 0 && index < size;
    }

    bool isPositionIndex(int index) const {
        return index >= 0 && index <= size;
    }

    void checkElementIndex(int index) const {
        if (!isElementIndex(index))
            throw std::out_of_range("Index: " + std::to_string(index) + ", Size: " + std::to_string(size));
    }

    void checkPositionIndex(int index) const {
        if (!isPositionIndex(index))
            throw std::out_of_range("Index: " + std::to_string(index) + ", Size: " + std::to_string(size));
    }
};

完整单链表实现

#include <iostream>
#include <stdexcept>

template <typename E>
class MyLinkedList2 {
private:
    struct Node {
        E val;
        Node* next;
        Node(E value) : val(value), next(nullptr) {}
    };

    Node* head;  // 虚拟头节点
    Node* tail;  // 实际尾节点
    int size_;

public:
    MyLinkedList2() {
        head = new Node(E());
        tail = head;
        size_ = 0;
    }

    ~MyLinkedList2() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }

    void addFirst(E e) {
        Node* newNode = new Node(e);
        newNode->next = head->next;
        head->next = newNode;
        
        if (size_ == 0) {
            tail = newNode;
        }
        size_++;
    }

    void addLast(E e) {
        Node* newNode = new Node(e);
        tail->next = newNode;
        tail = newNode;
        size_++;
    }

    void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size_) {
            addLast(element);
            return;
        }

        Node* prev = head;
        for (int i = 0; i < index; i++) {
            prev = prev->next;
        }
        
        Node* newNode = new Node(element);
        newNode->next = prev->next;
        prev->next = newNode;
        size_++;
    }

    E removeFirst() {
        if (isEmpty()) throw std::out_of_range("No elements");
        
        Node* first = head->next;
        head->next = first->next;
        
        if (size_ == 1) {
            tail = head;
        }
        
        size_--;
        E val = first->val;
        delete first;
        return val;
    }

    E removeLast() {
        if (isEmpty()) throw std::out_of_range("No elements");

        Node* prev = head;
        while (prev->next != tail) {
            prev = prev->next;
        }
        
        E val = tail->val;
        delete tail;
        prev->next = nullptr;
        tail = prev;
        size_--;
        return val;
    }

    E remove(int index) {
        checkElementIndex(index);

        Node* prev = head;
        for (int i = 0; i < index; i++) {
            prev = prev->next;
        }

        Node* nodeToRemove = prev->next;
        prev->next = nodeToRemove->next;
        
        if (index == size_ - 1) {
            tail = prev;
        }
        
        size_--;
        E val = nodeToRemove->val;
        delete nodeToRemove;
        return val;
    }

    // 查询操作
    E getFirst() {
        if (isEmpty()) throw std::out_of_range("No elements");
        return head->next->val;
    }

    E getLast() {
        if (isEmpty()) throw std::out_of_range("No elements");
        return tail->val;
    }

    E get(int index) {
        checkElementIndex(index);
        return getNode(index)->val;
    }

    // 修改操作
    E set(int index, E element) {
        checkElementIndex(index);
        Node* p = getNode(index);
        E oldVal = p->val;
        p->val = element;
        return oldVal;
    }

    // 工具函数
    int size() { return size_; }
    bool isEmpty() { return size_ == 0; }

private:
    Node* getNode(int index) {
        checkElementIndex(index);
        Node* p = head->next;
        for (int i = 0; i < index; i++) {
            p = p->next;
        }
        return p;
    }

    bool isElementIndex(int index) {
        return index >= 0 && index < size_;
    }

    bool isPositionIndex(int index) {
        return index >= 0 && index <= size_;
    }

    void checkElementIndex(int index) {
        if (!isElementIndex(index)) {
            throw std::out_of_range("Index: " + std::to_string(index) + ", size_: " + std::to_string(size_));
        }
    }

    void checkPositionIndex(int index) {
        if (!isPositionIndex(index)) {
            throw std::out_of_range("Index: " + std::to_string(index) + ", size_: " + std::to_string(size_));
        }
    }
};

测试和使用示例

int main() {
    // 测试双链表
    std::cout << "=== 双链表测试 ===" << std::endl;
    MyLinkedList<int> list;
    list.addLast(1);
    list.addLast(2);
    list.addLast(3);
    list.addFirst(0);
    list.add(2, 100);
    list.display();
    // 输出: 0 <-> 1 <-> 100 <-> 2 <-> 3 <-> null

    std::cout << "删除头部: " << list.removeFirst() << std::endl;
    std::cout << "删除尾部: " << list.removeLast() << std::endl;
    list.display();

    // 测试单链表
    std::cout << "\n=== 单链表测试 ===" << std::endl;
    MyLinkedList2<int> list2;
    list2.addFirst(1);
    list2.addFirst(2);
    list2.addLast(3);
    list2.addLast(4);
    list2.add(2, 5);

    std::cout << "删除头部: " << list2.removeFirst() << std::endl;
    std::cout << "删除尾部: " << list2.removeLast() << std::endl;
    std::cout << "删除中间: " << list2.remove(1) << std::endl;

    std::cout << "第一个元素: " << list2.getFirst() << std::endl;
    std::cout << "最后一个元素: " << list2.getLast() << std::endl;

    return 0;
}

复杂度分析和应用场景

时间复杂度对比

操作	数组	单链表	双链表
随机访问	O(1)	O(n)
头部插入	O(n)	O(1)	O(1)
尾部插入	O(1)	O(1)*
中间插入	O(n)	O(n)
头部删除		O(1)	O(1)
尾部删除	O(1)	O(n)
中间删除	O(n)		O(n)

注：单链表尾部插入需要维护尾指针才能达到O(1)

应用场景

适合使用链表的场景：

• 频繁在头部插入删除（栈、队列）
• 数据量不确定且频繁变化
• 不需要随机访问，主要是顺序访问

适合使用数组的场景：

• 需要频繁随机访问
• 数据量相对固定
• 内存空间紧张

总结

链表是计算机科学中至关重要的数据结构，理解它的原理和实现对于每个程序员都至关重要：

1. 单链表简单高效，适合单向遍历场景
2. 双链表功能更强，支持双向遍历，但维护成本稍高
3. 虚拟节点技巧能极大简化边界条件处理
4. 同时维护头尾指针可以优化尾部操作性能

掌握链表的实现不仅有助于理解更复杂的数据结构（如哈希链表、跳表等），也是面试和实际开发中的必备技能。建议读者亲自动手实现一遍，加深理解。