重学链表

Views: Word count in article: 7.1k Reading time ≈ 13 mins.

最近又重学了一遍链表，记得大一学链表时也是很迷，指来指去没指明白哈哈哈。这一次学也是通透多了。

单链表

基本概念

定义

1
2
3
4
typedef struct Lnode{
    int data ;
    struct Lnode *next ;
}Lnode , *Linklist ;
  • 结构体内两个元素data 、next
  • data是int型，可修改为其他，例如char、double
  • next是类型为struct Lnode的指针，可指向struct Lnode这种结构体，在链表中next指向下一个结点，例如1号结点的next = 2号结点的地址
  • Lnode是struct Lnode的别名 ， Linklist 是struct Lnode *的别名

声明一个链表

1
2
Linklist HEAD = new Lnode ;
HEAD->next = NULL ;
  • Linklist HEAD与Lnode *HEAD等价，但我们一般用Linklist HEAD来定义链表(定义链表头结点，链表头结点即代表该链表)。用Lnode *p定义一个结点
  • Linklist HEAD = new Lnode ;为头结点(头指针)分配一个大小为Lnode的空间。
  • 目前链表为空，头指针指向NULL.HEAD->next表示HEAD下一个结点地址。
  • 头指针HEAD不能严格算一个结点,HEAD->data未定义。

加入结点

1
2
3
4
Lnode *p = new Lnode ;//第一个结点p
cin >> p->data ; //输入该结点存储的数据data
HEAD->next = p ;
p->next = NULL ;
  • 再加一个结点
1
2
3
4
Lnode *q = new Lnode ;//第二个结点q
cin >> q->data ;
p->next = q ;
q->next = NULL ;
  • 注意最后一个结点的next应该指向NULL，否则q->next这个野指针无穷无尽。
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
#include<iostream>
using namespace std ;
const int N = 100010 ;
int e[N] , ne[N] , idx , head ;
void init(){
    head = -1 ;
    idx = 0 ;
}
void add_to_head(int x){
    e[idx] = x ;
    ne[idx] = head ;
    head = idx ;
    idx++ ;
}
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]] ;   
}
void print_list(){
    for(int i = head ; i != -1 ; i = ne[i]) cout << e[i] << ' ' ;
}
int main(){
    int M , k , x ;
    char operation ;
    init() ;
    cin >> M ;
    while(M--){
        cin >> operation ;
        switch(operation){
            case 'H' :
                cin >> x ;
                add_to_head(x) ;
                break ;
            case 'D' :
                cin >> k ;
                if(!k)  head = ne[head] ;
                else remove(k-1) ;
                break ;
            case 'I' :
                cin >> k >> x ;
                add(k-1 , x) ;
                break ;
            default:
                break ;
        }
        
    }
    print_list() ;
    return 0 ;
}
链表示意图.jpg

常用函数操作

  • 初始化链表(初始化头指针)
1
2
3
4
5
void InitList(Linklist &HEAD){
    //调用InitList前得先声明HEAD，例如 Linklist linkedlist_1 ，linkedlist_1即是该链表的名称(用头指针来代表链表名称，类似于用地址a来代表数组)
    HEAD = new Lnode ; //为HEAD声明一块Lnode大小的空间
    HEAD->next = NULL ;
}
  • 判断链表是否为空
1
2
3
4
int IsEmpty(Linklist &HEAD){
    if(HEAD->next) return 0 ;//非空
    return 1 ; //为空
}
  • 销毁链表
1
2
3
4
5
6
7
8
void DestroyList(Linklist &HEAD){
    Lnode *p ;
    while(HEAD){
        p = HEAD ;
        HEAD = HEAD->next  ;
        delete p ;
    }
}
  • 清空链表
1
2
3
4
5
6
7
8
9
10
void ClearList(Linklist &HEAD){
    Lnode *p , *q ;
    p = HEAD ->next ;
    HEAD->next = NULL ;
    while(p){
        q = p->next ;
        delete p ;
        p = q ;
    }
}

tips:清空链表不释放头指针空间

  • 获取链表长度
1
2
3
4
5
6
7
8
9
int GetLength(Linklist &HEAD){
    Lnode *p = HEAD->next ;
    int length = 0 ;
    while(p){
        length++ ;
        p = p->next ;
    }
    return length ;
}
  • 根据索引获取链表元素
1
2
3
4
5
6
7
8
9
10
int GetElem(Linklist &HEAD , int i){
    if(i < 0 || i >= GetLength(HEAD))   {cout << "the index is invalid" << endl ; return 0 ;}
    Lnode *p = HEAD->next ;
    int j = 0 ;
    while(j != i){
        j++ ;
        p = p->next ;
    }
    return p->data ;
}
  • 根据值确定结点索引
1
2
3
4
5
6
7
8
9
10
11
int LocateElem(Linklist &HEAD , int value){
    Lnode *p = HEAD->next ;
    int i = 0 ;
    while(p){
        if(value == p->data)    return i ;
        p = p->next ;
        i++ ;
    }
    cout << value << "not in this linkedlist" << endl ;
    return -1 ;
}
  • 插入结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ListInsert(Linklist &HEAD , int i , int data){
    if(i < 0 || i > GetLength(HEAD))    {cout << "the index is invalid" << endl ; exit(0) ;}
    Lnode *p = HEAD ;
    int j = -1 ;
    while(p && (j!=i-1)){
        p = p->next ;
        j++ ;
    }
    Lnode *s = new Lnode ;
    s->data = data ;
    s->next = HEAD->next ;
    HEAD->next = s ;
    cout << "Insert " << data << " in the index " << '[' << i << "] successfully !" << endl ;
}

