链表的形式

单链接或双链接，已排序或未排序，循环的或非循环的

双向链表

链表L中的每个元素都是一个对象，每个对象有一个关键字key和两个指针：next和prev，对象中还可以包含其他辅助数据（卫星数据）。若x是链表中的一个元素，则有： * x.next指向它在链表中的后继元素，x.prev指向它的前驱元素 * 若x.prev = None，则元素x是链表的第一个元素，即链表的头(head) * 若x.next = None, 则元素x是链表的最后一个元素，即链表的尾(tail) * L.head指向链表L的第一个元素，若L.head = None，则链表为空。

单向链表

链表L中的每个元素都是一个对象，每个对象有一个关键字key和一个指针：next，对象中还可以包含其他辅助数据（卫星数据）

已排序链表

链表的线性顺序与链表元素中关键字的线性顺序一致。因此，最小的元素就是表头元素，最大的元素是表尾元素。

注：对于未排序链表，这各元素可以以任何顺序出现

循环链表

链表L中的每个元素都是一个对象，每个对象有一个关键字key和两个指针：next和prev，对象中还可以包含其他辅助数据（卫星数据）。有： * 表头元素的prev指针指向表尾元素 * 表尾元素的next指针指向表头元素

链表的操作

注：以未排序且双链接链表为例

搜索

# 线性搜索，返回指向第一个关键字为k的元素的指针
# 若无关键字为k的对象，则返回None
# 最坏时间复杂度：O(n)，n为链表中元素个数
LIST_SEARCH(L, k)
    x = L.head
    while x != None and x.key != k
        x = x.next
    return x

插入

# x为已设置好关键字key的元素
# 将x插入到链表的前端
# 时间复杂度：O(1)
LIST_INSERT(L, x)
    x.next = L.head
    if L.head != None # 若L不为空链表，则将L原第一个元素指向x
        L.head.prev = x
    L.head = x
    x.prev = None

删除

# x是指向要删除元素
# 若要删除具有给定关键字值的元素，必须先调用LIST_SEARCH找到该元素
# 时间复杂度：O(1)
LIST_DELETE(L,x)
    if x.prev != None
        x.prev.next = x.next
    else L.head = x.next # x是第一个元素
    if x.next != None # 若x不是最后一个元素
        x.next.prev = x.prev

简化操作：哨兵哨兵L.nil是一个哑对象，表示None，其作用是简化边界条件的处理。将常规的双向链表转变为一个有哨兵的双向循环链表：

哨兵L.nil位于表头和表尾之间
属性L.nil.next指向表头，L.nil.prev指向表尾
表尾的next属性和表头的prev属性同时指向L.nil
把对L.head的引用代替为对L.nil.next的引用

一个空的链表只由一个哨兵构成，L.nil.next和L.nil.prev同时指向L.nil 带哨兵的双向循环链表

LIST_SEARCH_SENTINEL(L,k)
    x = L.nil.next
    while x != L.nil and x.key != k:
        x = x.next
    return x
LIST_INSERT_SENTINEL(L,x)
    x.next = L.nil.next
    L.nil.next.prev = x
    L.nil.next = x
    x.prev = L.nil
LIST_DELETE_SENTINEL(L,x)
    x.prev.next = x.next
    x.next.prev = x.prev

注意：仅当真正简化代码时才使用哨兵。

Python实现

结点对象：

class DNode(object):
    def __init__(self,value=0,prev=None,next=None):
        self.value = value
        self.next = next
        self.prev = prev

双向循环列表（无哨兵）

class DLink(object): # 双向循环列表（无哨兵）
    def __init__(self):
        self.head = None #表头初始为None
    def search(self,key):
        '''返回指向第一个关键字为key的元素的指针
           若无关键字为k的对象，则返回None
        '''
        x = self.head
        while x != None and x.value != key:
            x = x.next
        return x
    def insert(self,x):
        '''x为已设置好关键字key的元素
           将x插入到链表的前端
        '''
        x.next = self.head
        if self.head is not None: # 若不为空链
            self.head.prev = x
        self.head = x
        x.prev = None
    def delete(self,x):
        ''''删除元素'''
        if not isinstance(x,DNode): x = self.search(x)
        if x is None: return
        if x.prev != None: # x不是第一个结点
            x.prev.next = x.next
        else: self.head = x.next
        if x.next != None: # x不是最后一个结点
            x.next.prev = x.prev
    def show(self):
        '''打印链表'''
        x = self.head
        while x != None:
            print x.value
            x = x.next

双向循环链表(带哨兵)

class DLinkS(object): # 带哨兵的双向循环链表
    def __init__(self):
        self.nil = DNode() # 哨兵
        self.nil.next = self.nil # 一个空的链表只由一个哨兵构成，L.nil.next和L.nil.prev同时指向L.nil
        self.nil.prev = self.nil
    def search(self,key):
        x = self.nil.next
        while x != self.nil and x.value != key:
            x = x.next
        return x
    def insert(self,x):
        x.next = self.nil.next
        self.nil.next.prev = x
        self.nil.next = x
        x.prev = self.nil
    def delete(self,x):
        if not isinstance(x,DNode): x = self.search(x)
        if x is None: return
        x.prev.next = x.next
        x.next.prev = x.prev
    def show(self):
        x = self.nil.next
        while x != self.nil:
            print x.value
            x = x.next

# 单向链表实现的其他结构 ## 单向链表结点

class Node(object):
    def __init__(self,value,next=None):
        self.value = value
        self.next = next

## 单向链表

class Link(object):
    def __init__(self):
        self.head = None
    def search(self,key):
        x = self.head
        while x != None and x.value != key:
            x = x.next
        return x
    def insert(self,x): # 插入到链表头
        if self.head is not None:
            x.next = self.head
        self.head = x
    def delete(self,key):
        prev, x = None, self.head
        #查找第一个值为key的元素x，并保留x前的元素prev
        while x != None and x.value != key:
            prev = x
            x = x.next
        if x is None: return
        if prev: # x不是第一个元素
            prev.next = x.next
        else:
            self.head = x.next
    def show(self):
        x = self.head
        while x != None:
            print x.value
            x = x.next

## 栈

# 单链表实现栈
class UNDERFLOW(Exception):pass # 下溢
class StackL(object):
    def __init__(self):
        self.head = None
    #测试一个栈是否为空
    STACK_EMPTY = lambda self: self.head is None
    #插入元素到栈顶
    def PUSH(self,x):
        if self.head is not None:
            x.next = self.head          
        self.head = x
    #将栈顶元素返回并删除
    def POP(self):
        if self.STACK_EMPTY():
            raise UNDERFLOW("stack is empty")
        x = self.head
        self.head = x.next
        return x
    def show(self):
        x = self.head
        while x is not None:
            print x.value
            x = x.next

## 队列

class UNDERFLOW(Exception):pass # 下溢
class QueueL(object):
    def __init__(self):
        self.head = self.tail = None
    # 判断队列是否为空
    QUEUE_EMPTY = lambda self: self.head == None
    # 入队
    def ENQUEUE(self, x):
        if self.QUEUE_EMPTY(): #空队列，队头队尾都执行同一个元素
            self.head = self.tail = x
        else: #否则，队头保持不变，新元素放在队尾后
            self.tail.next = x
            self.tail = x
    # 出队
    def DEQUEUE(self):
        if self.QUEUE_EMPTY(): raise UNDERFLOW("the queue is empty")
        x = self.head
        self.head = x.next
        return x
    def show(self):
        x = self.head
        while x is not None:
            print x.value
            x = x.next

∞

链表及其Python的简单实现