【Python資料結構系列】《線性表》——知識點講解+代碼實作

靈魂拷問：為什么要學資料結構？
資料結構，直白地理解，就是研究資料的存盤方式，資料存盤只有一個目的，即為了方便后期對資料的再利用，因此，資料在計算機存盤空間的存放，決不是胡亂的，這就要求我們選擇一種好的方式來存盤資料，而這也是資料結構的核心內容，
可以說，資料結構是一切編程的基本，學習資料結構是學習一種思想：如何把現實問題轉化為計算機語言的表示，
對于學計算機的朋友來說，學習資料結構是基本功，而對于非計算機專業，但是未來想往資料分析、大資料方向發展、或者在Python的使用上能有一個大的跨越的朋友來說，學習資料結構是一種非常重要的邏輯思維能力的鍛煉，在求職、職業發展、問題解決等方面都能有潛移默化的大幫助，

tips：本文介紹的知識只是作為一個引子，供小伙伴們參考學習，在學習程序中如果遇到問題，一定要多去搜索相關博客、文章、書籍等其他資料，作為補充學習，
廢話不多說，我們開整！

1.線性表（線性存盤結構）

線性表是資料結構中最簡單的資料存盤結構，可以理解為“線性的表”，線性，是說資料在邏輯結構上具有線性關系，將具有“一對一”關系的資料“線性”地存盤到物理空間中，這種存盤結構就稱為線性存盤結構（簡稱線性表），

1.1 線性表基本介紹

線性表，資料結構中最簡單的一種存盤結構，專門用于存盤邏輯關系為"一對一"的資料，基于資料在實際物理空間中的存盤狀態，又可細分為順序表（順序存盤結構）和鏈表（鏈式存盤結構），

線性表，全名為線性存盤結構，使用線性表存盤資料的方式可以這樣理解，即"把所有資料用一根線兒串起來，再存盤到物理空間中"，

如圖 1 所示，這是一組具有“一對一”關系的資料，我們接下來采用線性表將其儲存到物理空間中，

首先，用“一根線兒”把它們按照順序“串”起來，如圖 2 所示：

圖 2 中，左側是“串”起來的資料，右側是空閑的物理空間，把這“一串兒”資料放置到物理空間，我們可以選擇以下兩種方式，如圖 3 所示，

圖 3a) 是多數人想到的存盤方式，而圖 3b) 卻少有人想到，我們知道，資料存盤的成功與否，取決于是否能將資料完整地復原成它本來的樣子，如果把圖 3a) 和圖 3b) 線的一頭扯起，你會發現資料的位置依舊沒有發生改變（和圖 1 一樣），因此可以認定，這兩種存盤方式都是正確的，

將具有**“一對一”關系的資料“線性”地存盤到物理空間中**，這種存盤結構就稱為線性存盤結構（簡稱線性表），

使用線性表存盤的資料，如同向陣列中存盤資料那樣，要求資料型別必須一致，也就是說，線性表存盤的資料，要么全部都是整形，要么全部都是字串，一半是整形，另一半是字串的一組資料無法使用線性表存盤，

1.2 順序存盤結構和鏈式存盤結構

圖 3 中我們可以看出，線性表存盤資料可細分為以下 2 種：

（1） 如圖 3a) 所示，將資料依次存盤在連續的整塊物理空間中，這種存盤結構稱為順序存盤結構（簡稱順序表）；

（2）如圖 3b) 所示，資料分散的存盤在物理空間中，通過一根線保存著它們之間的邏輯關系，這種存盤結構稱為鏈式存盤結構（簡稱鏈表）；

也就是說，線性表存盤結構可細分為順序存盤結構和鏈式存盤結構，

1.3 前驅和后繼

資料結構中，一組資料中的每個個體被稱為“資料元素”（簡稱“元素”），例如，圖 1 顯示的這組資料，其中 1、2、3、4 和 5 都是這組資料中的一個元素，

另外，對于具有“一對一”邏輯關系的資料，我們一直在用“某一元素的左側（前邊）或右側（后邊）”這樣不專業的詞，其實線性表中有更準確的術語：

某一元素的左側相鄰元素稱為“直接前驅”，位于此元素左側的所有元素都統稱為“前驅元素”；

某一元素的右側相鄰元素稱為“直接后繼”，位于此元素右側的所有元素都統稱為“后繼元素”；

以圖 1 資料中的元素 3 來說，它的直接前驅是 2 ，此元素的前驅元素有 2 個，分別是 1 和 2；同理，此元素的直接后繼是 4 ，后繼元素也有 2 個，分別是 4 和 5，如下圖所示：

2. 順序表（順序存盤結構）

2.1 順序表基本介紹

順序表，全名順序存盤結構，是線性表的一種，通過《什么是線性表》一節的學習我們知道，線性表用于存盤邏輯關系為“一對一”的資料，順序表自然也不例外，

不僅如此，順序表對資料的物理存盤結構也有要求，順序表存盤資料時，會提前申請一整塊足夠大小的物理空間，然后將資料依次存盤起來，存盤時做到資料元素之間不留一絲縫隙，

