链表

链表介绍

  • 线性表数据结构
  • 内存空间不连续，将分散的内存块串联起来，进行数据存储
  • 链表的每个数据节点，不仅存储数据还要存储下一个节点的地址

链表特点

  • 由于链表的数据结构，插入、删除效率高(改变指针指向即可)，时间复杂度 $O(1)$，但是随机访问的速度较慢，需要从头遍历链表。这个和数组相反
  • 由于链表的节点不仅存储数据还要存储下一节点的指针，所以存储空间相较于数组消耗较大

单链表、循环链表、双向链表、双向循环链表

单链表

  • 每个节点存储数据和下一个节点的指针，即后继指针
  • 第一个节点是头结点，记录链表的基地址；最后一个是尾节点，指向 NULL
  • 单链表的的插入和删除的时间复杂度是 $O(1)$，查询的时间复杂度是 $O(n)$。

循环链表

  • 尾节点的后继节点是头结点
  • 比较适合于处理环形数据结构的问题，例如约瑟夫环问题

双向链表

  • 每个节点有后继指针和前驱指针；头结点的前驱指针是 NULL，尾节点的后继指针是 NULL
  • 插入、删除操作比单链表效率更高 $O(1)$ 级别。以删除操作为例，删除操作分为 2 种情况：给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为 $O(n)$ 。对于第二种情况，要进行删除操作必须找到前驱节点，单链表需要从头到尾进行遍历直到 p->next = q，时间复杂度为 $O(n)$，而双向链表可以直接找到前驱节点，时间复杂度为 $O(1)$。

双向循环链表

  • 首节点的前驱指针指向尾节点，尾节点的后继指针指向首节点

指针和引用

  • 指针和引用是同一个概念，都是存储所指对象的内存地址
  • 将某个变量赋值给指针就是将变量的内存地址赋值给指针；对应的就是指针存储的就是变量的内存地址，通过这个指针就可以找到这个变量

指针丢失、内存泄漏

  • 链表操作时，要注意指针的交换顺序，避免出现指针丢失的情况。例如，要在当前节点 p 插入节点 x，示例1的操作会导致 x->next = x，造成整个链表断裂；只需将两个语句顺序交换即可。
    1
    2
    3
    4
    5
    6
    // 示例 1
    p->next = x;
    x->next = p->next;
    // 示例 2
    x->next = p->next;
    p->next = x;
  • 在没有自动管理内存的编程语言，再删除节点后要手动释放内存空间，避免造成内存泄漏

利用哨兵实现插入、删除

  • 针对链表的插入、删除，插入时需要对链表的第一个节点和最后一个节点进行特殊判断；
  • 引入哨兵，“哨兵”节点不存储数据，无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在。这样，插入第一个节点和插入其他节点，删除最后一个节点和删除其他节点都可以统一为相同的代码实现逻辑了。