鏈表（單向、雙向、單向循環、雙向循環）學習過程總結——有源代碼、注釋和示意圖

前段時間學習了數據結構的部分知識，然后到上個星期別人問相關問題的餓時候發現自己對鏈表的知識都有些模糊了，主要還是有些細節的地方記不太清楚，所以就萌生了寫這篇博客的想法，一是要重新復習一下鏈表的相關知識，二呢用C++重新寫一遍，熟悉C++語言。之前用C語言實現鏈表操作的時候也寫過幾篇博客，但是重點都是體現在代碼部分，示意圖都是從網站上下過來的或是別人博客上摘過來的，這次自己用Processon在網頁上重新畫了鏈表操作的過程示意圖，根據自己的理解畫的一些簡易圖，然后感覺自己對鏈表要注意的細節更加清楚了。寫這個博客主要是自己對知識點的復習，理解的一個檢查，如果能幫助某些志同道合的人那就更加欣慰了。

這里我主要分四個知識點來介紹鏈表，分別是單向鏈表、單向循環鏈表、雙向鏈表和雙向循環鏈表。操作包括鏈表的初始化、鏈表的創建、鏈表插入結點、鏈表刪除結點以及鏈表的刪除，也就是釋放內存。

單向鏈表

單向鏈表就是通過每個結點的指針指向下一個結點從而鏈接起來的結構。下面看下單向鏈表的示意圖（以下圖片全是原創）
單向鏈表的初始化：這里我所講的鏈表都是頭結點不參與計算的，也就是說第一個結點都是頭結點后面的第一個結點。所以我要先申明一點，這里我把鏈表的初始化放在了構造函數部分，然后析構函數負責釋放頭結點的內存。
單向鏈表的創建過程：鏈表的創建就是添加結點到鏈表的最后，開始是添加一個結點到head結點后面，然后添加一個結點到上次添加的結點后面，每次新建的結點的指針總是指向NULL指針。從上面的示意圖可以看出，我們需要一個輔助指針一直指向最后一個結點，這個輔助結點就是為了讓每次添加的結點都放置在最后一個位置。
單向鏈表插入結點過程：源代碼中的的插入結點函數我設置了一個指定位置，就是在指定位置插入結點。首先，通過位置變量position讓ptemp結點移動到要插入位置的前一個位置，然后接下來的過程就是和創建鏈表的過程是一樣的，把新建的結點添加到ptemp的后面。這里變量position可以從1到鏈表長度加1，意思就是如果不算頭結點的話有3個結點，那你的position變量就可以從1到4，這是因為ptemp指針可以到第3個結點的位置，所以新建結點的位置就可以到4了。
單向鏈表刪除結點過程：源代碼中的刪除結點函數也有一個指定位置變量，為了刪除指定位置的結點。和插入結點一樣通過變量position把ptemp移動到要刪除結點的前一個位置，然后讓ptemp結點中的指針指向要刪除結點后面的一個結點，也就是ptemp結點的下一個的下一個結點，雖然這個結點可能為空，但是程序還是正常運行。但是這里和插入結點不同的是變量position只能從1到鏈表的長度，是因為ptemp移動到最后一個結點的時候，它的下一個結點為空，所以不不需要參與刪除了。

單向循環鏈表

1.單向循環鏈和單向鏈表有點相似的地方，就是都是通過結點的指針指向下一個結點，然后這樣連接起來，但是有一個不同的地方就是單向鏈表的最后一個結點的指針指向NULL指針，而單向循環鏈表的最后一個結點的指針指向的是頭結點，這樣構成一個循環結點的環。下面是單向循環鏈表的示意圖：

2.單向循環鏈表的初始化：從上面的示意圖可以知道，單向循環鏈表最后一個結點的指針是指向頭結點的，那么當只有一個結點的時候就是頭結點的指針指自己。

3.單向循環鏈表的創建過程：和單向鏈表的創建過程相似，區別就是最后一個結點的指針是指著頭結點的。所以程序實現的時候每次新建一個結點的時候都是讓它的指針指向頭結點。

4.單向循環鏈表插入結點過程：因為這個時候是往鏈表中插入結點，結點已經構成一個環了，所以直接讓新插入結點的指針指向下一個結點就行。就算插入的是最后一個位置，讓它的指針指向下一個結點也符合條件，因為最后一個位置的下一個結點就是頭結點。

5.單向循環鏈表刪除結點過程：結合單向鏈表刪除結點過程和上面單向循環鏈表插入結點過程的解釋，那么這里就不難理解了。

雙向鏈表

1.聽名字可能就能猜到雙向鏈表就是鏈表結點包含兩個指針，一個指針是指向下一個結點的，另一個指針當然就是指向上一個結點的。這樣的鏈表就可以通過第一個結點找到最后一個結點，當然也可以通過最后一個結點找到第一個結點，因為它是雙向的，下面看下雙向鏈表的示意圖：

2.雙向鏈表的初始化：由于這里的鏈表頭結點不參與計算，所以頭結點的pPre指針是一直指向NULL指針的。