例如，使用順序表存盤集合 {1,2,3,4,5}，資料最終的存盤狀態如圖1所示：

由此我們可以得出，將“具有 ‘一對一’ 邏輯關系的資料按照次序連續存盤到一整塊物理空間上”的存盤結構就是順序存盤結構，

通過觀察圖 1 中資料的存盤狀態，我們可以發現，順序表存盤資料同陣列非常接近，其實，順序表存盤資料使用的就是陣列，

2.2 順序表基本操作之插入元素

向已有順序表中插入資料元素，根據插入位置的不同，可分為以下 3 種情況：
　　① 插入到順序表的表頭；
　　② 在表的中間位置插入元素；
　　③ 尾隨順序表中已有元素，作為順序表中的最后一個元素；

雖然資料元素插入順序表中的位置有所不同，但是都使用的是同一種方式去解決，即：通過遍歷，找到資料元素要插入的位置，然后做如下兩步作業：
　　① 將要插入位置元素以及后續的元素整體向后移動一個位置；
　　② 將元素放到騰出來的位置上；

例如，在 {1,2,3,4,5} 的第 3 個位置上插入元素 6，實作程序如下：

① 遍歷至順序表存盤第 3 個資料元素的位置，如圖 1 所示：

② 將元素 3 以及后續元素 4 和 5 整體向后移動一個位置，如圖 2 所示：

③ 將新元素 6 放入騰出的位置，如圖 3 所示：

2.3 順序表基本操作之洗掉元素

從順序表中洗掉指定元素，實作起來非常簡單，只需找到目標元素，并將其后續所有元素整體前移 1 個位置即可，

【注】：后續元素整體前移一個位置，會直接將目標元素洗掉，可間接實作洗掉元素的目的，

例如，從 {1,2,3,4,5} 中洗掉元素 3 的程序如圖 4 所示：

2.4 順序表基本操作之查找元素

順序表中查找目標元素，可以使用多種查找演算法實作，比如說二分查找演算法、插值查找演算法等，

2.5 順序表基本操作之更改元素

順序表更改元素的實作程序是：
　　（1）找到目標元素；
　　（2）直接修改該元素的值；
　　
關于順序表Python編程實作代碼可參考↓（個人撰寫，僅供參考，歡迎提出寶貴建議）

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/20 15:42 
# @Author : vaxtiandao
# @File : ds_1.py

import random
random.seed(10)

# 定義順序表的類
class SqList():
    # 初始化
    def __init__(self, length):
        self.length = length  # 先指定陣列的長度
        self.sqlist = [random.randint(1, 100) for j in range(length)]  # 生成length長度的隨機陣列

    # 輸出所有元素
    def ShowList(self):
        return self.sqlist

    # 遍歷所有元素
    def ErgodicList(self):
        for i in range(self.length):
            print("第{}個元素值為{}".format(i+1, self.sqlist[i]))

    # 取值
    def GetElem(self, i):
        # 首先判斷插入的位置是否在合法范圍內(1,length)
        if i < 1 or i > self.length:
            pass
            return False
        return self.sqlist[i-1]  # 在的話，直接回傳值

    # 查找
    def LocateElem(self, e):
        # 通過回圈遍歷串列，找到串列中等于e的元素，回傳其位置索引
        for j in range(self.length):
            if e == self.sqlist[j]:
                return j
                break
        # 否則，輸出一句話:"串列中不存在查找的元素"，然后回傳False
        print("串列中不存在查找的元素")

    # 插入
    def ListInsert(self, i, e):
        # 首先判斷插入的位置是否在合法范圍內(1,length)，不在的話，直接回傳False
        if i < 1 or i > self.length:
            return False
        return self.sqlist.insert(i,e)  # 串列中有insert()函式

    # 洗掉
    def ListDelete(self, i):
        # 首先判斷插入的位置是否在合法范圍內(1,length)，不在的話，直接回傳False
        if i < 1 or i > self.length:
            return False
        return self.sqlist.pop(i)  # 串列有個pop()函式，該函式會回傳洗掉的值

# 定義一個順序表物件
length = 10
my_sqlist = SqList(length)
print("初始化的順序表：", my_sqlist)
print("_________________________________________________")
# 輸出所有引數
mylist = my_sqlist.ShowList()
print("輸出所有引數：", mylist)
print("_________________________________________________")
# 呼叫遍歷函式
print("遍歷順序表")
my_sqlist.ErgodicList()
print("_________________________________________________")
# 插入
print("插入前的串列：{}".format(my_sqlist.ShowList()))
i = 4 # 插入的索引位置
e = 10 # 插入的值
my_sqlist.ListInsert(i, e)  # 在指定索引位置插入值
print("插入后的順序表：{}".format(my_sqlist.ShowList()))
print("_________________________________________________")
# 洗掉
i = 5 # 洗掉的索引位置
print("洗掉前的順序表：{}".format(my_sqlist.ShowList()))
my_sqlist.ListDelete(i)  # 洗掉i索引所在位置上的值
print("洗掉后的順序表：{}".format(my_sqlist.ShowList()))
print("_________________________________________________")
# 取值
index = 8  # 這里代表的是第10個數，不是位置索引為10的數，索引+1才是具體第幾個數;
value = my_sqlist.GetElem(index)
if value:
    print("順序表中第{}個數等于{}".format(index, value))
