一、链表的基本原理

刷过力扣的读者肯定对单链表非常熟悉，力扣上的单链表节点定义如下：

private:
    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;
        }
    };：

实际的定义：

private:
    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;
        }
    };

主要区别有两个：

• 1、编程语言标准库一般都会提供泛型，即你可以指定 val 字段为任意类型，而力扣的单链表节点的 val 字段只有 int 类型。

• 2、编程语言标准库一般使用的都是双链表而非单链表。单链表节点只有一个 next 指针，指向下一个节点；而双链表节点有两个指针，prev 指向前一个节点，next 指向下一个节点。

有了 prev 前驱指针，链表支持双向遍历，但由于要多维护一个指针，增删查改时会稍微复杂一些，后面带大家实现双链表时会具体介绍。

为什么需要链表

主要区别有两个：

1、编程语言标准库一般都会提供泛型，即你可以指定 val 字段为任意类型，而力扣的单链表节点的 val 字段只有 int 类型。

2、编程语言标准库一般使用的都是双链表而非单链表。单链表节点只有一个 next 指针，指向下一个节点；而双链表节点有两个指针，prev 指向前一个节点，next 指向下一个节点。

有了 prev 前驱指针，链表支持双向遍历，但由于要多维护一个指针，增删查改时会稍微复杂一些，后面带大家实现双链表时会具体介绍

二、单链表的基本操作

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

// 输入一个数组，转换为一条单链表
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;
}

1.查/改（单链表的遍历/查找/修改）

// 创建一条单链表
ListNode* head = createLinkedList({1, 2, 3, 4, 5});

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

2.增

（1）在单链表头部插入新元素

// 创建一条单链表
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

（2）在单链表尾部插入新元素

// 创建一条单链表
ListNode* head = createLinkedList({1, 2, 3, 4, 5});

// 在单链表尾部插入一个新节点 6
ListNode* p = head;
// 先走到链表的最后一个节点
while (p->next != nullptr) {
    p = p->next;
}
// 现在 p 就是链表的最后一个节点
// 在 p 后面插入新节点
p->next = new ListNode(6);

// 现在链表变成了 1 -> 2 -> 3 -> 4 -> 5 -> 6

（3）在单链表中间插入新元素

// 创建一条单链表
ListNode* head = createLinkedList({1, 2, 3, 4, 5});

// 在第 3 个节点后面插入一个新节点 66
// 先要找到前驱节点，即第 3 个节点
ListNode* p = head;
for (int i = 0; i < 2; i++) {
    p = p->next;
}
// 此时 p 指向第 3 个节点
// 组装新节点的后驱指针
ListNode* newNode = new ListNode(66);
newNode->next = p->next;

// 插入新节点
p->next = newNode;

// 现在链表变成了 1 -> 2 -> 3 -> 66 -> 4 -> 5

3.删

（1）在单链表中删除一个节点

删除一个节点，首先要找到要被删除节点的前驱节点，然后把这个前驱节点的 next 指针指向被删除节点的下一个节点。这样就能把被删除节点从链表中摘除了。

// 创建一条单链表
ListNode* head = createLinkedList({1, 2, 3, 4, 5});

// 删除第 4 个节点，要操作前驱节点
ListNode* p = head;
for (int i = 0; i < 2; i++) {
    p = p->next;
}

// 此时 p 指向第 3 个节点，即要删除节点的前驱节点
// 把第 4 个节点从链表中摘除
p->next = p->next->next;

// 现在链表变成了 1 -> 2 -> 3 -> 5

（2）在单链表尾部删除元素

这个操作比较简单，找到倒数第二个节点，然后把它的 next 指针置为 null 就行了：

// 创建一条单链表
ListNode* head = createLinkedList({1, 2, 3, 4, 5});

// 删除尾节点
ListNode* p = head;
// 找到倒数第二个节点
while (p->next->next != nullptr) {
    p = p->next;
}

// 此时 p 指向倒数第二个节点
// 把尾节点从链表中摘除
p->next = nullptr;

// 现在链表变成了 1 -> 2 -> 3 -> 4

（3）在单链表头部删除元素

// 创建一条单链表
ListNode* head = createLinkedList(vector<int>{1, 2, 3, 4, 5});

// 删除头结点
head = head->next;

// 现在链表变成了 2 -> 3 -> 4 -> 5

三、双链表的基本操作

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

DoublyListNode* createDoublyLinkedList(const vector<int>& arr) {
    if (arr.empty()) {
        return NULL;
    }
    DoublyListNode* head = new DoublyListNode(arr[0]);
    DoublyListNode* cur = head;
    // for 循环迭代创建双链表
    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;
}

1.查/改（双链表的遍历/查找/修改）

// 创建一条双链表
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});
DoublyListNode* tail = nullptr;

// 从头节点向后遍历双链表
for (DoublyListNode* p = head; p != nullptr; p = p->next) {
    cout << p->val << endl;
    tail = p;
}

// 从尾节点向前遍历双链表
for (DoublyListNode* p = tail; p != nullptr; p = p->prev) {
    cout << p->val << endl;
}

