python实现双链表

和单链表类似，只不过是增加了一个指向前面一个元素的指针而已。

示意图：

2. 单链表代码实现

    def __init__(self,val,p=0):
        '''
        创建双链表的数据结构 数据节点--下一个节点--上一个节点
        :param val: 数据节点
        :param p:
        '''
        self.data = val
        self.next = p
        self.prev = p

class LinkDBList(object):
    def __init__(self):
        '''
        初始化 默认指向0
        '''
        self.head = 0

    def __getitem__(self, key):
        '''
        取到对应的值
        :param key:
        :return:
        '''
        if self.is_empty():
            print('linkList is empty')
        elif key < 0 or key > self.getLength():
            print("the given key is error")
        else:
            self.getItem(key)

    def __setitem__(self, key, value):
        '''
        根据传入的参数 设置对应的key-value
        :param key: 索引
        :param value: 对应的值
        :return:
        '''
        if self.is_empty():
            print('linkList is empty')
        elif key < 0 or key > self.getLength():
            print("the given key is error")
        else:
            self.delete(key)
            self.insert(key,value)

    def initlist(self,data):
        '''
        传输的数组 转换成双链表
        :param data: 待转换的数组
        :return: 双链表
        '''
        self.head = Node(data[0])
        p = self.head
        for i in data[1:]:
            node = Node(i)
            p.next = node
            node.prev = p
            p = p.next


    def getLength(self):
        p = self.head
        length = 0
        while p != 0:
            length += 1
            p = p.next
        return length

    def is_empty(self):
        if self.getLength() == 0:
            return True
        else:
            return False

    def clear(self):
        self.head = 0

    def append(self,value):
        '''
        将key-value 添加到链表的尾部
        :param key:
        :param value:
        :return:
        '''
        if self.is_empty():
            print("linkList is empty")
            return
        p = self.head
        while p.next != 0:
            p = p.next
        node = Node(value)
        p.next = node
        node.prev = p

    def getItem(self,key):
        '''
        根据提供的key索引 获取对应的值value
        :param key:
        :return:
        '''
        if self.is_empty():
            print("linkList is empty")
            return
        p = self.head
        length = 0
        while p.next != 0 and length < key:
            p = p.next
            length += 1
        if length == key:
            return p.data
        else:
            print("the data is not exist")


    def insert(self,key,value):
        '''
        根据提供的key,value 插入到对应的链表中
        :param key:
        :param value:
        :return:
        '''
        if self.is_empty():
            print("linkList is empty")
            return
        if key < 0 or key > self.getLength():
            print("the given key is error")
            return

        if key == 0:
            q = self.head
            node = Node(val=value,p=key)
            self.head = node
            node.next = q
            q.prev = node
            return
        p = self.head
        post = self.head
        length = 0
        while p.next != 0 and length < key:
            post = p
            p = p.next
            length += 1
        if key == length:
            node = Node(key,value)
            post.next = node
            node.prev = post
            node.next = p
            p.prev = node

    def delete(self,key):
        '''
        删除对应索引的节点
        :param key:
        :return:
        '''
        if self.is_empty():
            print("linkList is empty")
            return
        if key < 0 or key > self.getLength():
            print("the given key is error")
            return
        if key == 0:
            self.head = self.head.next
            return
        p = self.head
        post = self.head
        length = 0
        while p.next != 0 and length < key:
            post = p
            p = p.next
            length += 1
        if key == length:
            p = p.next
            post.next = p
            p.prev = post


    def index(self,value):
        '''
        根据value匹配链表中的index
        :param value:
        :return:
        '''
        if self.is_empty():
            print("linkList is empty")
            return
        p = self.head
        index = 0
        while p.next != 0 and not p.data == value:
            p = p.next
            index +=1
        if p.data == value:
            return index
        else:
            return -1

    def node(self,key):
        '''
        根据索引查找对应的节点
        :param key:
        :return:
        '''
        if self.is_empty():
            print("linkList is empty")
            return
        p = self.head
        index = 0
        while p.next != 0 and index < key:
            p = p.next
            index += 1
        if index == key:
            return p

    def allData(self):
        '''
        返回所有的链表data
        :return: 
        '''
        if self.is_empty():
            print("linkList is empty")
            return
        p = self.head
        index = 0
        datas = []
        while p.next != 0 and index < self.getLength():
            datas.append(p.data)
            p = p.next
            index += 1

        return datas