print("_________________________________________________")
# 查找
e = 55  # 要查找的數
index = my_sqlist.LocateElem(e)
if index:
    print("元素{}在順序表中的索引為{}".format(e, index))

如下是實作效果：

關于順序表基本操作的C語言代碼，可以看這：順序表的基本操作

3. 單鏈表，鏈式存盤結構

3.1 單鏈表基本介紹

前面詳細地介紹了順序表，本節給大家介紹另外一種線性存盤結構——鏈表，

鏈表，別名鏈式存盤結構或單鏈表，用于存盤邏輯關系為 “一對一” 的資料，與順序表不同，鏈表不限制資料的物理存盤狀態，換句話說，使用鏈表存盤的資料元素，其物理存盤位置是隨機的，

例如，使用鏈表存盤 {1,2,3}，資料的物理存盤狀態如圖1所示：

我們看到，上圖根本無法體現出各資料之間的邏輯關系，對此，鏈表的解決方案是，每個資料元素在存盤時都配備一個指標，用于指向自己的直接后繼元素，如圖2所示：

像圖2這樣，資料元素隨機存盤，并通過指標表示資料之間邏輯關系的存盤結構就是鏈式存盤結構，

3.2 鏈表的節點

從上圖可以看到，鏈表中每個資料的存盤都由以下兩部分組成：
　　（1）資料元素本身，其所在的區域稱為資料域；
　　（2） 指向直接后繼元素的指標，所在的區域稱為指標域；

即鏈表中存盤各資料元素的結構如圖3所示：

上圖所示的結構在鏈表中稱為節點，也就是說，鏈表實際存盤的是一個一個的節點，真正的資料元素包含在這些節點中，如圖4所示：

3.3 頭節點，頭指標和首元節點

其實，圖 4 所示的鏈表結構并不完整，一個完整的鏈表需要由以下幾部分構成：

1. 頭指標：一個普通的指標，它的特點是永遠指向鏈表第一個節點的位置，很明顯，頭指標用于指明鏈表的位置，便于后期找到鏈表并使用表中的資料；

2. 節點：鏈表中的節點又細分為頭節點、首元節點和其他節點：
　　（1）頭節點：其實就是一個不存任何資料的空節點，通常作為鏈表的第一個節點，對于鏈表來說，頭節點不是必須的，它的作用只是為了方便解決某些實際問題；
　　（2）首元節點：由于頭節點（也就是空節點）的緣故，鏈表中稱第一個存有資料的節點為首元節點，首元節點只是對鏈表中第一個存有資料節點的一個稱謂，沒有實際意義；
　　（3）其他節點：鏈表中其他的節點；

因此，一個存盤 {1,2,3} 的完整鏈表結構如圖5所示：

【注】：鏈表中有頭節點時，頭指標指向頭節點；反之，若鏈表中沒有頭節點，則頭指標指向首元節點，

明白了鏈表的基本結構，下面我們來學習如何創建一個鏈表，

3.4 鏈表的創建（初始化）

創建一個鏈表需要做如下作業：

1. 宣告一個頭指標（如果有必要，可以宣告一個頭節點）；

2. 創建多個存盤資料的節點，在創建的程序中，要隨時與其前驅節點建立邏輯關系；

3.5 單鏈表基本操作

本節將詳細介紹對鏈表的一些基本操作，包括對鏈表中資料的添加、洗掉、查找（遍歷）和更改，

插入元素

同順序表一樣，向鏈表中增添元素，根據添加位置不同，可分為以下 3 種情況：
　　（1）插入到鏈表的頭部（頭節點之后），作為首元節點；
　　（2）插入到鏈表中間的某個位置；
　　（3）插入到鏈表的最末端，作為鏈表中最后一個資料元素；

雖然新元素的插入位置不固定，但是鏈表插入元素的思想是固定的，只需做以下兩步操作，即可將新元素插入到指定的位置：
　　（1）將新結點的 next 指標指向插入位置后的結點；
　　（2）將插入位置前結點的 next 指標指向插入結點；

例如，我們在鏈表 {1,2,3,4} 的基礎上分別實作在頭部、中間部位、尾部插入新元素 5，其實作程序如圖 1 所示：

從圖中可以看出，雖然新元素的插入位置不同，但實作插入操作的方法是一致的，都是先執行步驟 1 ，再執行步驟 2，

【注意】：鏈表插入元素的操作必須是先步驟 1，再步驟 2；反之，若先執行驟步 2，除非再添加一個指標，作為插入位置后續鏈表的頭指標，否則會導致插入位置后的這部分鏈表丟失，無法再實作步驟 1

洗掉元素

