把它们链在一起

链表这玩意属于很基础的数据结构了，因为太基础了，所以还是给它留一篇笔记比较好

链表的每个节点都存有值和下一个（或者是上一个或者两个兼有）节点的地址，这样的结构能很方便地插入与删除元素

节点

这就是一个节点，如果对那个构造函数不熟悉，可以去瞧瞧和类相关的东西

typedef struct node{
    int val;
    node *next;
    node(int x) : val(x), next(nullptr) {}
} node;

很简单，只有一个int和一个地址 其实不用typedef也没事

表

因为C艹轮子很多（至少比C好使得多），所以以下内容都写在类里面

简单的构造

class LinkedList{
private:
    node *head, *tail;
    int size;
public:
    LinkedList(node *h) {
        head = h;
        tail = h;
        size = 1;
        head -> next = tail;
    }
  ~LinkedList() {
    if (size == 0) return; // 防止没有头的特殊情况

    while (head != nullptr) {
      node *temp = head;
      if (head -> next == head) {  // 一样是防止特殊情况
        return;
      }
      head = head -> next;
      delete temp;
    }
  }
}

~~为了偷懒，~~这里直接传入了一个结点作为链表的头，当它的生命结束时，下面的析构函数就会发挥作用释放内存

添加（追加）节点

因为列表太好用了，所以我给链表加个append也没事吧（

void append(int a) {
    node *temp = new node(a);
    size++;
    if (size == 2) {
        tail -> next = temp;
        tail = tail -> next;
        head -> next = tail;
    }
    else if(size == 1) {
        head = temp;
        tail = temp;
        head -> next = tail;
    }
    else {
        tail -> next = temp;
        tail = tail -> next;
    }
}

这里是先分配了一个新的节点，然后size++，再对两种特殊情况进行判断，不然可能会有意想不到的事情发生……如果不是那些情况的话，直接在尾巴后面再加一个节点就好

插入节点

链表最大的优势，在某个节点之后再插入一个

void insert(int x, int v) {
    if (x >= size) return;
    node *temp = new node(v), *p = head;
    for (int i = 0; i < x; i++) {
        p = p -> next;
    }
    size++;
    temp -> next = p -> next;
    p -> next = temp;
    if (x == size - 1) {
        tail = temp;
    }
}

没啥特别的，就是一个很经典的插入，如果是在最后一个节点插入，那也要把尾节点更新一下

删除节点

就是删除对应的节点

void remove(int x) {
    if (x >= size) return;
    node *p = head;
    if (x == 0) {
        node *temp = head;
        head = head -> next;
        delete temp;
        size--;
        return;
    }
    for (int i = 0; i < x - 1; i++) {
        p = p -> next;
    }
    if (p -> next == nullptr) { // 其实我也搞不懂为啥这里我要这么写
        tail = p;
        return;
    }
    node *temp = p -> next, *q = temp -> next;
    p -> next = q;
    size--;
    delete temp;
}

如果删的是头节点，还得把头节点更新一下

访问节点

对于某个数据结构，访问其元素显然是必须的。为了偷懒方便，这里可以直接返回节点的指针

node *access(int index) {
    if (index >= size) return(nullptr);
    node *p = head;
    for (int i = 0; i < index; i++) {
        p = p -> next;
    }
    return p;
}

如果越界了，就给一个空指针吧(￣﹃￣)

虽然我觉得抛出一个异常会优雅（

寻找节点

给你一个值，找到第一个是这个值的节点，没找到就返回-1了

和上面差不多，时间复杂度都是$O(n)$

int find(int v) {
    int i = 0;
    for (node *p = head; p != nullptr; p = p -> next) {
        if (p -> val == v) return i;
        i++;
    }
    return -1;
}

然后呢？

然后链表的基础功能都实现了，接下来就可以往里面添加自己喜欢的功能了，比如获取长度，输出整个表之类的

太棒了面向对象