本章涉及知识点：
1、数组的优点和缺点
2、链表的定义和分类
3、单链表的优点和缺点
4、单链表的查找
5、单链表的更新
6、单链表的追加
7、单链表的删除
8、单链表的插入
9、单链表的反转
10、结果演示
一、数组的优点和缺点
在高级编程语言里，我们最常用的数据结构就是数组，数组是一种利用元素索引作为线索，来高效的访问元素的数据结构
数组的优点：
（1）通过元素索引作为线索来访问元素
（2）对于元素的查找和更新操作效率高
（3）方便随机访问任何元素
数组的缺点：
（1）对于元素的插入和删除操作效率低
（2）内存的分配是静态的，且内存连续，这样每次申请数组之前都必须指定数组的大小，如果大小不合理，则可能会造成内存浪费
（3）数组大小是固定的，不能动态拓展其空间
二、链表的定义和分类
链表的定义：
动态申请内存空间，用节点来保存数据，并且以节点的前驱或者后置指针作为线索来访问元素
链表根据节点的数据结构设计分为单链表和双链表
单链表的每一个节点包含：元素数据和指向下一个节点的指针，即
单链表
可以看到单链表以节点的next指针来移动，属于单边运动
双链表的每一个节点包含：元素数据和指向上一个和下一个节点的指针，即
双链表
可以看到单链表可以以节点的front和tail两个指针来移动，属于双向运动
我们本篇文章主要研究单链表的增删改查
三、单链表的优点和缺点
单链表的优点：
（1）通过节点的next指针作为线索来访问元素
（2）对于元素的插入和删除操作效率高
（3）动态分配内存，使得内存利用率高，不会造成内存浪费
（4）链表的大小不固定，方便动态扩展
单链表的缺点：
（1）对于元素的查找和修改操作效率低
（2）随机访问节点效率低
四、单链表的查找
单链表的查找：根据节点的位置index查找节点，思路很简单，直接移动next指针并递增计数位置，当计数等于查找位置，即找到待查找节点
单链表的查找
显然单链表的查找操作的时间复杂度为O(n)
五、单链表的更新
单链表的更新：根据节点的位置index查找到节点，并更新该节点的值为new_date即可，其思路和查找方法基本一致
单链表的更新
显然单链表的更新操作的时间复杂度为O(n)
六、单链表的追加
单链表的追加：在链表的末尾节点添加新节点new_node，思路也很简单，直接移动next指针到链表的末尾处，然后将末尾节点的next指针改为new_node即可
单链表的追加
显然单链表的追加操作的时间复杂度为O(n)
七、单链表的删除
单链表的删除：根据待删除节点的位置index将该节点从链表中删除，其思路如下：
（1）移动next指针，并递增计数位置，直到找到待删除节点的前驱节点
找到待删除节点的前驱节点
（2）直接修改前驱节点的后置=待删除节点的后置
修改前驱节点指向后置节点
经过上面两步，我们就将将待删除节点从链表中删除，并且保证链表的节点指针连续
单链表的删除
显然单链表的删除操作的时间复杂度为O(n)
八、单链表的插入
单链表的插入：根据待插入节点的位置index将该节点插入待该位置，其思路如下：
（1）移动next指针，并递增计数位置，直到找到待插入节点位置的前驱节点
找到待插入节点的前驱节点
（2）直接修改前驱节点的后置=new_node节点，和new_node节点的后置=原前驱节点的后置
修改新插入节点的前驱和后置
单链表的插入
显然单链表的插入操作的时间复杂度为O(n)
九、单链表的反转
单链表的反转：顾名思义，将整个链表倒置，其思路如下：
（1）从头节点（第一个节点）开始运动，设置三个变量p，q和temp，其意义为：
p指针：用来保存当前节点
q指针：用来保存当前节点的后置
temp：用来保存当前节点的后置的后置
注意：因为我们单链表是单向运动的，我们需要temp来保证在修改完p和q的指针关系后，链表能够向后移动
三个变量p，q和temp
（2）直接修改q指针的后置=p指针（反向）
修改q指针的后置=p指针
（3）修改完成后，p指针和q指针和temp向后运动一步，迭代第(2)步即可
p指针和q指针和temp向后运动一步
单链表的反转
显然单链表的反转操作的时间复杂度为O(n)
十、结果演示
我们用python实现单链表的CURD操作，做以下实验：
（1）初始化链表，头结点为0
（2）向当前链表追加10个元素
（3）在当前链表的第3个位置插入新节点
（4）查找当前链表的第3个位置元素
（5）更新当前链表的第3个位置的节点值
（6）反转整个链表
（7）删除当前链表的第9个位置元素
（8）向当前链表追加1个元素
（9）反转整个链表
实验结果为：
实验结果
实验代码见：单链表算法
网友评论