從鏈表中洗掉指定資料元素時，實則就是將存有該資料元素的節點從鏈表中摘除，但作為一名合格的程式員，要對存盤空間負責，對不再利用的存盤空間要及時釋放，因此，從鏈表中洗掉資料元素需要進行以下 2 步操作：
　　（1）將結點從鏈表中摘下來;
　　（2）手動釋放掉結點，回收被結點占用的存盤空間;

其中，從鏈表上摘除某節點的實作非常簡單，只需找到該節點的直接前驅節點 temp，例如，從存有 {1,2,3,4} 的鏈表中洗掉元素 3，則此代碼的執行效果如圖 2 所示：

查找元素

在鏈表中查找指定資料元素，最常用的方法是：從表頭依次遍歷表中節點，用被查找元素與各節點資料域中存盤的資料元素進行比對，直至比對成功或遍歷至鏈表最末端的 NULL（比對失敗的標志），

注意，遍歷有頭節點的鏈表時，需避免頭節點對測驗資料的影響，因此在遍歷鏈表時，建立使用上面代碼中的遍歷方法，直接越過頭節點對鏈表進行有效遍歷，

更新元素

更新鏈表中的元素，只需通過遍歷找到存盤此元素的節點，對節點中的資料域做更改操作即可，
　　
關于鏈表Python編程實作代碼可參考↓（個人撰寫，僅供參考，歡迎提出寶貴建議）

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/21 17:12
# @Author : vaxtiandao
# @File : ds_12.py
# 單向鏈表的實作
# 每個節點包含兩部分,資料區和指向下個節點的鏈接
# 單向串列:每個節點包含兩部分:資料區與鏈接區(指向下一個節點),最后一個元素的鏈接區為None
# 單向串列只要找到頭節點,就可以訪問全部節點

# 定義結點類，包含兩個成員：結點元素值和指向下一結點的指標
class SingleNode():
    # 結點類初始化
    def __init__(self, item):
        self.item = item  # item存放結點的數值
        self.next = None  # 下一指標指向


# 定義單鏈表
class SingleLinkList():
    # 鏈表類初始化
    def __init__(self):
        self.head = None

    # 判斷鏈表是否為空
    def is_empty(self):
        return self.head == None

    # 輸出鏈表長度
    def get_length(self):
        return len(self.travel())

    # 遍歷整個鏈表
    def travel(self):
        # 思路就是先判斷鏈表是否為空
        # 為空直接回傳None，
        # 不為空的話，就先定義一個串列，然后通過next指標從頭指標開始遍歷，依次將結點存盤的值加入串列中，直到下一指標指向為空，則停止遍歷；
        if self.is_empty():
            return None
        else:
            curlist = []
            cur = self.head
            while cur != None:
                curlist.append(cur.item)
                cur = cur.next
            return curlist

    # 頭插法創建單鏈表
    def add(self, newItem):
        node = SingleNode(newItem)
        node.next = self.head  # 指標變換
        self.head = node

    # 尾插法
    def append(self, newItem):
        node = SingleNode(newItem)
        if self.is_empty():
            return self.add(newItem)
        # 從頭結點開始遍歷
        nod = self.head
        while nod.next != None:  # 當下一個結點的next為None時，停止遍歷//  注：跟網上不一樣，回頭用尾插法新建單鏈表試試
            nod = nod.next
        nod.next = node

    # 指定位置添加元素
    def insert(self, pos, newItem):  # 在指定pos位置上添加newItem元素
        # 鏈表的插入需要分幾種情況
        # 第一步 判斷pos是否在合理范圍內，如果不在，則直接終止
        # 第二步 判斷pos是否在第一個，如果是則采用頭插法
        # 第三步 如果pos在最后一個，則采用尾插法
        # 第四步 如果既不在頭，也不再尾，則通過回圈遍歷到pos位置，再用Insert插入
        node = SingleNode(newItem)
        cur = self.head
        count = 0
        if pos == 0:
            return self.add(newItem)
        elif pos < (self.get_length()):
            while count < pos - 1:
                cur = cur.next
                count += 1
            node.next = cur.next
            cur.next = node
        elif pos == (self.get_length()):
            return self.append(newItem)
        else:
            return '輸入的位置有誤，請確認'

    # 洗掉指定位置上的結點
    def remove(self, pos):
        # 第一步 判斷給定的pos是否再合理范圍內
        # 第二步 通過回圈，遍歷到pos位置，遍歷期間通過next指標依次指向下一結點
        # 第三步 找到指定位置的結點后，通過nod.next = nod.next.next洗掉
        cur = self.head
        count = 0
        if 1 <= pos < (self.get_length()):
            while count < pos - 1:
                cur = cur.next
                count += 1
            cur.next = cur.next.next
        elif pos == 0:
            self.head = cur.next
        else:
            return '輸入的位置有誤，請確認'

    # 查找指定位置的結點值
    def find(self, pos):
        cur = self.head
        count = 0
        if 0 <= pos < (self.get_length()):
            while count < pos:
                cur = cur.next
                count += 1
            return cur.item
        else:
            return '輸入的位置有誤，請確認'

    # 更新鏈表中某個位置的值
    def update(self, pos, newItem):
        cur = self.head
        count = 0
        if 0 <= pos < (self.get_length()):
            while count < pos:
                cur = cur.next
                count += 1
            cur.item = newItem
        else:
            return '輸入的位置有誤，請確認'

    ## 清空鏈表
    def clear(self):
        self.head = None