3.雙向鏈表的創建過程：由于雙向鏈表的每個結點包含兩個指針那么這個時候我們就要小心處理好每一個指針的指向，要不然會有很多意想不到的錯誤。同樣的，和單向鏈表的創建過程一樣，需要一個輔助指針來指向最后一個結點，然后每新建一個結點，這個結點的pNext指針都是指向NULL指針的，pPre指針指向上一個結點（這是和單向鏈表不同的地方），然后讓上一個指針的pNext指向新建的結點，這樣整個鏈表就連接起來了。

4.雙向鏈表插入結點過程：知道了雙向鏈表的創建過程，那么插入結點的過程就大同小異了，有一點需要特別注意的就是這里的變量position范圍也是從1到鏈表長度加1，但是如果待插入的位置是最后一個位置的話，情況就不同了，看到下面的圖我們可以很好的理解，因為沒新建一個結點的時候都需要處理兩個指針，而且新建結點的下一個結點的pPre指針就需要指向這個新建的結點，但是有可能這個新建的結點可能就已經是最后一個結點了，那么這個時候再執行

ptemp->pNext->pPre = pnew;

這條指令的時候就會報錯了，因為ptemp->pNext已經是個NULL指針了，那空指針哪里還有pPre呢。因此在程序中要進行一次判斷，看看結點是否是最后一個結點。

5.雙向鏈表刪除結點的過程：要注意的問題和插入結點一樣，看看這個結點是否為NULL。這里就不重復了。

雙向循環鏈表

1.雙向循環鏈表相對于上面的雙向鏈表多了循環兩個字，我們就可以結合單向循環鏈表聯想到，其實就是雙向鏈表夠成了一個環。下面先看看雙向循環鏈表的示意圖：

2.雙向循環鏈表初始化：雙向循環鏈表的初始化可以通過單向循環鏈表的初始化聯想到，就是兩個指針都指向頭結點本身。這是因為pPre指針要指向上一個結點，而pNext指針要指向下一個結點，這個時候就只有頭結點一個，所以就都指向頭結點了。

3.雙向循環鏈表的創建過程：這個也過程和上面單向循環鏈表都類似，就是多了一個結點指針要考慮到。

4.雙向循環鏈表插入結點過程：和單向循環鏈表過程類似。

5.雙向循環鏈表刪除結點過程：這個也是和單向循環鏈表類似。

寫了2個多小時，終于快結束了，其實加上畫圖和敲源代碼總共花了好幾天的時間。最后我想說說我對鏈表的一點個人理解，開始學習的時候看過去挺簡單的，但是自己操作的時候就會發現遇到很多細節性的問題，所以勸解那些看的人還是動動手自己寫一遍。然后呢，我想說的是，這里列出的只是鏈表的一些簡單操作，不能說會了這些鏈表就都會了，當然知識也是相通的，如果真正理解了的話，那不管怎么變也不怕了。比如：鏈表數據的排序、然后輸入結點時按順序插入等，還有很多很多。

PS：希望大家一起學習、一起討論、一起進步。

本文鏈接：https://blog.csdn.net/Drogal_dracarys/article/details/106126437

智能推薦

freemarker + ItextRender 根據模板生成PDF文件

1. 制作模板 2. 獲取模板，并將所獲取的數據加載生成html文件 2. 生成PDF文件其中由兩個地方需要注意，都是關于獲取文件路徑的問題，由于項目部署的時候是打包成jar包形式，所以在開發過程中時直接安照傳統的獲取方法沒有一點文件，但是當打包后部署，總是出錯。于是參考網上文章，先將文件讀出來到項目的臨時目錄下，然后再按正常方式加載該臨時文件；還有一個問題至今沒有解決，就是關于生成PDF文件...

電腦空間不夠了？教你一個小秒招快速清理 Docker 占用的磁盤空間！

Docker 很占用空間，每當我們運行容器、拉取鏡像、部署應用、構建自己的鏡像時，我們的磁盤空間會被大量占用。如果你也被這個問題所困擾，咱們就一起看一下 Docker 是如何使用磁盤空間的，以及如何回收。 docker 占用的空間可以通過下面的命令查看： TYPE 列出了docker 使用磁盤的 4 種類型： Images：所有鏡像占用的空間，包括拉取下來的鏡像，和本地構建的。 Con...

requests實現全自動PPT模板

http://www.1ppt.com/moban/ 可以免費的下載PPT模板，當然如果要人工一個個下，還是挺麻煩的，我們可以利用requests輕松下載訪問這個主頁，我們可以看到下面的樣式點每一個PPT模板的圖片，我們可以進入到詳細的信息頁面，翻到下面，我們可以看到對應的下載地址點擊這個下載的按鈕，我們便可以下載對應的PPT壓縮包那我們就開始做吧首先，查看網頁的源代碼，我們可以看到每一...

SpringMvc自定義類型轉換器步驟

...

Linux C系統編程-線程互斥鎖（四）

互斥鎖互斥鎖也是屬于線程之間處理同步互斥方式，有上鎖/解鎖兩種狀態。互斥鎖函數接口 1）初始化互斥鎖 pthread_mutex_init() man 3 pthread_mutex_init (找不到的情況下首先 sudo apt-get install glibc-doc sudo apt-get install manpages-posix-dev) 動態初始化 int pthread_...