Python数据结构之链表

主要实现了链表的三个功能：链表的查找、插入与删除。

最近在看《算法导论》，看到第十章——基本数据结构中，提到了链表，于是用Python进行了实现。算法导论中只给出了三个操作：链表的查找、插入与删除。于是，暂时也只实现了这三个。

下面进行简要的介绍：

我们首先定义一个节点的类，用来存储链表中的每个节点。每个节点都有三个属性：节点存储的元素值，指向上一个节点的指针以及指向下一个节点的指针。

class Node:  # 链表的每个节点
    def __init__(self, value=None, _prev=None, _next=None):
        self.value = value
        self.prev = _prev
        self.next = _next

    def __str__(self):  # 在print时默认返回value
        return str(self.value)

其中，__str__函数使得在print一个Node对象的时候打印其value值。

接着我们定义链表类List。Python中list是一个关键字，表示序列，故避免重复，也可以把链表叫做LinkedList。

class List:
    def __init__(self):
        self.head = None  # init as a empty list

上述初始化函数中的self.head = None将链表初始化为空链表。

接着分别实现搜索、插入和删除三个功能。可以对照着书中的伪码

def search(self, key):
    x = self.head
    while x.next is not None and x.value != key:
        x = x.next
    return x

def insert(self, x):
    # 插入节点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):
    # x is in list and known (can use search to find)
    if x.prev is not None:
        x.prev.next = x.next
    else:
        self.head = x.next

    if x.next is not None:
        x.next.prev = x.prev

下面的这个show_value函数是为了依次打印链表的元素，不是必须的，可以跳过。__str__与Node中的类似，实现了可以直接打印一个List的对象。

def show_value(self):
    # 依次打印链表的值
    x = self.head
    print("The List Value is:", end=' ')
    while x is not None:
        print(x.value, end=' ')
        x = x.next
    print()
    return 'show_value'

def __str__(self):
    # 支持直接print一个List的对象
    return self.show_value() + " in List"

最后是主函数，对上述实现进行简单的测试。

if __name__ == "__main__":
    l = List()
    l.insert(Node(5))
    l.insert(Node(4))
    l.insert(Node(3))
    n = l.search(5)
    print("search value: ", n.value, n.prev, n.next,
          "\nhead: ", l.head.value, l.head.prev, l.head.next)
    l.delete(n)
    print("head: ", l.head.value, l.head.prev, l.head.next)
    l.insert(Node(6))  # always insert as head.
    l.insert(Node(7))
    l.insert(Node(8))
    l.show_value()

    n = l.search(7)
    print("search value:", n, n.prev, n.next,
          "\nhead:", l.head, l.head.prev, l.head.next)

    l.delete(l.search(6))
    print(l)

完整的代码放在Github上了，仅供参考。链接为：Introduction_to_Algorihtms/list_my.py