单链表入门——定义&模板&头插法&删除_头插法的时间复杂度

单链表入门——定义&模板&头插法&删除

前言：

​ 好久不见，我是小夏；

​ 我们今天讲的是单链表，一种不同于数组的数据结构，在算法比赛和工程中都会涉及的基本数据结构；

​ 我们会分析它的时间复杂度，同时给出一种用数组模拟单链表的方法；

​ 我们会看一道来自acwing的单链表例题，我看了许多题解，文末我会提供一个链接集，给大家参考大神们的写法；

​ 让我们开始学习吧；

单链表定义

不知道你家里有没有珍珠项链——闪闪发亮，光彩炫目；

还记得我们平常时看到的高铁吗，动车是由好几组车厢链接起来的，要是我们从动车尾部上车，并且想要找到头部车厢，就只能一节一节车厢地往前走；

我们所谈的这些东西——珍珠项链、高铁动车，其实很像链表；

链表由数个结点构成，每个结点包含数据和指针。

一个结点的指针将指向下一个结点的地址。

一个车厢里有很多乘客，乘客便是数据；而车厢之间有通道连接，通道便是指针；

另一个关于指针的——我很喜欢的——比喻，是抽屉里的小纸条，

小夏说他忘记带书了，他请你帮拿一下，他留了纸条在抽屉里，

那张纸条上写着“要想找到那本书，你得去翻一翻蓝色的抽屉”，

结果你去翻了蓝色的抽屉，里面的纸条上写着“要想找到那本书，你得去翻一翻红色的抽屉”；

你按照纸条的指示一路翻找，终于找到了小夏的书；

（蓝色箭头指向的是一整个结点的地址而非红色的数据）

head为头指针，它指向第一个结点的位置；

如果head指向null，说明链表是空的；

单链表模板

以下的代码模板来自acwing

常用代码模板2——数据结构 - AcWing

它用数组来模拟链表，这样的好处是在插入时，我们可以利用ne数组找到被插入的位置，时间复杂度是O（1）；

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

include<bits/stdc++.h>
    using namespace std;

const int N = 100010;

int n;
int h[N],e[N],ne[N],head ,idx;

//初始化链表，使得该链表为空；
void init(){
    head = -1;
    idx = 0;//表示当前的指针；
}
//将x插入头结点
void int_to_head(int x){
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
    /*e[]存放的是元素，element；
ne[]存放的是指针，它指向的是下一个结点的位置；
next—element;
idx当前是0，因为我们的第一个元素的下标是从0开始；
e[0]是第一个元素；
ne[0]是第一个元素的指针，它指向下一个结点的下标；

*/
}

//将数值x插入到下标为k的结点后面，相当于串珍珠，把一颗新的珍珠串到原来珍珠项链的末端；
void add(int k , int x){
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}

void remove(int k){
    ne[k] = ne[ ne[k] ];
}

int main(){
    int t ;
    cin>>t;
    init();
    while(t–){
        char s;
        cin>>s;
        if(s == ‘H’){
            int x;
            cin>>x;
            int_to_head(x);
        }
        if(s == ‘D’){
            int k;
            cin>>k;
            if(k == 0) head =ne[head]; //删除头节点；
            else remove( k - 1 );
        }
        if(s == ‘I’){
            int k,x;
            cin>>k>>x;
            add( k-1 , x);
        }
    }
    for(int i = head ; i != -1 ; i = ne[i] )cout<<e[i]<<” “;
    cout<<endl;
    return 0;
}
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
66
67
68
69

头插法

头插法的时间复杂度是O（1），因为不需要移动后面的结点，你只需要创建一个新的结点，然后让头指针指向这个新结点就可以了；

	node->next = head->next;          //  将头指针所指向的下一个结点的地址，赋给新创建结点的next 
	head->next = node;          //  将新创建的结点的地址赋给头指针的下一个结点

1
2
3

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}
1
2
3
4
5

删除

把指针直接指向被删除的结点的指针指向的地址就可以了；

一般来说，删除的时间复杂度是O（n）,这里采用数组模拟的方法，可以使得时间复杂度降低到O（1）

void remove(int k){
    ne[k] = ne[ ne[k] ];
}
1
2
3

例题

826. 单链表 - AcWing题库

题解如下：

include<bits/stdc++.h>
    using namespace std;

const int N = 100010;

int n;
int h[N],e[N],ne[N],head ,idx;

//初始化链表，使得该链表为空；
void init(){
    head = -1;
    idx = 0;//表示当前的指针；
}
//将x插入头结点
void int_to_head(int x){
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
    /*e[]存放的是元素，element；
ne[]存放的是指针，它指向的是下一个结点的位置；
next—element;
idx当前是0，因为我们的第一个元素的下标是从0开始；
e[0]是第一个元素；
ne[0]是第一个元素的指针，它指向下一个结点的下标；

*/
}

//将数值x插入到下标为k的结点后面，相当于串珍珠，把一颗新的珍珠串到原来珍珠项链的末端；
void add(int k , int x){
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}

void remove(int k){
    ne[k] = ne[ ne[k] ];
}

int main(){
    int t ;
    cin>>t;
    init();
    while(t–){
        char s;
        cin>>s;
        if(s == ‘H’){
            int x;
            cin>>x;
            int_to_head(x);
        }
        if(s == ‘D’){
            int k;
            cin>>k;
            if(k == 0) head =ne[head]; //删除头节点；
            else remove( k - 1 );
        }
        if(s == ‘I’){
            int k,x;
            cin>>k>>x;
            add( k-1 , x);
        }
    }
    for(int i = head ; i != -1 ; i = ne[i] )cout<<e[i]<<” “;
    cout<<endl;
    return 0;
}
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
66
67
68
69

1