數據結構中的鍊表,你知道多少?

2020-12-25 愚公要移山1

為什麼要講鍊表呢？這是因為java中有很多集合類底層都是通過鍊表來實現的。而且面試的時候，鍊表的實現是經常考的一個知識點。所以這篇文章的重點在於，如何使用代碼去實現這些數據結構。但是這篇文章我不打算直接上來就講鍊表，而是先從線性表開始。按照慣例先給出這篇文章的大致脈絡吧。

首先，是對數據結構中線性表，做一個回顧。還講了其兩大存儲結構，順序存儲結構和鏈式存儲結構。接下來，重點講各種鍊表的介紹，以及常用方法和特點最後，對java中使用鍊表的集合類，進行一個介紹。當然，還有一些常見的面試題。

OK，開始。

一、線性表

為了很好的描述這個概念，先從一個例子開始吧，比如幼兒園的小朋友放學之後，都是手拉手排著隊走出校園，這些小朋友從外表來看就像是一條鏈子，而線性表就和這個鏈子一樣，這些小朋友就像是線性表裡面的數據元素，從外面看一個接一個。比較正式的定義那就是：線性表：0個或者多個數據元素的有限序列。

剛剛我提到的都是從表面來看都是一樣的，說明在內部的實現方式是不一樣的，下面就是線性表的兩種存儲結構：順序存儲結構和鏈式存儲結構。

順序存儲結構：用一段地址連續的存儲單元依次存儲線性表的數據元素。

鏈式存儲結構：地址可以連續也可以不連續的存儲單元存儲數據元素

今天主要講的就是基於鏈式存儲結構的鍊表。你可以這樣理解，比如說你要找一個人，名字叫張三，你首先跑到A，發現沒有，A告訴你B可能知道，你跑到了B。B說C可能知道，你跑到了C，張三果然在C那裡，如果沒有就這樣一直不停的去找。一張圖看一下

但是這只是基礎，對線性表的描述，不想花費太多時間在這。下面用一張圖表述吧。

有了上面這張圖，相信對分類等都有了了解和認識了。下面開始今天的主題單鍊表。

下面在對這兩種存儲結構進行一個對比。

二、鍊表

1、單鍊表

對於鍊表，裡面主要有幾個重要的信息，對於每一個節點（比如上一節講到的A,B,C三處）都有下一個節點的地址和當前節點的數據。下面代碼實現一下：

首先是節點的定義（由於直接上傳代碼，效果不好，這裡就給出圖片了））：

接下來無非是對節點的增刪改查罷了，先看基本的操作。

下面就是正刪改查了，但是有一個思路需要我們要牢記，這樣在使用其他語言實現的時候，就能快速的掌握，這是我自己的方法。上面已經描述了通過索引查找元素，所以下面只考慮，插入刪除操作就好了。

首先，我們要判斷當前的空間是否滿足增刪該查的條件接下來，判斷增刪改查的位置是否正確最後，增刪改查之後沒有副作用產生。

第一個操作：插入（三種方式：頭插入、尾插入、中間插入）

對於插入操作，使用一張圖簡單表述一下

第二種操作：刪除

對刪除操作同樣一張圖

小結：上述是對單鍊表的增刪改查操作，對於其他鍊表關鍵就在於對單鍊表的更改。當然這裡只給出了鍊表的代碼實現。對於順序存儲結構的順序表實現。同樣也是這個道理。你只需要定義一個節點進行增刪改查就好了。

2、循環鍊表

如果你對單鍊表的操作能夠掌握的話，剩下的這幾種鍊表，我相信你也能很快掌握，只不過把node中的基本數據改一下，增刪的時候多一兩行代碼。對於循環鍊表，你可以想像成y一個閉環的鍊表。也就是最後一個元素又指向了第一個元素。其特點是這裡的討論重點。

特點

（1）適合合併兩個循環鍊表：有了尾指針直接合併，比如說下面有兩個循環鍊表。

