链表由节点组成

• 节点的属性：
  1. 关键字key
  2. 由节点对象代替的指针prev,next
     单向节点只有next指针
• 链表由表头（一个节点对象）和指针构成

链表的形式

• 单链接或双链接：
  单链接只有next指针，双链接指针齐全
• 循环或非循环：
  L.head.prev = L.tail
  L.tail.next = L.head
• 已排序或未排序

链表相关操作

• 链表的搜索：
  从n = L.head开始，遍历n.next,直到找到与给定参数相同的key或者n = null为止。
• 链表的插入：
  1. 如果链表为空，则直接将x作为表头：
     L.head = x;
  2. 将给定关键字的新节点x链接到表头
     x.next = L.head;
     L.head.prev = x;
     L.head = x;
     x.prev = null;
• 链表的删除：
  1. 如果当前节点为表头：
     L.head = x.next;
     x.next.prev = nil;
  2. 如果当前节点为表尾：
     x.prev.next = nil;
  3. 当前节点前后都有节点：
     x.prev.next = x.next;
     x.next.prev = x.prev;

有哨兵的双向链表

L.head.prev = L.nil;
L.tail.next = L.nil;
L.nil.next = L.head;
L.nil.prev = L.tail;

• 链表的搜索：
  从n = L.nil.next开始遍历整个链表，知道key等于给定参数或n = L.nil;
• 链表的插入：
  插入到L.nil和L.nil.next中间
• 链表的删除：
  x.prev.next = x.next;
  x.next.prev = x.prev;
• 对单一链表，增加哨兵会提高效率
• 对多个短链表，增加哨兵可能会浪费存储空间