在前文提到的線性結(jié)構(gòu)中，存在中間插入數(shù)據(jù)不方便的現(xiàn)象，因此為了解決這個(gè)問題，提出了鏈?zhǔn)浇Y(jié)構(gòu)。鏈?zhǔn)浇Y(jié)構(gòu)分為單鏈?zhǔn)浇Y(jié)構(gòu)和雙鏈?zhǔn)浇Y(jié)構(gòu)。

單鏈?zhǔn)浇Y(jié)構(gòu)

雙鏈?zhǔn)浇Y(jié)構(gòu)

1. 什么是鏈?zhǔn)浇Y(jié)構(gòu)

鏈?zhǔn)浇Y(jié)構(gòu)是為了解決線性結(jié)構(gòu)中間插入數(shù)據(jù)速度不友好而提出的解決方法，對初始化的數(shù)據(jù)添加next屬性，使得它指向下一個(gè)節(jié)點(diǎn)，這樣需要添加數(shù)據(jù)或者刪除數(shù)據(jù)（完全刪除，非重置為None）只需要將鏈?zhǔn)浇Y(jié)構(gòu)打斷并重新連接即可實(shí)現(xiàn)。不過需要犧牲線性結(jié)構(gòu)的快速查詢性能。

• 單鏈?zhǔn)浇Y(jié)構(gòu)
  • 單鏈?zhǔn)浇Y(jié)構(gòu)解決了插入數(shù)據(jù)和完全刪除數(shù)據(jù)問題，查找數(shù)據(jù)則需要進(jìn)行遍歷查找。但是因?yàn)閱捂準(zhǔn)浇Y(jié)構(gòu)只有next一個(gè)屬性，因此無法逆序遍歷。
• 雙鏈?zhǔn)浇Y(jié)構(gòu)
  • 雙鏈?zhǔn)浇Y(jié)構(gòu)根據(jù)單鏈?zhǔn)浇Y(jié)構(gòu)無法逆序而添加新的屬性，prev屬性，指向它的上一個(gè)節(jié)點(diǎn)，實(shí)現(xiàn)了數(shù)據(jù)的逆序遍歷。

2. 鏈?zhǔn)浇Y(jié)構(gòu)的優(yōu)缺點(diǎn)

• 優(yōu)點(diǎn)
  • 鏈?zhǔn)浇Y(jié)構(gòu)可以快速插入數(shù)據(jù)
• 缺點(diǎn)
  • 查找某一個(gè)數(shù)據(jù)或者說顯示某一個(gè)數(shù)據(jù)需要進(jìn)行遍歷查找

3. 代碼

3.1 單鏈?zhǔn)浇Y(jié)構(gòu)

class Node():
    def __init__(self, value=None, next=None):
        self.value = value
        self.next = next
    
    # 用于顯示
    def __str__(self):
        return self.value