現在使用尾指針合併他們。

（2）從表中任何一個節點出發，都能訪問鍊表的全部節點。這一點很好理解。

3、雙向鍊表

從名字就可以看出，每一個節點既指向前驅又指向後繼。

這個雙向鍊表相對於單鍊表還是比較複雜的，畢竟每個節點多了一個前驅，因此對於插入和刪除要格外小心。雙向鍊表的優點在於對每個節點的相鄰接點操作時候，效率會比較高。

三、java中的線性表表

最典型的就是Collection接口了。下面還包括了一些他的實現類，比如List接口，ArrayList類和LinkList類，其底層都是實現了線性表。我們只需要知道Collection這些全部都是使用了線性表，因此在遇見面試題的時候，如果要求不能使用java中提供的集合類。那麼我們應該學會使用上述的線性表表的操作去解決問題。

四、常見面試題，你會幾個？

對於面試題，由於篇幅問題，所以這裡只給出思路，本來我把代碼放進來了，但是又刪除了（原諒我顫抖的手）

1、單鍊表的創建和遍歷

本題上面已經給出答案，這裡不再說了。

2、求單鍊表中節點的個數

這一題相當於，遍歷一遍鍊表

3、查找單鍊表中的倒數第k個結點（劍指offer，題15）

先計算出鍊表的長度size，然後直接輸出第(size-k)個節點就可以了

4、查找單鍊表中的中間結點

你可以先獲取整個鍊表的長度N，N/2就好了。

5、合併兩個有序的單鍊表，合併之後的鍊表依然有序【出現頻率高】

這個類似於歸併排序，你創建一個新鍊表，然後把上面兩個鍊表依次比較，插入新鍊表

6、單鍊表的反轉【出現頻率最高】（劍指offer，題16）

這個是對插入操作的考察，在上面寫了三種插入操作實現方式，從頭到尾遍歷鍊表，取出當前鍊表節點，插入新鍊表的頭結點。這樣第一個取出的節點，在新鍊表就是最後一個

7、從尾到頭列印單鍊表（劍指offer，題5）

8、判斷單鍊表是否有環

這裡也是用到兩個指針，如果一個鍊表有環，那麼用一個指針去遍歷，是永遠走不到頭的。因此，我們用兩個指針去遍歷：first指針每次走一步，second指針每次走兩步，如果first指針和second指針相遇，說明有環。

9、取出有環鍊表中，環的長度

10、單鍊表中，取出環的起始點（劍指offer，題56）。

11、判斷兩個單鍊表相交的第一個交點（劍指offer，題37）

12、 已知一個單鍊表中存在環，求進入環中的第一個節點

基本上就寫這麼多吧，由於是基礎內容，也比較容易理解，在大學的時候都學到過，這裡算是一個複習鞏固吧。

有什麼問題，還請批評指正。謝謝

