C/C++ 如何实现和使用链表（linked list）

由于实现链表（Linked List）是实现一种数据结构，使用结构体（structure），而不是必须使用 Class。所以 C 和 C++ 没区别。

需要说明一下，这里的一些名词和一些教材上所指不同，需要注意哦！

链表原理

链表其实是一个个连接起来的节点，每个节点包含两个数据：值和下一个节点的地址。

如下是一个有三个节点的链表，nullptr是表示链表结尾的指针：

实现链表

知道了链表的数据结构，实现起来就是照做。

第一步：实现链表节点的数据结构

下面这个结构体就声明了一个数据结构，包含了一个值（这个类型自己决定）和一个指针（用于存放指向下一节点的指针或者末尾指针nullptr），就可以实现链表的基础数据结构（也是通常实现链表的方式）：

struct ListNode
{
	//这里的数据类型自己决定
	int val;
	//之所以这里需要使用 ListNode 本身，因为一个链表的节点大小是一个 ListNode 的大小
	ListNode *next;
}
1
2
3
4
5
6
7

第二点：实现一个简短的链表

上面声明了链表节点的数据结构，只需要穿起来就可以实现一个链表了。下面来实现一个简单的链表：

int main() {
    //声明节点
    ListNode *a, *b, *c;
    //为每个节点动态分配内存空间
    a=new ListNode();
    b=new ListNode();
    c=new ListNode();
    //初始化每个节点
    a->val=10;
    a->next=b;
    b->val=11;
    b->next=c;
    c->val=12;
    c->next=nullptr;
    //输出最后一个节点的两种方式
    //直接通过第三个节点c
    cout<<c->val<<endl;
    //通过第一个节点一步步跳转
    cout<<a->next->next->val<<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

第三步：如何实现和按顺序输出一个较长的链表呢？

有两种方法：

1. 在写代码的时候，一个一个节点的输入；
2. 在编译后，一个个输入；
3. 使用迭代来输出多个值。

前二者就像上文，使用起来不是特别方便，而且也说过了，所以这里讲一下第三种。

方法如下：

#include 

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
};


int main() {
	//head 是头节点，因为要通过它来访问，所以需要放在迭代之外
	//temp 是迭代途中为了生成新的地址所需的
	//tail 就是最后一个节点，迭代只要负责设置最后一个节点即可
    ListNode *head, *temp, *tail;
    int i;
    
    //初始化头节点和尾节点
    head = new ListNode;
    tail = new ListNode;
    
    //输出十个数，从10到0
    i=10;
    
    //先设置好头节点的值
    head->val=i;
    head->next=tail;
    //开始迭代
    while (i>0){
    	//为尾节点赋值
        tail->val = --i;
        //（再次）初始化temp
        temp = new ListNode;
        //把尾节点存储的下一个节点的值变成temp
        tail->next = temp;
        //这时候将tail变成之前存储的下一个节点的空间，也就是上面next地址指向的空间
        tail = temp;
    }
    
    //输出
    while (head->next!=nullptr){
        cout<<head->val<<endl;
        head=head->next;
    }
    
    
    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

输出结果如下：

10
9
8
7
6
5
4
3
2
1
0
1
2
3
4
5
6
7
8
9
10
11

希望可以帮到有需要的人～