概述

由一系列 节点 通过指针连接在一起形成的线性结构，称为 链表

简单图示(C++)

链表

特性

  • 随机存储 —— 存储空间不一定连续：链表在内存中不是连续分布，分配机制取决于操作系统的内存管理，资源申请方面一般是先申请节点资源，通过指针把各个结点串成链表，资源释放方面也是以结点为单位
  • 不定长：由于结构相比数组较为松散，以节点为单位来管理资源，因此链表长度灵活，增删方便

链表种类

  • 单链表(一个指针，指向后一个结点)
  • 双链表(两个指针，分别指向前一个结点和后一个结点)
  • 循环链表(最后结点的指针指向开头结点)
  • …

实现(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
struct Node {
    int data;
    Node* next;

    Node(int dat, Node* nxt = nullptr) : data(dat), next(nxt) {}
};

class List {
public:
    List() : virtualHead_(new Node(-1)), size_(0) {}
    ~List() {
        Node* cur = virtualHead_->next;
        while (cur != nullptr) {
            Node* tmp = cur;
            cur = cur->next;
            delete tmp;
            --size_;
        }

        delete virtualHead_;
    }

    void insert(int data, int index = 0) {
        if (index < 0 || index > size_) return;
        Node* preNode = indexToNode(index - 1);
        Node* newNode = new Node(data, preNode->next);
        preNode->next = newNode;
        ++size_;
    }
    void erase(int index) {
        if (index < 0 || index >= size_) return;
        Node* preNode = indexToNode(index - 1);
        Node* cur = indexToNode(index);
        if (cur == nullptr) return;
        preNode->next = cur->next;
        delete cur;
        --size_;
    }
    int data(int index) {
        Node* cur = indexToNode(index);
        if (cur) return cur->data;
        return -1;
    }
    int size() {
        return size_;
    }

private:
    Node* indexToNode(int index) {
        Node* node = virtualHead_;
        if (index < 0 || index > size_) return node;
        int cnt = 0;
        while (node != nullptr && cnt <= index) {
            node = node->next;
            ++cnt;
        }
        return node;
    }

private:
    Node* virtualHead_ = nullptr;
    int size_;
};


复杂度分析(部分操作)

操作 时间复杂度
访问/查找元素 O(n)
插入数据 O(1)
删除数据 O(1)
扩容 O(1)

发散/随想/自身理解(?)

  • 链表是线性的，在检索数据方面较慢，需要从头结点开始遍历找到目标结点; 但长度很灵活，增删方面比数组优
  • 相比数组，需要额外存储指针结构
  • 介绍链表不如说是介绍链表的节点结构，这个在我看来才是主角，链表是节点的一种组织形式
  • 虚头节点，便于管理链表增删，视情况添加