python如何實現雙鏈表

本篇內容介紹了“python如何實現雙鏈表”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

實現雙鏈表需要注意的地方

1、如何插入元素，考慮特殊情況：頭節點位置，尾節點位置；一般情況：中間位置
2、如何刪除元素，考慮特殊情況：頭結點位置，尾節點位置；一般情況：中間位置

代碼實現

1.構造節點的類和鏈表類

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.previous = None


class DoubleLinkList:
    '''雙鏈表'''

    def __init__(self, node=None):
        self._head = node

以下方法均在鏈表類中實現

2. 判斷鏈表是否為空

def is_empty(self):
        return self._head is None

3. 輸出鏈表的長度

def length(self):
        count = 0
        if self.is_empty():
            return count
        else:
            current = self._head
            while current is not None:
                count += 1
                current = current.next
        return count

4. 遍歷鏈表

def travel(self):
        current = self._head
        while current is not None:
            print("{0}".format(current.data), end=" ")
            current = current.next
        print("")

5.頭插法增加新元素

def add(self, item):
        node = Node(item)

        # 如果鏈表為空，讓頭指針指向當前節點
        if self.is_empty():
            self._head = node

        # 注意插入的順序，
        else:
            node.next = self._head
            self._head.previous = node
            self._head = node

6. 尾插法增加新元素

def append(self, item):
        node = Node(item)

        # 如果鏈表為空，則直接讓頭指針指向該節點
        if self.is_empty():
            self._head = node

        # 需要找到尾節點，然后讓尾節點的與新的節點進行連接
        else:
            current = self._head
            while current.next is not None:
                current = current.next
            current.next = node
            node.previous = current

7. 查找元素是否存在鏈表中

def search(self, item):
        current = self._head
        found = False
        while current is not None and not found:
            if current.data == item:
                found = True
            else:
                current = current.next
        return found

8. 在某個位置中插入元素

def insert(self, item, pos):

        # 特殊位置，在第一個位置的時候，頭插法
        if pos <= 0:
            self.add(item)

        # 在尾部的時候，使用尾插法
        elif pos > self.length() - 1:
            self.append(item)

        # 中間位置
        else:
            node = Node(item)
            current = self._head
            count = 0
            while count < pos - 1:
                current = current.next
                count += 1

            # 找到了要插入位置的前驅之后，進行如下操作
            node.previous = current
            node.next = current.next
            current.next.previous = node
            current.next = node

 # 換一個順序也可以進行
def insert2(self, item, pos):
        if pos <= 0:
            self.add(item)
        elif pos > self.length() - 1:
            self.append(item)
        else:
            node = Node(item)
            current = self._head
            count = 0
            while count < pos:
                current = current.next
                count += 1

            node.next = current
            node.previous = current.previous
            current.previous.next = node
            current.previous = node

9. 刪除元素

def remove(self, item):
        current = self._head
        if self.is_empty():
            return
        elif current.data == item:
            # 第一個節點就是目標節點，那么需要將下一個節點的前驅改為None 然后再將head指向下一個節點
            current.next.previous = None
            self._head = current.next
        else:

            # 找到要刪除的元素節點
            while current is not None and current.data != item:
                current = current.next
            if current is None:
                print("not found {0}".format(item))

            # 如果尾節點是目標節點，讓前驅節點指向None
            elif current.next is None:
                current.previous.next = None

            # 中間位置，因為是雙鏈表，可以用前驅指針操作
            else:
                current.previous.next = current.next
                current.next.previous = current.previous

# 第二種寫法
    def remove2(self, item):
        """刪除元素"""
        if self.is_empty():
            return
        else:
            cur = self._head
            if cur.data == item:
                # 如果首節點的元素即是要刪除的元素
                if cur.next is None:
                    # 如果鏈表只有這一個節點
                    self._head = None
                else:
                    # 將第二個節點的prev設置為None
                    cur.next.prev = None
                    # 將_head指向第二個節點
                    self._head = cur.next
                return
            while cur is not None:
                if cur.data == item:
                    # 將cur的前一個節點的next指向cur的后一個節點
                    cur.prev.next = cur.next
                    # 將cur的后一個節點的prev指向cur的前一個節點
                    cur.next.prev = cur.prev
                    break
                cur = cur.next

10. 演示

my_list = DoubleLinkList()


print("add操作")
my_list.add(98)
my_list.add(99)
my_list.add(100)
my_list.travel()
print("{:#^50}".format(""))

print("append操作")
my_list.append(86)
my_list.append(85)
my_list.append(88)
my_list.travel()
print("{:#^50}".format(""))

print("insert2操作")
my_list.insert2(66, 3)
my_list.insert2(77, 0)
my_list.insert2(55, 10)
my_list.travel()
print("{:#^50}".format(""))


print("insert操作")
my_list.insert(90, 4)
my_list.insert(123, 5)
my_list.travel()
print("{:#^50}".format(""))

print("search操作")
print(my_list.search(100))
print(my_list.search(1998))
print("{:#^50}".format(""))

print("remove操作")
my_list.remove(56)
my_list.remove(123)
my_list.remove(77)
my_list.remove(55)
my_list.travel()
print("{:#^50}".format(""))

print("remove2操作")
my_list.travel()
my_list.remove2(100)
my_list.remove2(99)
my_list.remove2(98)
my_list.travel()

“python如何實現雙鏈表”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！