# 定義一個鏈表節(jié)點
class Node():
	def __init__(self,data=None):
		self.val = data
		self.pre = None
		self.next = None
# 定義雙向鏈表		
class biLinkedList():
	def __init__(self):
		self.head = None
	# 獲取鏈表長度
	def length(self):
		curr = self.head
		count = 0
		while curr != None:
			count += 1
			curr = curr.next
		return count
	# 插入節(jié)點
	def insert(self,index,data):
		node = Node(data)
		# 在頭部插入
		if index <= 0:
			# 如果鏈表為空
			if self.head == None: 
				self.head = node
			else:
				node.next = self.head # 節(jié)點下一個指向head
				self.head.pre = node # head的上一個指向node
				self.head = node # head指向node
		# 在尾部插入
		elif index > self.length-1:
			if self.head == None: 
				self.head = node
			else:
				# 將指針移動到鏈表尾部
				curr = self.head
				while curr.next != None:
					curr = curr.next
				curr.next = node # 尾節(jié)點的下一個指向節(jié)點
				node.prev = curr # 節(jié)點的上一個指向尾節(jié)點
		# 在中間插入
		else:
			curr = self.head
			count = 0
			# 將指針移動到要插入位置的前一個位置
			while count < index-1:
				count += 1
				curr = curr.next
			node.pre = curr # 節(jié)點的上一個指向當(dāng)前
			node.next = curr.next # 節(jié)點的下一個指向當(dāng)前下一個
			curr.next.pre = node # 當(dāng)前的下一個的上一個指向節(jié)點
			curr.next = node # 當(dāng)前的下一個指向節(jié)點
# https://jackkuo666.github.io/Data_Structure_with_Python_book/chapter3/section3.html
# https://blog.csdn.net/qq490691606/article/details/49948263 (insert不能實現(xiàn)在尾部插入節(jié)點)

class Node:  # 鏈表的節(jié)點類
    def __init__(self, data, _prev=None, _next=None):
        self.prev = _prev #指針域 指向的是當(dāng)前節(jié)點的前一個節(jié)點
        self.data = data  # 數(shù)據(jù)域
        self.next = _next  # 指針域 指向的是當(dāng)前節(jié)點的下一個節(jié)點
