链表，其中的各对象按线性顺序排列。
我们都知道数组的线性顺序是由数组的下标决定的，链表与数组不同的是，链表的线性顺序是由各个对象里的指针决定的。链表为动态集合提供了一种简单而灵活的表示方法。
上图所示，双向链表的每个元素都是一个对象，每个对象有一个key值和两个指针：perv和next。当然对象中还可以包含其他的辅助数据（卫星数据）。假设 x 为链表的一个元素，x.next指向它在链表中的后继元素，x.prev指向它的前驱元素。如果x.prev=nil，则元素没有前驱，表示是链表的第一个元素，也就是链表头。反之x.next=nil，则表示链表尾。
链表可以有很多中形式。可以是双向连接也可以是单向连接，可以是已排序的也可以是未排序的，可以是循环的也可以是不循环的。在单向链表中（singly linked），省略了每个元素中的prev指针。
如果链表是已排序（sorted）的，则链表的线性顺序和链表元素中关键字的线性顺序是一致的，所以最小的元素是表头，最大的元素是表尾。如果链表是未排序（unsorted），则各个元素可以以任何顺序出现。再循环链表中，表头元素的prev指针指向表尾，表尾元素的next指针指向表头。
-
链表的搜索
LIST-SEARCH(L,k)
x = L.head
while x != NIL && x.key != k
x = x.next
return x
采用简单的线性搜索方法，用于查找链表中第一个key值为k的元素，并返回该元素的指针。
该操作时间复杂度为 O(n) -
链表的插入
LIST-INSERT(L,x)
x.next = L.head
if L.head != NIL
L.head.next = x
L.head = x
x.prev = NIL
给定一个设置好关键字key的元素x，通过LIST-INSERT将元素x连接到链表的前端。
该操作的时间复杂度 O(1) -
链表的删除
LIST-DELETE(L,x)
if x.prev != NIL
x.prev.next = x.next
else L.head = x.next
if x.next != NIL
x.next.prev = x.prev
删除操作是通过修改一些指针，将 x "删除出"链表。要删除一个元素就必须先从链表中找到该元素，所以时间复杂度为 O(n）。
如果能够忽略表头表尾的边界条件，执行速度会快很多。
哨兵,（sentinel）是一个哑对象，起作用是简化边界条件的处理。假设在链表L中设置一个对象L.nil,该对象代表NIL，但是也具有和其他对象相同的各个属性。对于链表代码中出现的每一处的NIL都是对L.nil的引用。这样调整之后就将双向链表转换为了有哨兵的双向循环链表（circular,doubly linked with a sentinel）,哨兵L.nil位于表头和表尾之间。这样就能去掉属性L.head，并把对它的引用代替为对L.nil.next的引用，一个空的链表只有一个L.nil构成。
修改后链表的搜索
LIST-SEARCH(L,k)
x = L.nil.next
while x != L.nil && x.key != k
x = x.next
return x
基本保持不变，只是对NIL和L.head的引用更换成哨兵。
修改后链表的删除
LIST-DELETE(L,x)
x.prev.next = x.next
x.next.prev = x.prev
修改后链表的插入
LIST-INSERT(L,x)
x.next=L.nil.next
L.nil.next.prev=x
L.nil.next=x
x.prev=L.nil
注意：使用哨兵基本不能降低数据结构相关操作的渐进时间界，但是可以降低常数因子。在循环语句中使用哨兵的好处往往在于代码简洁，而非提高速度。举例来说，使用哨兵使链表的代码变得更加的简洁，但是在LIST-INSERT和LIST-DELETE过程中仅仅节约了O(1)的时间。然而在另一些情况下，哨兵的使用使循环语句的代码更紧凑，从而降低了运行时间中 n 或者 n2 等项的系数。