【学习笔记】【数据结构与算法篇】链表

什么是链表？是一种线性表，但不按线性存储，即内存不连续，链表在每一个节点里存到下一个节点的指针(Pointer)，从而形成顺序关系。

数据结构的意思指的是，我们如何在计算机中存储及表示我们的数据

链表的第一个元素，称之为头节点。

如果链表的最后的一个元素指向了头节点，那么这个链表就成为了一个环。就像一条咬到自己尾巴的蛇。

我们用线性表存储我们的数据时，依然（同数组）是需要 CRUD 四个操作：

• 插入
• 更新
• 删除
• 查询

CRUB 操作分析

插入

比如说，我们要在 linklist[5] 这个位置之后插入数据，这个我们分为两种情况讨论。

第一种是，我们有头节点的指针，也就是 [0] ，然后需要一个个遍历，一直数到 5 ，才可以插入数据，插入方式就是将当前节点的下个节点指向指针指向新创建的节点，将下个节点的地址赋值给新创建节点的下个节点指向指针，这种情况，前面包括了一个查询，所以，时间复杂度为 O(n);

第二种情况，就是我们已经有了 linklist[5] 的指针，那就直接插入就是，时间复杂度 O(1).

删除

删除基本同上，将待删除节点的下个节点指向指针赋值给待删除节点的上个节点下个节点指向指针，然后清理掉待删除节点，时间复杂度 O(n) 或 O(1)

更新和查询

查询与更新都需要遍历数据， O(n)

其它链表

上面的这种是单链表，还有循环链表、双向链表、双向循环链表、静态链表等