访问或修改节点时，可以根据索引是靠近头部还是尾部，选择合适的方向遍历，这样可以一定程度上提高效率。

2.增

（1）在双链表头部插入新元素

// 创建一条双链表
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});

// 在双链表头部插入新节点 0
DoublyListNode* newHead = new DoublyListNode(0);
newHead->next = head;
head->prev = newHead;
head = newHead;

// 现在链表变成了 0 -> 1 -> 2 -> 3 -> 4 -> 5

（2）在双链表尾部插入新元素

// 创建一条双链表
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});

DoublyListNode* tail = head;
// 先走到链表的最后一个节点
while (tail->next != nullptr) {
    tail = tail->next;
}

// 在双链表尾部插入新节点 6
DoublyListNode* newNode = new DoublyListNode(6);
tail->next = newNode;
newNode->prev = tail;
// 更新尾节点引用
tail = newNode;

// 现在链表变成了 1 -> 2 -> 3 -> 4 -> 5 -> 6

（3）在双链表中间插入新元素

// 创建一条双链表
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});

// 想要插入到索引 3（第 4 个节点）
// 需要操作索引 2（第 3 个节点）的指针
DoublyListNode* p = head;
for (int i = 0; i < 2; i++) {
    p = p->next;
}

// 组装新节点
DoublyListNode* newNode = new DoublyListNode(66);
newNode->next = p->next;
newNode->prev = p;

// 插入新节点
p->next->prev = newNode;
p->next = newNode;

// 现在链表变成了 1 -> 2 -> 3 -> 66 -> 4 -> 5

3.删

（1）在双链表中删除一个节点

// 创建一个双链表
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});

// 删除第 4 个节点
// 先找到第 3 个节点
DoublyListNode* p = head;
for (int i = 0; i < 2; ++i) {
    p = p->next;
}

// 现在 p 指向第 3 个节点，我们将它后面那个节点摘除出去
DoublyListNode* toDelete = p->next;

// 把 toDelete 从链表中摘除
p->next = toDelete->next;
toDelete->next->prev = p;

// 把 toDelete 的前后指针都置为 null 是个好习惯（可选）
toDelete->next = nullptr;
toDelete->prev = nullptr;

// 现在链表变成了 1 -> 2 -> 3 -> 5

（2）在双链表头删除一个结点

// 创建一条双链表
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});

// 删除头结点
DoublyListNode* toDelete = head;
head = head->next;
head->prev = nullptr;

// 清理已删除节点的指针
toDelete->next = nullptr;

// 现在链表变成了 2 -> 3 -> 4 -> 5

（3）在双链表尾部删除元素

// 创建一条双链表
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});

// 删除尾节点
DoublyListNode* p = head;
// 找到尾结点
while (p->next != nullptr) {
    p = p->next;
}

// 现在 p 指向尾节点
// 把尾节点从链表中摘除
p->prev->next = nullptr;

// 把被删结点的指针都断开是个好习惯（可选）
p->prev = nullptr;

// 现在链表变成了 1 -> 2 -> 3 -> 4

四、关键点

1.同时持有头尾节点的引用

在力扣做题时，一般题目给我们传入的就是单链表的头指针。但是在实际开发中，用的都是双链表，而双链表一般会同时持有头尾节点的引用。

因为在软件开发中，在容器尾部添加元素是个非常高频的操作，双链表持有尾部节点的引用，就可以在 O(1) 的时间复杂度内完成尾部添加元素的操作。

对于单链表来说，持有尾部节点的引用也有优化效果。比如你要在单链表尾部添加元素，如果没有尾部节点的引用，你就需要遍历整个链表找到尾部节点，时间复杂度是
O(n)；如果有尾部节点的引用，就可以在 O(1) 的时间复杂度内完成尾部添加元素的操作。

即便如此，如果删除一次单链表的尾结点，那么之前尾结点的引用就失效了，还是需要遍历一遍链表找到尾结点。

是的，但你再仔细想想，删除单链表尾结点的时候，是不是也得遍历到倒数第二个节点（尾结点的前驱），才能通过指针操作把尾结点删掉？那么这个时候，你不就可以顺便把尾结点的引用给更新了吗

2.虚拟头尾节点举例来说，假设虚拟头尾节点分别是 dummyHead 和 dummyTail，那么一条空的双链表长这样：

dummyHead <-> dummyTail

如果你添加 1,2,3 几个元素，那么链表长这样：

dummyHead <-> 1 <-> 2 <-> 3 <-> dummyTail

你以前要把在头部插入元素、在尾部插入元素和在中间插入元素几种情况分开讨论，现在有了头尾虚拟节点，无论链表是否为空，都只需要考虑在中间插入元素的情况就可以了，这样代码会简洁很多。

当然，虚拟头结点会多占用一点内存空间，但是比起给你解决的麻烦，这点空间消耗是划算的。

对于单链表，虚拟头结点有一定的简化作用，但虚拟尾节点没有太大作用。

虚拟节点是内部实现，对外不可见

