链表由节点组成
- 节点的属性：
- 关键字key
- 由节点对象代替的指针prev,next
单向节点只有next指针
- 链表由表头（一个节点对象）和指针构成
链表的形式
- 单链接或双链接：
单链接只有next指针，双链接指针齐全 - 循环或非循环：
L.head.prev = L.tail
L.tail.next = L.head - 已排序或未排序
链表相关操作
- 链表的搜索：
从n = L.head开始，遍历n.next,直到找到与给定参数相同的key或者n = null为止。 - 链表的插入：
- 如果链表为空，则直接将x作为表头：
L.head = x; - 将给定关键字的新节点x链接到表头
x.next = L.head;
L.head.prev = x;
L.head = x;
x.prev = null;
- 如果链表为空，则直接将x作为表头：
- 链表的删除：
- 如果当前节点为表头：
L.head = x.next;
x.next.prev = nil; - 如果当前节点为表尾：
x.prev.next = nil; - 当前节点前后都有节点：
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; - 对单一链表，增加哨兵会提高效率
- 对多个短链表，增加哨兵可能会浪费存储空间