singlelinklist = SingleLinkList() # 實體化物件
print("初始化單鏈表：",singlelinklist)
print("________________________________________________________________________________________________")
print("判斷單鏈表是否為空：",singlelinklist.is_empty())
print("________________________________________________________________________________________________")
# 添加資料
import random
for i in range(10):
    singlelinklist.add(random.randint(1,100))
# 遍歷資料
singlelinklist.travel()
print("遍歷單鏈表：",singlelinklist.travel())
print("________________________________________________________________________________________________")
print("判斷單鏈表是否為空：",singlelinklist.is_empty())
print("________________________________________________________________________________________________")
# 末尾添加資料
singlelinklist.append(10)
print("末尾添加元素后的單鏈表遍歷結果：", singlelinklist.travel())
print("________________________________________________________________________________________________")
# 開頭添加資料
singlelinklist.add(1)
print("開頭添加元素后的單鏈表遍歷結果：", singlelinklist.travel())
print("________________________________________________________________________________________________")
# 查看資料長度
print("單鏈表長度：",singlelinklist.get_length())
print("________________________________________________________________________________________________")
# 指定位置插入資料，位置從0開始
singlelinklist.insert(1, 13)
print("插入資料后的遍歷單鏈表：", singlelinklist.travel())
print("________________________________________________________________________________________________")
# 洗掉指定位置資料
singlelinklist.remove(0)
print("洗掉資料后的遍歷單鏈表：", singlelinklist.travel())
print("________________________________________________________________________________________________")
# 更新指定位置資料
singlelinklist.update(2,2)
print("更新資料后的遍歷單鏈表：", singlelinklist.travel())
print("________________________________________________________________________________________________")
# 清空所有資料
singlelinklist.clear()
print("清空資料后的遍歷單鏈表：", singlelinklist.travel())
print("________________________________________________________________________________________________")

如下是代碼實作效果：

關于單鏈表基本操作詳細的C語言代碼，見這👉：單鏈表的基本操作

4. 單向回圈鏈表

對于單鏈表以及雙向鏈表，其就像一個小巷，無論怎么樣最終都能從一端走到另一端，然而回圈鏈表則像一個有傳送門的小巷，因為回圈鏈表當你以為你走到結尾的時候，其實你又回到了開頭，

回圈鏈表和非回圈鏈表其實創建的程序以及思路幾乎完全一樣，唯一不同的是，非回圈鏈表的尾結點指向空（NULL），而回圈鏈表的尾指標指向的是鏈表的開頭，通過將單鏈表的尾結點指向頭結點的鏈表稱之為回圈單鏈表（Circular linkedlist）

如圖，為一個完整的回圈單鏈表；

4.1 回圈鏈表結點設計（以單回圈鏈表為例）

對于回圈單鏈表的結點，可以完全參照于單鏈表的結點設計，如圖：

data表示資料，其可以是簡單的型別（如int,double等等），也可以是復雜的結構體（struct型別）；

next表示指標，它永遠指向自身的下一個結點，對于只有一個結點的存在，這個next指標則永遠指向自身，對于一個鏈表的尾部結點，next永遠指向開頭，

4.2 回圈單鏈表初始化

如同單鏈表的創建，我們需要先創建一個頭結點并且給其開辟記憶體空間，但與單鏈表不同的是，我們需要在開辟記憶體空間成功之后將頭結點的next指向head自身，我們可以創建一個init函式來完成這件事情，為了以后的重復創建和插入，我們可以考慮在init重創建的結點next指向空，而在主函式呼叫創建之后手動講head頭結點的next指標指向自身，

這樣的操作方式可以方便過后的創建單鏈表，直接利用多次呼叫的插入函式即可完成整體創建，

4.3 回圈單鏈表的基本操作

回圈單鏈表基本操作包括：初始化、判空、遍歷、創建(頭插/尾插)、輸出長度、添加、洗掉、查找、更新以及清空；
　　
關于鏈表Python編程實作代碼可參考↓（個人撰寫，僅供參考，歡迎提出寶貴建議）

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/21 17:16 
# @Author : vaxtiandao
# @File : ds_13.py

# 定義結點類，包含兩個成員：結點元素值和指向下一結點的指標
class SingleNode():
    # 結點類初始化
    def __init__(self, item):
        self.item = item  # 存放結點的數值
        self.next = None  # 下一指標指向


