链表

特点

• 不需要一块连续的内存空间，它通过“指针”将一组不连续的内存空间串联起来使用

常见的链表结构

单向链表

• 只有一个后继指针next
• 与数组相比，删除和插入操作比较方便，复杂度为O(1)，而随机访问性不如数组，复杂度为O(n)

单向循环链表

• 与单向链表相比，从尾结点到头节点的访问比较方便
• 当要处理的数据具有环形的特点时，特别适合使用循环链表

双向链表

• 多了一个前驱指针prev

• 与单向链表相比，访问节点要更灵活，但是占用内存要更多

• 在某些情况下，双向链表的插入和删除操作要比单向链表更高效

  • 在指定节点前插入节点
  • 删除给定指针指向的节点

• 容器实例：LinkedHashMap

• 设计思想：用空间换时间

双向循环链表

与数组的对比

• 数组优点是使用简单，随机访问性好；缺点是大小固定，如果声明过大，会导致空间的浪费，并可能没有足够的内存可以分配，如果声明过小，则需申请更大的内存，并拷贝原有的数据，操作耗时

• 链表缺点是随机访问性差；优点是天然支持扩容，对链表进行频繁的插入和删除操作时，会导致频繁的内存申请和释放，容易造成内存碎片，在java中则会导致GC频繁

链表代码技巧

• 理解指针或引用的含义

• 警惕指针丢失和内存泄露

• 在插入节点的时候，要注意操作的顺序

• 利用哨兵简化实现难度

  • 哨兵是解决边界问题的，不直接参与业务逻辑
  • 在任何时候，不管链表是不是为空，head始终指向这个哨兵节点，该链表称为带头链表；反之则是不带头链表
  • 在插入排序、归并排序、动态规划等都有体现哨兵思想

• 留意边界条件处理

  • 链表为空的情况
  • 链表只包含一个节点的情况
  • 链表只包含两个节点的情况
  • 处理头节点和尾节点的情况

• 举例画图，辅助思考

• 多写多练