用python实现基本数据结构【03/4】

说明

        如果需要用到这些知识却没有掌握，则会让人感到沮丧，也可能导致面试被拒。无论是花几天时间“突击”，还是利用零碎的时间持续学习，在数据结构上下点功夫都是值得的。那么Python 中有哪些数据结构呢？列表、字典、集合，还有……栈？Python 有栈吗？本系列文章将给出详细拼图。
 

9章：Advanced Linked Lists

之前曾经介绍过单链表，一个链表节点只有data和next字段，本章介绍高级的链表。

Doubly Linked List，双链表，每个节点多了个prev指向前一个节点。双链表可以用来编写文本编辑器的buffer。

class DListNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None


def revTraversa(tail):
    curNode = tail
    while cruNode is not None:
        print(curNode.data)
        curNode = curNode.prev


def search_sorted_doubly_linked_list(head, tail, probe, target):
    """ probing technique探查法，改进直接遍历，不过最坏时间复杂度仍是O(n)
    searchin