class LinkedList():
    def __init__(self):
        # 初始化root節(jié)點(diǎn)為空，不進(jìn)行展示
        self.root = Node()
        self.size = 0  # 記錄有多少元素
        self.next = None  # 增加新數(shù)據(jù)時(shí)，將新數(shù)據(jù)的地址與誰關(guān)聯(lián)

    def append(self, value):
        node = Node(value)
        # 判斷是否已經(jīng)有數(shù)據(jù)
        if not self.next:  # 如果沒有節(jié)點(diǎn)時(shí)
            self.root.next = node  # 將新節(jié)點(diǎn)掛到root后面
        else:
            self.next.next = node  # 將新節(jié)點(diǎn)掛到最后一個(gè)節(jié)點(diǎn)上
        # 同時(shí)要將添加的數(shù)據(jù)設(shè)置為最后一個(gè)節(jié)點(diǎn)
        self.next = node
        self.size += 1

    def append_first(self, value):
        node = Node(value)
        if not self.next:
            self.root.next = node
            self.next = node
        else:
            temp = self.root.next  # 獲取原來root后面的那個(gè)節(jié)點(diǎn)
            self.root.next = node  # 將新的節(jié)點(diǎn)掛到root上
            node.next = temp  # 新的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是原來的root后的節(jié)點(diǎn)
        self.size += 1

    def __iter__(self):
        current = self.root.next
        if current:
            while current is not self.next:
                yield current
                current = current.next
            yield current

    # 查找數(shù)據(jù)需要進(jìn)行遍歷整個(gè)鏈?zhǔn)奖?    def find(self, value):
        for data in self.__iter__():
            if data.value == value:
                return data

    def find_count(self, value):
        count = 0
        for data in self.__iter__():
            if data.value == value:
                count += 1
        return count

    def remove(self, value):
        prev = self.root
        for data in self.__iter__():
            # 判斷節(jié)點(diǎn)的值與要?jiǎng)h除的值是否相等
            if data.value == value:
                # 查看是不是最后一個(gè)節(jié)點(diǎn)
                if data == self.next:
                    # 更新倒數(shù)第二節(jié)點(diǎn)的關(guān)系
                    prev.next = None
                    # 更新最后一個(gè)節(jié)點(diǎn)為原倒數(shù)第二個(gè)節(jié)點(diǎn)
                    self.next = prev
                prev.next = data.next
                del data
                self.size -= 1
                return True
            prev = data

    def remove_all(self, value):
        prev = self.root
        for data in self.__iter__():
            if data.value == value:
                if data == self.next:
                    prev.next = None
                    self.next = prev
                prev.next = data.next
                del data
                self.size -= 1
                continue
            prev = data

3.2 雙鏈?zhǔn)浇Y(jié)構(gòu)

class Node():
    def __init__(self, value=None, prev=None, next=None):
        self.value = value
        self.prev = prev
        self.next = next

    def __str__(self):
        return self.value


class DoubleLinkedList():
    def __init__(self):
        self.root = Node()
        self.size = 0
        self.end = None

    def append(self, value):
        node = Node(value)  # 封裝節(jié)點(diǎn)對象
        # 判斷是否已經(jīng)有數(shù)據(jù)
        if not self.end:  # 如果沒有元素
            self.root.next = node  # 將root 的下一個(gè)節(jié)點(diǎn) 設(shè)置為新的node節(jié)點(diǎn)
            node.prev = self.root  # 設(shè)置新節(jié)點(diǎn)的 上一個(gè)節(jié)點(diǎn) 為 root
        else:
            self.end.next = node  # 將原來最后節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) 設(shè)置為新的node節(jié)點(diǎn)
            node.prev = self.end  # 設(shè)置新節(jié)點(diǎn)的 上一個(gè)節(jié)點(diǎn) 為 原來的最后一個(gè)節(jié)點(diǎn)
        self.end = node  # 更新最后 一個(gè)節(jié)點(diǎn)新加的node節(jié)點(diǎn)
        self.size += 1

    def append_first(self, value):
        node = Node(value)
        # 判斷是否已經(jīng)有數(shù)據(jù)
        if not self.end:  # 如果沒有元素
            self.end = node  # 更新最后 一個(gè)節(jié)點(diǎn)新加的node節(jié)點(diǎn)
        else:
            temp = self.root.next  # 保存原來的第一個(gè)節(jié)點(diǎn)
            node.next = temp  # 設(shè)置新節(jié)的下一個(gè)節(jié)為原來的 第一個(gè)節(jié)點(diǎn)
            temp.prev = node  # 更新原來的第一個(gè)節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)位置為 新的node節(jié)點(diǎn)
        node.prev = self.root  # 設(shè)置新節(jié)點(diǎn)的 上一個(gè)節(jié)點(diǎn) 為 root
        self.root.next = node  # 將root 的下一個(gè)節(jié)點(diǎn) 設(shè)置為新的node節(jié)點(diǎn)
        self.size += 1

    def __iter__(self):
        current = self.root.next
        if current:
            while current is not self.end:
                yield current
                current = current.next
            yield current

    def revers_iter(self):
        current = self.end  # 獲取最后一節(jié)點(diǎn)
        if current:
            while current is not self.root:
                yield current
                current = current.prev