双链表的每个节点有两个指针:一个指向后一个节点,另一个指向前一个节点。结构比单链表略复杂,但使用上更方便。

代码示例

class Node():
    def __init__(self, item, next=None, prior=None):
        self.item = item
        self.next = next
        self.prior = prior

# 插入操作
p.next = cur_node.next
cur_node.next.prior = p
p.prior = cur_node
cur_node.next = p

# 删除操作
p = cur_node.next
cur_node.next = p.next
p.next.prior = cur_node
del p

对比总结

1、链表在插入和删除的操作上明显快于顺序表;

2、链表的内存可以更灵活的分配;

3、如果用链表实现队列和栈结构,就不需要考虑大小的问题,可以更加灵活;

4、链表这种链式存储的数据机构,对数和图结构有很大的启发作用。

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/322