数据结构之线性表之链表(附加一个考研题)

链表的定义

链表的结构：

单链表-初始化

代码实现：

单链表-头插法

代码实现：

这里我给大家分析一下

我们每创建一个新的节点都要插在头节点的后面，我们一定要注意顺序

一定要先让新节点指向头节点指向的下一个节点，再让头节点指向新的节点

单链表-遍历

代码实现：

代码分析：

这里我定义了一个指针p，p指向第一个节点的地址，判断p是否为空指针，不为空指针，打印这个节点的数据，并让p指向下一个节点，依次类推，直到指向的下一个节点为空指针

单链表-尾插法

代码实现：

单链表-在指定位置插入

代码实现：

单链表-根据数据或学号什么的删除一个节点

代码实现：

单链表-获取链表的长度

代码实现：

我们来看一下结果吧

代码展示：

单链表-释放节点

代码实现：

代码展示：

我们来做一道题

我们利用双指针的思想来解决这道题，这是一个套路，大家记住就可以了

分析：

我们会有两个指针，一个快指针，一个慢指针，我们要倒数第几个，就让快指针走几步，然后在快指针和慢指针一块走，当快指针指向NULL的时候，慢指针正好指向了我们要找的那个节点，然后我们打印这个节点的数据值就可以了

代码实现：

代码结果：

循环链表：

就一个不一样的点是尾节点指向的是头节点，一般的尾节点指向的是NULL

接下来我们直接进入双向链表吧！

双向链表无非就是多了一个前驱，其他都一样

双向链表的定义：

双向链表的结构：

双向链表-头插法

代码实现：

结果：

遍历的代码跟原来一样

双向链表-尾插法

代码实现：

结果：

双向链表-根据数据删除节点

代码实现：

双向链表的遍历和释放跟单链表是一样的

到这里链表就结束了，后面就是刷题在巩固巩固就可以了