单链表

单链表的概述

链表：通过一组任意的存储单元来存储线性表中的数据元素，由一个个结点构成。

如上图所示，一般单链表的每个结点由两部分组成，一部分为存储数据的data单元(值域)，一部分为next单元(指针域)存储指向下一个结点的指针。

特别地，为了方便链表的插入和删除操作，一般我们会设置一个头结点，仅供我们方便进行操作。

链表和顺序表的比较：

​ 1、链表的每个结点的存储空间可以不连续，而顺序表一定要连续。

​ 2、链表的空间大小不固定，可更具自己的要求改变，顺序表的空间大小是在初始化时分配好的，不能改变

​ 3、链表的空间利用程度更低(因为指针域)

​ 4、链表更适合增加和删除操作，而顺序表更适合查询操作

单链表的模板

用数组模拟单链表

为什么要用数组来模拟链表呢？在很多算法题和笔试中实际不需要考虑内存是否浪费的问题，而频繁的使用构造一个新结点的new操作却又非常消耗时间很容易就会超时，所以我们此时选择这种用空间来换取时间的做法。

1、初始化

vector val, ne;//val数组充当结点的值，ne数组充当结点的next 指针
int head = -1, now = 0;//head 充当指向头结点的指针初始值为-1（相当于链表为空）
                        //now 为当前可利用的结点的下标

2、在头结点处插入值为x的结点

void add_to_head(int x){
    val.push_back(x);
    ne.push_back(1);//相当于开辟一个新空间
    ne[now] = head;//新结点的指针指向头结点指向的结点
    head = now ++ ;//头结点指向新结点
}

3、在第k个插入的结点后面插入x

void add(int k, int x){
    val.push_back(x);
    ne.push_back(1);//为x开辟一个空间
    ne[now] = ne[k - 1];
    ne[k - 1] = now ++;
}
//注意这里时第k个插入的数，而不是链表的第k个数
void add(int k, int x){//如果想在链表的第k个数后面插入
    val.push_back(x);
    ne.push_back(x);
    int p = head, k -- ;
    while(k -- )    p = ne[p];
    ne[now] = ne[p];
    ne[p] = now ++;
}
//这种插入的时间复杂度为o(n), 在很多算法题中实际不需要这么实现，而是用第一种方法来插入
//因为一套完整的插入删除操作算作一个链表建立的初始化用第一个操作完全能实现，时间也能节省很多

4、删除第k个插入的结点后面插入的结点

void remove(int k){
    if (k == 0) head = ne[head];
    else ne[k - 1] = ne[ne[k - 1]];
}
//注意这里时第k个插入的数，而不是链表的第k个数
//如果想删除链表的第k个数实现方法和前面相似，这里就不写了

真正的单链表

在实际的工程问题中，当然就不只需要考虑时间的问题了，同时也应该非常在乎内存的消耗问题，毕竟…那可是钱啊……

1、初始化

typedef struct node{//结点的结构体
    int val;
    struct node *next;
}Node;
Node *head = new Node;//头指针

2、在表头插入

void add_to_head(int x){
    Node *p = new Node;//为新结点开辟空间
    p->val = x;
    p->next = head->next;
    head->next = p;
}//其实实现逻辑和前面的数组模拟一样

3、在链表的第K个元素后插入

在单链表中这种在某个元素后插入的情况非常少，太费时了，一般都采用头插法或者尾插法

void add(int k, int x){
    Node *p = new Node;
    p->val = x;
    Node *now = head;
    while(k -- ) now = now->next;
    p->next = now->next;
    now->next = p;
}//引入头结点后将k置为0即是头插法

4、删除第K位后面的结点

void remove(int k){ 
    Node *p = head;
    while(k -- ) p = p->next;
    Node *q = p->next;
    p->next = p->next->next;
    delete q; 
}