python 实现双向链表的基本操作带详细注解

#双向链表的实现
# coding = utf-8

# 定义节点类
class Node(object):
    def __init__(self,data):
        #定义数据域
        self.data = data
        #定义后指向
        self.next = None
        #定义前指向
        self.prev = None
 #定义双项链表类
class Double_List(object):
    def __init__(self):
        #定义链表头
        self._head = Node(None)
        #定义链表长度
        self._length = 0
    def is_empty(self):
        if self._length == 0:
            return True
        else:
            return False
        #循环遍历节点
    def trave(self):
        #定义游标
        cur = self._head
        for i in range(self._length):
            print(cur.next.data, end=" ")
            cur = cur.next
        else:
            print("")

    #尾部添加节点
    def append(self, data):
        #构造新的节点
        new_code = Node(data)
        #创建游标
        cur = self._head
        for i in range(self._length):
            #移动游标
            cur = cur.next
        else:
            #插入新节点
            #1.新节点有所指向
            new_code.prev = cur
            #2.让与新节点有关的节点有所指向
            cur.next = new_code
            #链表长度加1
            self._length +=1
    def insert(self, pos, data):
        #判断pos有效性
        if isinstance(pos, int):
            if pos < 0 :
                dl.insert(0, data)
            elif pos >self._length:
                dl.append(data)
            else:
                #创建新节点
                new_code = Node(data)
                #创建游标
                cur = self._head
                for i in range(self._length):
                    if i ==pos:
                        #插入新节点：
                        #1，让新的节点有所指向
                        new_code.prev = cur
                        new_code.next = cur.next
                        #2。让与新节点有关的节点有所指向
                        cur.next = new_code
                        new_code.next.prev = new_code

                        #链表长度更新
                        self._length += 1
                        return
                    else:
                        cur = cur.next
        else:
            print('pos数据无效')

    def remove(self, data):
        if self.is_empty():
            print("list is empty!")
        else:
            cur = self._head
            for i in range(self._length):
                if cur.next.data == data:
                    if cur.next.next is None:

                        #尾部节点删除
                        cur.next = None
                    else:
                        #删除中间节点
                        #1.让中间节前的节点的next指向中间节点的后节点
                        cur.next = cur.next.next
                        #2.让中间节点后的节点prev指向中间节点的前节点
                        cur.next.prev = cur
                        #更新链条长度
                        self._length -= 1
                        return
                else:
                    cur = cur.next
            else:
                print("{} is not in".format(data), end="")


if __name__ == "__main__":
    print("尾部插入", end=" ")
    dl = Double_List()
    for i in range(10):
        dl.append(i)
    dl.trave()


    print("任意位置插入：", end=" ")
    dl.insert(-10, "a")
    dl.insert(3,"d")
    dl.insert(10,"c")
    dl.trave()


    print("删除节点：", end=" ")
    dl.remove("d")
    dl.remove("c")
    dl.trave()