特点：

  • 内存不连续
  • 随机访问复杂度：O(n)
  • 增删负载：O(1)

分类：

1.单向链表：

2.循环链表:

  • 尾节点指向头结点
  • 从链尾到链头比较方便，解决特殊问题

3.双向链表：

  • 每个节点一个后继指针指向后一个节点，也有一个前继指针指向前一个节点
  • 增删更加高效
  • 如果是有序链表，通过对比，可选择向前或者向后查找，更加高效

4.双向循环链表：

小知识点：

  • 对链表频繁的进行增删，容易造成内存随便，JVM会频繁的gc
  • 如果对性能要求非常的苛刻，就应避免使用容器，尽量使用数组

题目(练习题LeetCode对应编号:206，141，21，19，876):

  • 单链表反转
  • 链表中环的检测
  • 两个有序链表合并
  • 删除链表中倒数第n个节点
  • 求链表的中间节点

注意点：
  • 指针丢失
  • 哨兵节点
  • 处理边界条件