tips: 此处p = HEAD从HEAD开始，j=-1 j从-1开始，是为了i=0的特殊情况。

  • 删除元素
1
2
3
4
5
6
7
8
9
10
11
12
13
void DeleteElem(Linklist &L , int i){
    if(i < 0 || i >= GetLength(L))  {cout << "the index i is invalid" << endl ; exit(0) ;}
    Lnode *p = L ;
    int j = -1 ;
    while(p && (j!=i-1)){
        p = p->next ;
        j++ ;
    }
    Lnode *s = p->next ;
    p->next = s->next ;
    delete s ;

}
  • 打印链表所有元素
1
2
3
4
5
6
7
8
void PrintList(Linklist &L){
    Lnode *p = L->next ;
    while(p){
        cout << p->data << "  " ;
        p = p->next ;
    }
    cout << endl ;
}
  • 头插法创建链表
1
2
3
4
5
6
7
8
9
10
11
void CreateList_H(Linklist &L , int n){
    //insert the nodes from the head of linkedlist
    L = new Lnode ;
    L->next = NULL ;
    for(int i = n - 1 ; i >= 0 ; i--){
        Lnode *p = new Lnode ;
        cin >> p->data ;
        p->next = L->next ;
        L->next = p ;
    }
}
  • 尾插法创建链表
1
2
3
4
5
6
7
8
9
10
11
12
void CreateList_T(Linklist &L , int n ){
    //Insert elements from the tail of linkedlist
    L = new Lnode ;
    L->next = NULL ;
    Lnode *T = L ;
    for(int i = 0 ; i < n ; i++){
        Lnode *p = new Lnode ;
        cin >> p->data ;
        T->next = p ;
        T = T->next ;
        p->next = NULL ;
    }

双向链表

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
using namespace std ;
typedef struct DoubleLinkedList
{
    int data ;
    struct DoubleLinkedList *prior , *next ;
}DLNode , *DLList;
void InitDLList (DLList &HEAD){
    HEAD = new DLNode ;
    HEAD->next = NULL ;
    HEAD->prior = NULL ;
}
void CreateList_DL(DLList &HEAD , int n){
    for(int i = 0 ; i < n ; i++){
        DLNode *p = new DLNode ;
        cin >> p->data ;
        p->next = HEAD->next ;

        if(HEAD->next){
            HEAD->next->prior = p ;
        }
        //i = 0 时，插入第一个元素时，HEAD->next 为NULL， NULL是没有的，即NULL->prior是访问不到的，segmentation fault
        //因此当HEAD->next不为NULL时，才会执行HEAD->next->prior = p 
        //当HEAD->next 为NULL，也就是创建第一个结点时，不要让(也没法让)NULL->prior = p 

        HEAD->next = p ;
        p->prior = HEAD ;
    }
}
int GetLength_DL(DLList &HEAD){
    int length = 0 ;
    DLNode *p = HEAD->next;
    while(p){
        length++ ;
        p = p->next ;
    }
    return length ;
}
void PrintList_DL(DLList &HEAD){
    DLNode *p = HEAD->next ;
    for(int i = 0 ; i < GetLength_DL(HEAD) ; i++){
        cout << p->data << "  " ;
        p = p->next ;
    }
    cout << endl ;
}
void InsertList_DL(DLList &HEAD , int i , int data){
    if( i < 0 || i > GetLength_DL(HEAD))    {cout << "the index is invalid" << endl ; exit(0) ;}
    DLNode *p = HEAD ;
    for(int j = 0 ; j < i ; j++){
        p = p->next ;
    }
    DLNode *s = new DLNode ;
    s->data = data ;
    s->next = p->next ;
    if(p->next){
        p->next->prior = s ;
    }
    p->next = s ;
    s->prior = p ;

}
void DeleteElem_DL(DLList &HEAD  , int i){
    if(i < 0 || i >= GetLength_DL(HEAD))    {cout << "the index is invalid " << endl ; exit(0) ;}
    DLNode *p = HEAD->next ;
    while(i--){
        p = p->next ;
    }
    p->prior->next = p->next ;
    p->next->prior = p->prior ;
    delete p ;
}
int main(){
    DLList HEAD ;
    InitDLList(HEAD) ;
    CreateList_DL(HEAD , 6) ;
    PrintList_DL(HEAD) ;
    InsertList_DL(HEAD , 2 , 821) ;
    PrintList_DL(HEAD) ;
    DeleteElem_DL(HEAD , 1) ;
    PrintList_DL(HEAD) ;
    return 0 ;
}

常见bugs

  • 未考虑NULL的特殊性，执行NULL->next操作。编译器还不会爆出错误信息，满大街找bug.

解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void InsertList_DL(DLList &HEAD , int i , int data){
    if( i < 0 || i > GetLength_DL(HEAD))    {cout << "the index is invalid" << endl ; exit(0) ;}
    DLNode *p = HEAD ;
    for(int j = 0 ; j < i ; j++){
        p = p->next ;
    }
    DLNode *s = new DLNode ;
    s->data = data ;
    s->next = p->next ;
    if(p->next){
        p->next->prior = s ;
    }//加入判断p->next是否为NULL
    p->next = s ;
    s->prior = p ;
}

y总的链表算法

在写AcWing上的题时，发现写的比较吃力。我在想，结构体+指针是否还不是高效的解法，就想着去看看y总的算法，y总提到：

  • 指针+结构体实现链表一般出现在面试题中，笔试题一般用数组实现链表
  • new操作太耗时，大数据量时多个new操作可能超时。Acwing单链表那道题，数组模拟链表快10%。
  • 但用数组模拟链表与动态实现链表相比，空间复杂度更大。

一些练习题