python 双链表实现

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


class DoubleLink(object):
    def __init__(self, node=None):
        self.__head = node

    def length(self):
        count = 0
        cur_node = self.__head
        while cur_node != None:
            count += 1
            cur_node = cur_node.next
        return count

    def traverse(self):
        cur_node = self.__head
        while cur_node:
            print(cur_node.item, end=',')
            cur_node = cur_node.next
        print('')

    def append(self, ele):
        if ele is None:
            return None
        node = Node(ele)
        if self.__head == None:
            self.__head = node
            return node
        cur_node = self.__head
        while cur_node.next != None:
            cur_node = cur_node.next
        cur_node.next = node
        node.pre = cur_node
        return node

    def add(self, ele):
        node = Node(ele)
        if self.__head:
            node.next = self.__head
            self.__head.pre = node
            self.__head = node
            # self.__head.pre = None
        else:
            self.__head = node

    def insert(self, index, ele):
        count = 1
        cur = self.__head
        node = Node(ele)

        if index == 0:
            self.add(ele)
            return
        if index == 1:
            node.next = self.__head.next
            node.pre = self.__head
            self.__head.next = node
            self.__head.next.pre = node
            return

        if index < self.length():
            while True:
                cur = cur.next
                count += 1
                if count == index:
                    node.next = cur.next
                    node.pre = cur
                    cur.next = node
                    cur.next.pre = node
                    break
        else:
            self.append(ele)

    def delete(self, ele):

        cur = self.__head
        if cur.item == ele:
            self.__head = cur.next
            cur.pre = None

        while cur:
            if cur.next:
                if cur.next.item == ele:
                    cur.next = cur.next.next
                    if cur.next:
                        cur.next.pre = cur
                        break
                    else:
                        # 寻找最后一个值
                        last_node = self.__head
                        while last_node.next:
                            last_node = last_node.next
                        last_node.pre = cur

                        break

                cur = cur.next

            else:
                return


s = DoubleLink()
s.append('a')
s.append('b')
s.traverse()
s.add('c')
s.traverse()
s.insert(2, 'd')
s.append('e')
s.traverse()
s.delete('e')
s.traverse()
s.delete('d')
s.traverse()