# 定義單鏈表
class SingleLinkList():
    # 鏈表類初始化
    def __init__(self, node=None):
        self.head = node  # 指向頭結點
        if node:
            node.next = node  # 如果實體化物件時輸入了結點，定義結點回圈

    # 判斷鏈表是否為空
    def is_empty(self):
        return self.head == None

    # 輸出鏈表長度
    def get_length(self):
        if self.is_empty():
            return 0
        cur = self.head
        count = 1
        while cur.next != self.head:
            count += 1
            cur = cur.next
        return count

    # 遍歷整個鏈表
    def travel(self):
        curlist = []
        if self.is_empty():
            return curlist
        cur = self.head
        while cur.next != self.head:
            curlist.append(cur.item)
            cur = cur.next
        curlist.append(cur.item)
        return curlist

    # 頭插法創建單鏈表
    def add(self, newItem):
        node = SingleNode(newItem)
        cur = self.head
        if self.head is None:
            self.head = node
            node.next = node
        else:
            while cur.next != self.head:
                cur = cur.next
            node.next = self.head
            self.head = node
            cur.next = node

    # 尾插法創建單鏈表
    def append(self, newItem):
        node = SingleNode(newItem)
        # 從尾結點開始遍歷
        cur = self.head
        if self.is_empty():
            self.head = node
            node.next = node
        else:
            while cur.next != self.head:
                cur = cur.next
            node.next = self.head
            cur.next = node

    # 指定位置添加元素,pos從零開始
    def insert(self, pos, newItem):
        node = SingleNode(newItem)
        if pos <= 0:
            self.add(newItem)
        elif pos > (self.get_length() - 1):
            self.append(newItem)
        else:
            count = 0
            cur = self.head
            while count < (pos - 1):
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    # 洗掉指定位置上的結點
    def remove(self, pos):
        if pos <= 0:
            return '資料為空'
        elif pos > (self.get_length() - 1):
            return '超過鏈表范圍'
        else:
            count = 0
            cur = self.head
            while count < (pos - 1):
                count += 1
                cur = cur.next
            cur.next = cur.next.next

    # 查找指定位置的結點值
    def find(self, pos):
        if pos <= 0:
            return '資料為空'
        elif pos > (self.get_length() - 1):
            return '超過鏈表范圍'
        else:
            count = 0
            cur = self.head
            while count < pos:
                count += 1
                cur = cur.next
            return cur.item

    # 更新鏈表中的某個位置的值
    def update(self, pos, newItem):
        if pos <= 0:
            return '資料為空'
        elif pos > (self.get_length() - 1):
            return '超過鏈表范圍'
        else:
            count = 0
            cur = self.head
            while count < pos:
                count += 1
                cur = cur.next
            cur.item = newItem

    # 清空鏈表
    def clear(self):
        self.head = None


# 實體化物件
import random

singlelinklist = SingleLinkList()
print("初始化物件：", singlelinklist)
print("________________________________________________________________________________________________")
# 查看鏈表是否為空
print("初始化后，判斷當前鏈表是否為空：", singlelinklist.is_empty())
print("________________________________________________________________________________________________")
# 隨機添加資料
for i in range(10):
    singlelinklist.add(random.randint(1, 100))
# 查看鏈表是否為空
print("判斷當前鏈表是否為空：", singlelinklist.is_empty())
print("________________________________________________________________________________________________")
# 查看鏈表資料
print("遍歷鏈表查看鏈表元素：", singlelinklist.travel())
print("________________________________________________________________________________________________")
# 查詢鏈表的長度
print("當前鏈表長度為", singlelinklist.get_length())
print("________________________________________________________________________________________________")
# 頭插法
print("頭插前，遍歷鏈表查看鏈表元素：", singlelinklist.travel())
singlelinklist.add(0)
print("頭插后，遍歷鏈表查看鏈表元素：", singlelinklist.travel())
print("________________________________________________________________________________________________")
# 尾插法
print("尾插前，遍歷鏈表查看鏈表元素：", singlelinklist.travel())
singlelinklist.append(100)
print("尾插后，遍歷鏈表查看鏈表元素：", singlelinklist.travel())
print("________________________________________________________________________________________________")
# 指定位置插入值
print("指定位置插入前，遍歷鏈表查看鏈表元素：", singlelinklist.travel())
singlelinklist.insert(3, 3)
print("指定位置插入后，遍歷鏈表查看鏈表元素：", singlelinklist.travel())
print("________________________________________________________________________________________________")
# 查找指定位置的結點值
print("查找指定位置的結點值：", singlelinklist.find(5))
print("________________________________________________________________________________________________")
# 洗掉指定位置的值
print("洗掉前，遍歷鏈表查看鏈表元素：", singlelinklist.travel())
singlelinklist.remove(6)
print("洗掉后，遍歷鏈表查看鏈表元素：", singlelinklist.travel())
print("________________________________________________________________________________________________")
# 更新指定位置的值
print("更新前，遍歷鏈表查看鏈表元素：", singlelinklist.travel())
singlelinklist.update(3, 15)
print("更新后，遍歷鏈表查看鏈表元素：", singlelinklist.travel())
print("________________________________________________________________________________________________")
# 清空結點
print("清空前，遍歷鏈表查看鏈表元素：", singlelinklist.travel())
singlelinklist.clear()
print("清空后，遍歷鏈表查看鏈表元素：", singlelinklist.travel())
print("________________________________________________________________________________________________")

以下是上述代碼實作效果：

關于回圈單鏈表基本操作，見這👉：回圈單鏈表的基本操作

