# 链表理论基础

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域，一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向 NULL。

链表的入口节点被称为链表的头结点也就是 head。

# 链表类型

# 单链表

单链表中的指针域只能指向节点的下一个节点。

# 双链表

每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表既可以向前查询也可以向后查询。

# 循环链表

链表首尾相连，可以来解决约瑟夫环问题。

# 链表的存储方式

数组在内存中是连续分布的，但是链表在内存中不是连续分布的。

链表是散乱的分布在内存的某地址上，分配机制取决于操作系统的内存管理，通过指针域的指针链接在内存中各个节点。

# 链表的操作

# 删除节点

删除下图中的 D 节点：只需要将 C 节点的 next 指针指向 E 节点即可，时间复杂度$O(1)$。

但是要注意，要是删除第最后一个节点，需要从头节点查找到倒数第二个节点通过 next 指针进行删除操作，查找的时间复杂度是 O (n)。

删除之后 D 节点依然留存在内存中，只不过并不存在这个链表当中。

C/C++ 最好手动释放这个节点所占用的内存。

Java、Pthon 等有自己的内存回收机制，不需要手动释放。

# 添加节点

在下图链表中插入 F 节点：C 节点 next 指针指向 F 节点，F 节点 next 指针指向 D 节点，时间复杂度$O(1)$。

# 性能分析

数组和链表性能比较

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。