链表这玩意属于很基础的数据结构了，因为太基础了，所以还是给它留一篇笔记比较好
链表的每个节点都存有值和下一个（或者是上一个或者两个兼有）节点的地址，这样的结构能很方便地插入与删除元素
节点
这就是一个节点，如果对那个构造函数不熟悉，可以去瞧瞧和类相关的东西
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;
}
然后呢？
然后链表的基础功能都实现了，接下来就可以往里面添加自己喜欢的功能了，比如获取长度，输出整个表之类的
太棒了面向对象