5. 雙向鏈表

5.1 雙向鏈表基本介紹

目前我們所學到的鏈表，無論是動態鏈表還是靜態鏈表，表中各節點中都只包含一個指標（游標），且都統一指向直接后繼節點，通常稱這類鏈表為單向鏈表（或單鏈表），

雖然使用單鏈表能100%解決邏輯關系為 “一對一” 資料的存盤問題，但在解決某些特殊問題時，單鏈表并不是效率最優的存盤結構，比如說，某場景中需要大量地查找某結點的前趨結點，這種情況下使用單鏈表無疑是災難性的，因為單鏈表更適合 “從前往后” 找，“從后往前” 找并不是它的強項，

對于逆向查找（從后往前）相關的問題，使用本節講解的雙向鏈表，會更加事半功倍，

雙向鏈表，簡稱雙鏈表，從名字上理解雙向鏈表，即鏈表是 “雙向” 的，如圖1所示：

所謂雙向，指的是各節點之間的邏輯關系是雙向的，但通常頭指標只設定一個，除非實際情況需要，可以為最后一個節點再設定一個“頭指標”，

根據圖 1 不難看出，雙向鏈表中各節點包含以下 3 部分資訊（如下圖所示）：
　　（1）指標域：用于指向當前節點的直接前驅節點；
　　（2）資料域：用于存盤資料元素；
　　（3）指標域：用于指向當前節點的直接后繼節點，

5.2 雙向鏈表的創建

同單鏈表相比，雙鏈表僅是各節點多了一個用于指向直接前驅的指標域，因此，我們可以在單鏈表的基礎輕松實作對雙鏈表的創建，

和創建單鏈表不同的是，創建雙向鏈表的程序中，每一個新節點都要和前驅節點之間建立兩次鏈接，分別是：
　　（1）將新節點的 prior 指標指向直接前驅節點；
　　（2）將直接前驅節點的 next 指標指向新節點；

5.3 雙向鏈表基本操作

前面學習了如何創建一個雙向鏈表，本節學習有關雙向鏈表的一些基本操作，即如何在雙向鏈表中添加、洗掉、查找或更改資料元素，

本節知識基于已熟練掌握雙向鏈表創建程序的基礎上，我們繼續上節所創建的雙向鏈表來學習本節內容，創建好的雙向鏈表如圖 1 所示：

雙向鏈表添加節點

根據資料添加到雙向鏈表中的位置不同，可細分為以下 3 種情況：
　　　
　　 （1）添加至表頭
　　將新資料元素添加到表頭，只需要將該元素與表頭元素建立雙層邏輯關系即可，
　　換句話說，假設新元素節點為 temp，表頭節點為 head，則需要做以下 2 步操作即可：
　　　① temp->next=head; head->prior=temp;
　　　② 將head 移至 temp，重新指向新的表頭；

例如，將新元素 7 添加至雙鏈表的表頭，則實作程序如圖 2 所示：

（2）添加至表的中間位置
　　同單鏈表添加資料類似，雙向鏈表中間位置添加資料需要經過以下 2 個步驟，如圖 3 所示：
　　　① 新節點先與其直接后繼節點建立雙層邏輯關系；
　　　② 新節點的直接前驅節點與之建立雙層邏輯關系；

（3）添加至表尾
　　與添加到表頭是一個道理，實作程序如下（如圖 4 所示）：
　　　① 找到雙鏈表中最后一個節點；
　　　② 讓新節點與最后一個節點進行雙層邏輯關系；

雙向鏈表洗掉節點

雙鏈表洗掉結點時，只需遍歷鏈表找到要洗掉的結點，然后將該節點從表中摘除即可，

例如，從圖 1 基礎上洗掉元素 2 的操作程序如圖 5 所示：

雙向鏈表查找節點

通常，雙向鏈表同單鏈表一樣，都僅有一個頭指標，因此，雙鏈表查找指定元素的實作同單鏈表類似，都是從表頭依次遍歷表中元素，

雙向鏈表更改節點

更改雙鏈表中指定結點資料域的操作是在查找的基礎上完成的，實作程序是：通過遍歷找到存盤有該資料元素的結點，直接更改其資料域即可，
　　
關于鏈表Python編程實作代碼可參考↓（個人撰寫，僅供參考，歡迎提出寶貴建議）

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/22 9:14 
# @Author : vaxtiandao
# @File : ds_14.py
# 定義結點類，包含兩個成員：結點元素值和指向下一結點的指標
class SingleNode():
    # 結點類初始化
    def __init__(self, item):
        self.item = item  # 存放結點的數值
        self.next = None  # 下一指標指向
        self.hail = None  # 上一指標指向


