链表概念的讲解 链表是什么： 链表是一种线性数据结构，每个节点都存有数据，通过指针将各个节点链接在一起。 链表的性质： 一致性: 每个节点有相同的数据结构，相同的数据大小，内存中占据相同的大小，存储相同的数据类型。 有序性: 节点之间的相对顺序固定，排在某节点前面的节点就是它的前驱，后面的节点就是它的后继，所以定义里面有’线性’。 链表的分类： 链接方式分类：单向链表，双向链表。 ps: 代码展示只用单链表举例。 单链表结构 单链表中的每个结点包含数据+指向后继节点的指针，通过这种方式，单链表将所有结点按顺序组织起来。 节点定义： 双链表结构 双链表中的每个节点包含数据+指向前驱和后继的指针。 链表的基本操作： 链表基本操作: 插入、搜索、删除。 以下分别讲每个操作是如何进行的，时间复杂度多少，为什么是那么多，根据时间复杂度判断链表的适合场景。 查找 按照索引/值查找：遍历找到对应的位置/值，然后返回该节点。 时间复杂度：是线性遍历的，所以时间复杂度是 O(n)。因为时间复杂度相对较高，所以在大量数据需要经常用检索的时候就不要用链表了。 插入 按照 index 插入 先创建新节点 new_node； 找到要插入的位置的前驱节点 pre； 新节点 new_node 指向 pre 的后继节点； pre 指向新节点。 时间复杂度：由于第2步要线性遍历去找 index 位置，所以时间复杂度是 O(n)。如果插入在头部，就不需要找位置，时间复杂度是 O(1)。 删除 如何做删除的？ 找到待删节点的前驱 pred； 把它的前驱节点的后继指向待删节点后继的后继。 时间复杂度：因为要去找前驱，所以线性遍历，时间复杂度是 O(n)。如果删除头部，就不需要找位置，时间复杂度是 O(1)。 链表常见的考点: 哑节点(边界条件)-用于简化边界情况，链表为空或链表的头结点和尾节点。解决办法：自己创建一个哑节点，然后把它的后继连接原节点。 […]