虚拟节点是你内部实现数据结构的技巧，对外是不可见的。比如按照索引获取元素的 get(index) 方法，都是从真实节点开始计算索引，而不是从虚拟节点开始计算

五、代码实现

单链表

#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 to remove");
        }
        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 to remove");
        }

        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 in the list");
        }
        return head->next->val;
    }

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

    E get(int index) {
        checkElementIndex(index);
        Node* p = getNode(index);
        return p->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:
    bool isElementIndex(int index) {
        return index >= 0 && index < size_;
    }

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

    // 检查 index 索引位置是否可以存在元素
    void checkElementIndex(int index) {
        if (!isElementIndex(index)) {
            throw std::out_of_range("Index: " + std::to_string(index) + ", size_: " + std::to_string(size_));
        }
    }

    // 检查 index 索引位置是否可以添加元素
    void checkPositionIndex(int index) {
        if (!isPositionIndex(index)) {
            throw std::out_of_range("Index: " + std::to_string(index) + ", size_: " + std::to_string(size_));
        }
    }

    // 返回 index 对应的 Node
    // 注意：请保证传入的 index 是合法的
    Node* getNode(int index) {
        Node* p = head->next;
        for (int i = 0; i < index; i++) {
            p = p->next;
        }
        return p;
    }
};

int main() {
    MyLinkedList2<int> list;
    list.addFirst(1);
    list.addFirst(2);
    list.addLast(3);
    list.addLast(4);
    list.add(2, 5);

    std::cout << list.removeFirst() << std::endl; // 2
    std::cout << list.removeLast() << std::endl; // 4
    std::cout << list.remove(1) << std::endl; // 5

    std::cout << list.getFirst() << std::endl; // 1
    std::cout << list.getLast() << std::endl; // 3
    std::cout << list.get(1) << std::endl; // 3

    return 0;
}

双链表

#include <iostream>
#include <stdexcept>

template<typename E>
class MyLinkedList {
    // 虚拟头尾节点
    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;
        // temp <-> x

        x->next = tail;
        tail->prev = x;
        // temp <-> x <-> tail
        size++;
    }

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

        head->next = x;
        x->prev = head;
        // head <-> x <-> temp
        size++;
    }

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

        // 找到 index 对应的 Node
        Node* p = getNode(index);
        Node* temp = p->prev;
        // temp <-> p

        // 新要插入的 Node
        Node* x = new Node(element);

        p->prev = x;
        temp->next = x;

        x->prev = temp;
        x->next = p;

        // temp <-> x <-> 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 <-> x <-> temp
        head->next = temp;
        temp->prev = head;

        E val = x->val;
        delete x;
        // head <-> temp

        size--;
        return val;
    }

    E removeLast() {
        if (size < 1) {
            throw std::out_of_range("No elements to remove");
        }
        Node* x = tail->prev;
        Node* temp = tail->prev->prev;
        // temp <-> x <-> tail

        tail->prev = temp;
        temp->next = tail;

        E val = x->val;
        x->prev = nullptr;
        x->next = nullptr;
        delete x;
        // temp <-> tail

        size--;
        return val;
    }

    E remove(int index) {
        checkElementIndex(index);
        // 找到 index 对应的 Node
        Node* x = getNode(index);
        Node* prev = x->prev;
        Node* next = x->next;
        // prev <-> x <-> next
        prev->next = next;
        next->prev = prev;

        E val = x->val;
        x->prev = nullptr;
        x->next = nullptr;
        delete x;
        // prev <-> next

        size--;
        return val;
    }

    // ***** 查 *****

    E get(int index) {
        checkElementIndex(index);
        // 找到 index 对应的 Node
        Node* p = getNode(index);

        return p->val;
    }

    E getFirst() {
        if (size < 1) {
            throw std::out_of_range("No elements in the list");
        }

        return head->next->val;
    }

    E getLast() {
        if (size < 1) {
            throw std::out_of_range("No elements in the list");
        }

        return tail->prev->val;
    }

    // ***** 改 *****

    E set(int index, E val) {
        checkElementIndex(index);
        // 找到 index 对应的 Node
        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 << "nullptr" << std::endl;
        std::cout << std::endl;
    }

private:
    Node* getNode(int index) {
        checkElementIndex(index);
        Node* p = head->next;
        // TODO: 可以优化，通过 index 判断从 head 还是 tail 开始遍历
        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;
    }

    // 检查 index 索引位置是否可以存在元素
    void checkElementIndex(int index) const {
        if (!isElementIndex(index))
            throw std::out_of_range("Index: " + std::to_string(index) + ", Size: " + std::to_string(size));
    }

    // 检查 index 索引位置是否可以添加元素
    void checkPositionIndex(int index) const {
        if (!isPositionIndex(index))
            throw std::out_of_range("Index: " + std::to_string(index) + ", Size: " + std::to_string(size));
    }
};

int main() {
    MyLinkedList<int> list;
    list.addLast(1);
    list.addLast(2);
    list.addLast(3);
    list.addFirst(0);
    list.add(2, 100);

    list.display();
    // size = 5
    // 0 <-> 1 <-> 100 <-> 2 <-> 3 <-> null

    return 0;
}