# 定義單鏈表
class DoubleLinkList():
    # 鏈表類初始化
    def __init__(self):
        self.head = None  # 指向頭結點
        self.hail = None  # 指向尾結點

    # 判斷鏈表是否為空
    def is_empty(self):
        return self.head == None

    # 輸出鏈表長度
    def get_length(self):
        return len(self.travel())

    # 遍歷整個鏈表
    def travel(self):
        curlist = []
        cur = self.head
        while cur != None:
            curlist.append(cur.item)
            cur = cur.next
        return curlist

    # 頭插法創建單鏈表
    def add(self, newItem):
        node = SingleNode(newItem)
        if self.head is not None:
            node.next = self.head
            self.head = node
            node.next.prev = node
        else:
            self.head = node
            self.hail = node

    # 尾插法創建單鏈表
    '''def append(self,newItem):
        node = SingleNode(newItem)
        # 從尾結點開始遍歷
        cur = self.head
        if self.is_empty():
            self.head = node
        while cur.next != None:
            cur = cur.next
        cur.next = node
        node.prev = cur'''

    def append(self, newItem):
        node = SingleNode(newItem)
        if self.hail is not None:
            self.hail.next = node
            node.prev = self.hail
            self.hail = node
        else:
            self.hail = node
            self.head = node

    # 指定位置添加元素,pos從零開始
    def insert(self, pos, newItem):
        node = SingleNode(newItem)
        if pos <= 0:
            self.add(newItem)
        elif pos > (self.get_length() - 1):
            self.append(newItem)
        else:
            count = 0
            cur = self.head
            while count < pos:
                count += 1
                cur = cur.next
            node.next = cur
            node.prev = cur.prev
            cur.prev.next = node
            cur.prev = node

    # 洗掉指定位置上的結點
    def remove(self, pos):
        cur = self.head
        count = 0
        if 1 <= pos < (self.get_length()):
            while count < pos - 1:
                cur = cur.next
                count += 1
            cur.next = cur.next.next
            cur.next.prev = cur
        elif pos == 0:
            self.head = cur.next
        else:
            return '輸入的位置有誤，請確認'

    # 查找指定位置的結點值
    def find(self, pos):
        cur = self.head
        count = 0
        if 0 <= pos < (self.get_length()):
            while count < pos:
                cur = cur.next
                count += 1
            return cur.item
        else:
            return '輸入的位置有誤，請確認'

    # 更新鏈表中的某個位置的值
    def update(self, pos, newItem):
        cur = self.head
        count = 0
        if 0 <= pos < (self.get_length()):
            while count < pos:
                cur = cur.next
                count += 1
            cur.item = newItem
        else:
            return '輸入的位置有誤，請確認'

    # 清空鏈表
    def clear(self):
        self.head = None
        self.hail = None


# 實體化物件
doublelinklist = DoubleLinkList()
print("初始化雙向鏈表：", doublelinklist)
print("________________________________________________________________________________________________")
# 檢查鏈表是否為空
print("未插入元素之前鏈表為空：", doublelinklist.is_empty(), end="")
print("________________________________________________________________________________________________")
# 使用頭插法隨機添加資料
import random
for i in range(10):
    doublelinklist.add(random.randint(1, 100))
# 判斷鏈表是否為空
print("插入元素之后鏈表不為空：", doublelinklist.is_empty())
print("________________________________________________________________________________________________")
# 查詢鏈表長度
print("當前鏈表長度為：", doublelinklist.get_length())
print("________________________________________________________________________________________________")
# 查看資料
print("當前雙向鏈表遍歷后元素為：", doublelinklist.travel())
print("________________________________________________________________________________________________")
# 使用尾插法
print("尾插法之前，雙向鏈表遍歷后元素為：", doublelinklist.travel())
doublelinklist.append(10)
print("尾插法之后，雙向鏈表遍歷后元素為：", doublelinklist.travel())
print("________________________________________________________________________________________________")
# 使用頭插法
print("頭插法之前，雙向鏈表遍歷后元素為：", doublelinklist.travel())
doublelinklist.add(0)
print("頭插法之后，雙向鏈表遍歷后元素為：", doublelinklist.travel())
print("________________________________________________________________________________________________")
# 指定位置插入值
print("指定位置插入之前，雙向鏈表遍歷后元素為：", doublelinklist.travel())
doublelinklist.insert(1, 1)
print("指定位置插入之后，雙向鏈表遍歷后元素為：", doublelinklist.travel())
print("________________________________________________________________________________________________")
# 查找指定位置的值
t = 5
print("當前鏈表第{} 個元素數值為：".format(t), doublelinklist.find(t))
print("________________________________________________________________________________________________")
# 洗掉指定位置的值
print("洗掉指定位置值之前，雙向鏈表遍歷后元素為：", doublelinklist.travel())
doublelinklist.remove(4)
print("洗掉指定位置值之前，雙向鏈表遍歷后元素為：", doublelinklist.travel())
print("________________________________________________________________________________________________")
# 更新指定位置的值
doublelinklist.update(5, 5)
print("當前雙向鏈表遍歷后元素為：", doublelinklist.travel())
print("________________________________________________________________________________________________")
# 清空鏈表資料
doublelinklist.clear()
print("當前雙向鏈表遍歷后元素為：", doublelinklist.travel())
print("________________________________________________________________________________________________")

以下是如上代碼實作效果：

　　關于雙向鏈表基本操作的C語言代碼，見這👉：雙向鏈表的基本操作