相關焦點

  • 數據結構之鍊表
    數據是最重要的財富數據結構之鍊表## 什麼是鍊表鍊表一種時間複雜度和空間複雜度為線性的數據結構鍊表的種類主要有三種，單鍊表，雙鍊表，雙向循環鍊表。鍊表的優缺點鍊表是一種鏈式結構，使得它對內存沒有太大的要求。可以充分使用散亂的內存空間，插入和刪除的時間複雜度比數組好。但是結構實現起來比較複雜，容易出錯。而且不具備隨機訪問的特性，每次查詢都要從頭節點出發。
  • 一篇文章搞懂 數據結構中的 線性表存儲方式(順序表 與 鍊表)
    我們知道：數據結構是計算機存儲和組織數據的方式。選擇不同的數據結構來處理數據，可以在不同的場景發揮很棒的效率。數據結構從邏輯層面上分為線性結構和非線性結構。線性結構：顧名思義，就是數據連成線一樣存儲。順序表的時間性能查找（只知道內容，不知道下標叫查找）：一般來說順序表查找一個元素與鍊表查找一個元素是相同的時間複雜度，但在數據有序的情況下，順序表可以使用二分查找
  • 【算法系列】面試常用數據結構(二):鍊表
    Hello 大家好我是今天沒寫 bug 的八哥，上周我們總結分享了面試高頻數據結構中的數組和避坑指南，如果你還沒有閱讀的話快點擊下面圖片進行閱讀吧。之前我們講過，數據結構只有兩種：一維數據結構和多維數據結構。一維數據結構最重要的是連續性的數組和非連續性的鍊表，這種連續性和非連續性的特點會一直影響及應用在對應的多維數據結構中。
  • 結合JAVA詳解鍊表、棧、隊列等數據結構
    前言其實在學習數據結構之前，我也是從來都沒了解過這門課，但是隨著工作的慢慢深入，之前學習的東西實在是不夠用，並且太皮毛了。太淺，只是懂得一些淺層的，我知道這個東西怎麼用，但是要優化、或者是解析，就不知道該咋弄了。
  • Java線性數據結構之數組和鍊表篇
    按數據的邏輯結構來說，線性結構指N個元素數據的有序（次序）集合。Java程序中較為廣泛線性結構包含線性表，棧，隊列，雙隊列，數組等。今天詳細講解數組和鍊表結構。ArrayList數組擴容的實現源碼部分鍊表鍊表是一種非連續、非順序的結構，數據元素的邏輯順序是通過鍊表中的指針連結次序實現的，鍊表由一系列結點組成
  • Smaller And Smarter Python數據結構:鍊表相加
    如果你是第一次看，也許，你可以看看本系列下面的文章：Smaller And Smarter Python數據結構：鍊表逆轉Smaller And Smarter Python數據結構：刪除無序鍊表重複結點今日問題 """目標：寫一段程序，計算兩個單鍊表所代表數之和例如：輸入-> 9->0->
  • Java實現單鍊表、棧、隊列三種數據結構
    ：文末有最新Java實戰項目和面試題作者：遠航cnblogs.com/yang-guang-zhang/p/13884023.html一、單鍊表1、在我們數據結構中它裡面的數據元素是以結點為單位，每個結點是由數據元素的數據和下一個結點的地址組成，在java集合框架裡面  LinkedList、HashMap（數組加鍊表）等等的底層都是用鍊表實現的。
  • 面試需要知道的六種數據結構
    數據結構是算法的基石，若無紮實的數據結構基礎，想把算法學好甚至融會貫通是非常困難的，而優秀的算法又往往取決於你採用哪種數據結構。本篇主講：數字、字符串；鍊表；棧；隊列；雙端隊列；樹。數組和字符串是最基本的數據結構，在很多程式語言中都有著十分相似的性質，而圍繞著它們的算法面試題也是最多的。
  • 應對程式設計師面試,你必須知道的八大數據結構
    這就是為什麼在面試過程中，需要考察軟體工程師對數據結構的理解。幾乎所有的問題都需要面試者對數據結構有深刻的理解。無論你是初入職場的新兵（剛從大學或者編程培訓班畢業），還是擁有幾十年經驗的職場老鳥。簡單地說，數據結構是以某種特定的布局方式存儲數據的容器。這種「布局方式」決定了數據結構對於某些操作是高效的，而對於其他操作則是低效的。首先我們需要理解各種數據結構，才能在處理實際問題時選取最合適的數據結構。
  • 基本數據結構-鍊表的總結
    鍊表的反轉鍊表反轉再讓結點1的next域指向結點3，最後將結點2的next域指向結點1，頭結點的next域指向結點2。 p->next = list->next;//2的next指向結點1 list->next = p;//頭結點指向結點2 } return list;}怎麼經過一次遍歷求出鍊表的中間值
  • 數據結構java面試題及答案
    數組是最常用的基礎數據結構，它將元素保存在連續的內存中。它也是面試最喜歡的問題之一，在代碼面試中你會經常聽到很多關於數組的問題，例如，數組的反轉、數組的排序或者查找數組中的一個元素。數組結構的一個關鍵優點是在知道索引的情況能夠以O(1)的複雜度找到一個元素。但是增加或者刪除一個元素是很慢的，因為一旦創建了一個數組，你就不能改變它的大小了。
  • 盤點數據結構的應用場景
    數據結構是計算機編程中最重要的內容之一，我們經常會看到一個公式，那就是程序=數據結構+算法。從這個公式我們就能夠看出來數據結構是多麼的重要，要想寫出優雅高效的程序，一定離不開良好的數據結構，今天我們就來盤點一下常用的數據結構的應用場景。
  • 教你用 Python 實現 HashMap 數據結構
    讓我們帶著疑問來看看hashmap的基本結構。基本結構hashmap這個數據結構其實並不難，它的結構非常非常清楚，我用一句話就可以說明，其實就是鄰接表。雖然這兩者的用途迥然不同，但是它們的結構是完全一樣的。
  • 每個程式設計師都必須知道的8種數據結構
    數據結構是一種特殊的組織和存儲數據的方式，可以使我們可以更高效地對存儲的數據執行操作。數據結構在計算機科學和軟體工程領域具有廣泛而多樣的用途。幾乎所有已開發的程序或軟體系統都使用數據結構。此外，數據結構屬於計算機科學和軟體工程的基礎。當涉及軟體工程面試問題時，這是一個關鍵主題。因此，作為開發人員，我們必須對數據結構有充分的了解。在本文中，我將簡要解釋每個程式設計師必須知道的8種常用數據結構。
  • 深入理解Linux內核鍊表
    相對於數組，鍊表具有更好的動態性，建立鍊表時無需預先知道數據總量，可以隨機分配空間，可以高效地在鍊表中的任意位置實時插入或刪除數據。鍊表的開銷主要是訪問的順序性和組織鏈的空間損失。通常鍊表數據結構至少應包含兩個域：數據域和指針域，數據域用於存儲數據，指針域用於建立與下一個節點的聯繫。
  • 什麼是鍊表?
    （給算法愛好者加星標，修煉編程內功）來源：碼海如果說數據結構是算法的基礎
  • 二進位跳動帶你看Redis數據結構底層
    一場面試至少也是半小時起，如果一個問題你只能回答不到50個字，這個結果肯定不是面試官想要的，其實也不是你自己想要的。緊接著還有問題，String在redis底層是怎麼存儲的？這些數據類型在Redis中是怎麼存放的？Redis快的原因是不是只有單線程和基於內存處理？
  • 概述Java中的數據結構是什麼及其內部實現原理
    本文主講介紹幾種常用的數據結構，數據結構是一種容器的一個分支,容器時用來裝東西的,那麼數據結構就是專門用來存儲數據的容器。首先我們從數組來給大家漸漸引入數據結構,容器的概念。那麼數組是什麼呢,數組是一個對象,準確的說我們將對象進行分類,具有特定功能的對象就被成為數據結構或者容器,集合等，數組就是其中之一。
  • 數據結構和算法學習指南
    從整體到細節，自頂向下，從抽象到具體的框架思維是通用的，不只是學習數據結構和算法，學習其他任何知識都是高效的。先說數據結構，然後再說算法。數據結構的存儲方式只有兩種：數組（順序存儲）和鍊表（鏈式存儲）。
  • 給Java程式設計師的20個鍊表面試題
    什麼是鍊表？數據結構在程序面試中極其重要。鍊表則是對數組數據結構進行的補充，是另一種常見的數據結構。和數組相似的是，鍊表也是線性數據結構，並以線性方式儲存元素。但是，和數組不同的是，鍊表不將元素儲存在連續的位置；相反，其元素分散在內存中的各個地方，並以節點進行相互連接。鍊表不過是一個節點的列表，其中每一個節點都包含存儲的值和下一個節點的位置。