class DoubleLinkList:
    def __init__(self):
        self.head = None  # 頭結(jié)點
        self._length = 0  # 長度
    def is_empty(self):
        #鏈表是否為空
        return self._length == 0
    def length(self):
        # 鏈表長度
        return self._length
    def nodes_list(self):
        # 返回鏈表中的所有節(jié)點的值組成的列表
        ls = []
        cur = self.head
        while cur != None:  # cur = None時找到尾結(jié)點
            ls.append(cur.data)
            cur = cur.next  # 鏈表不為空時繼續(xù)向后
        return ls  # 返回鏈表
    def add(self, data):
        # 向鏈表的頭部添加一個節(jié)點 data
        node = Node(data)  # 新建一個節(jié)點
        if self.is_empty():#鏈表為空
            self.head = node
        else:#鏈表不為空
            self.head.prev = node #1 讓鏈表中原本得頭結(jié)點prev指向新建節(jié)點
            # 如果鏈表為空時self.head = None 無法調(diào)用None.prev
            node.next = self.head  #  2讓node指向當(dāng)前鏈表中的頭結(jié)點
            self.head = node  # 3再讓鏈表的head指向當(dāng)前node節(jié)點
        self._length += 1  # 添加節(jié)點 鏈表長度+1
    def append(self, data):
        # 向鏈表的尾部添加一個節(jié)點， 值為data
        # 新建一個節(jié)點node, 值為data
        node = Node(data)
        if self.head != None:  # 鏈表不為空 有元素
            cur = self.head
            # 鏈表為空時，self.head 為None  無法執(zhí)行循環(huán)中的.next         while cur.next != None: #cur.next = None時找到尾結(jié)點
            # 找到鏈表的尾節(jié)點
            # 從頭結(jié)點開始，遍歷鏈表中所有的結(jié)點
            # 每次判斷當(dāng)前節(jié)點的next是否為空
            # 為空說明當(dāng)前節(jié)點就是尾結(jié)點
            # 不為空時，通過當(dāng)前節(jié)點得next去訪問下一個節(jié)點
            while cur.next != None:  # cur.next = None時找到尾結(jié)點cur
                cur = cur.next
            # 讓當(dāng)前的尾節(jié)點得指針域指向node
            node.prev = cur #讓node的prev指向原本的尾節(jié)點
            cur.next = node # 讓原本的尾節(jié)點的next去指向新建的節(jié)點
            # 添加完畢，鏈表的長度+1
        else:  # 空鏈表
            self.head = node
        self._length += 1
    def insert(self, pos, data):
        # 向指定位置添加節(jié)點，值為data
        # 異常情況 超出邊界
        if pos <= 0:
            self.add(data)
        elif pos >= self._length:
            self.append(data)
        else:
            node = Node(data)  # 1
            cur = self.head
            n = 0  # 2找鏈表中索引為pos-1的節(jié)點（0,1,2）， cur = cur.next 執(zhí)行pos-1步
            while n < pos - 1:
                cur = cur.next
                n = n + 1
            # 到這里cur指向的是索引為pos-1 的節(jié)點
            # 1新的節(jié)點node的prev指向索引為pos -1的節(jié)點
            node.prev = cur
            # 2鏈表中原本索引為pos的節(jié)點prev指向新的節(jié)點node
            cur.next.prev = node
            # 3新的節(jié)點node的next指向鏈表中原本索引為pos的節(jié)點
            node.next = cur.next  # cur.next 為pos的節(jié)點
            # 4讓索引為pos-1的節(jié)點得next指向node
            cur.next = node
            self._length += 1  # 5 長度+1
    def remove(self, data):
        # 刪除鏈表中第一個值為data的節(jié)點
        cur = self.head
        while cur:
            if cur.data == data:#找到要刪的節(jié)點
                # 如果前驅(qū)節(jié)點為空， 說明我們要刪除的節(jié)點是第一個節(jié)點
                if cur == self.head:#刪的是第一個結(jié)點
                    self.head = cur.next # 指向第二個節(jié)點
                    self.head.prev = None
                else:  # 要刪除的不是第一個節(jié)點
                    cur.prev.next = cur.next #要刪除節(jié)點的前一節(jié)點的next指向要刪除節(jié)點的后一個節(jié)點
                    #如要刪除的節(jié)點為最后一個節(jié)點，只需執(zhí)行這一步
                    if cur.next != None:#判斷cur.next是否存在
                        cur.next.prev = cur.prev #要刪除節(jié)點的下一節(jié)點的prev指向要刪除節(jié)點的前一個節(jié)點
                self._length -= 1
                return 0  # 找到
            cur = cur.next  # 繼續(xù)向后
        return -1  # 沒有找到
    def modify(self, pos, data):
        # 修改鏈表中指定位置的節(jié)點
        if pos < 0 or pos >= self._length:
            print("位置不正確")  # 位置不正確
        else:
            cur = self.head
            n = 0  # 找鏈表中索引為pos的節(jié)點（0,1,2）， cur = cur.next 執(zhí)行pos-1步
            while n < pos:
                cur = cur.next
                n = n + 1
            cur.data = data
    def search(self, data):
        # 查找鏈表中是否有節(jié)點的值為data
        cur = self.head
        while cur:
            if cur.data == data:
                return True  # 找到
            cur = cur.next  # 繼續(xù)向后
        return False  # 沒有找到
if __name__ == "__main__":
    l1 = DoubleLinkList()  # 新建一個鏈表類
    print(l1.nodes_list())
    l1.add(1)
    print(l1.nodes_list())
    l1.add(2)
    print(l1.nodes_list())
    l1.append(3)
    print(l1.nodes_list())
    l1.insert(1, 7)
    print(l1.nodes_list())
    l1.insert(5, 5)
    print("插入")
    print(l1.nodes_list())
    l1.remove(2)
    print(l1.nodes_list())
    l1.modify(0, 0)
    print(l1.nodes_list())
    print("查找")
    print(l1.search(5))