鏈表
鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，是用一組任意的存儲單元來存儲數(shù)據(jù)，存儲單元不一定是連續(xù)的。數(shù)據(jù)元素隨機存儲，并通過指針表示數(shù)據(jù)之間邏輯關(guān)系的存儲結(jié)構(gòu)就是鏈?zhǔn)酱鎯Y(jié)構(gòu)。
鏈表的每個元素稱為一個節(jié)點，每個節(jié)點都可以存儲在內(nèi)存中的不同的位置，為了表示每個元素與后繼元素的邏輯關(guān)系，以便構(gòu)成“一個節(jié)點鏈著一個節(jié)點”的鏈?zhǔn)酱鎯Y(jié)構(gòu)，
鏈表的節(jié)點
每個節(jié)點都包含兩部分，第一部分稱為鏈表的數(shù)據(jù)區(qū)域，用于存儲元素本身的數(shù)據(jù)信息，它不局限于一個成員數(shù)據(jù)，也可是多個成員數(shù)據(jù)。第二部分是一個結(jié)構(gòu)體指針，稱為鏈表的指針域，用于存儲其直接后繼的節(jié)點信息，這里用next表示，
next的值實際上就是下一個節(jié)點的地址，當(dāng)前節(jié)點為末節(jié)點時，next的值設(shè)為空指針
1. data: 數(shù)據(jù)元素本身，其所在的區(qū)域稱為數(shù)據(jù)域；value代表該節(jié)點存儲的值
2. next: 指向直接后繼元素的指針，所在的區(qū)域稱為指針域；
next指向下一個節(jié)點，next可能指向一個單一節(jié)點，也可能指向一個鏈表，也可能指向null(代表尾節(jié)點)。
頭指針就是鏈表的名字，僅僅是個指針而已。頭結(jié)點是為了操作的統(tǒng)一與方便而設(shè)立的，放在第一個有效元素結(jié)點（首元結(jié)點）之前，其數(shù)據(jù)域一般無意義（當(dāng)然有些情況下也可存放鏈表的長度、用做監(jiān)視哨等等）。
雙向鏈表
雙向鏈表(雙鏈表)是鏈表的一種。和單鏈表一樣，雙鏈表也是由節(jié)點組成，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。一般我們都構(gòu)造雙向循環(huán)鏈表。
數(shù)組
1.?數(shù)組可以方便的遍歷查找需要的數(shù)據(jù)。
2. 在查詢數(shù)組指定位置（如查詢數(shù)組中的第4個數(shù)據(jù)）的操作中，只需要進行1次操作即可，時間復(fù)雜度為O(1)。
3. 數(shù)組在內(nèi)存中占用了連續(xù)的空間，在進行類似的查找或者遍歷時，本質(zhì)是指針在內(nèi)存中的定向偏移。然而，當(dāng)需要對數(shù)組成員進行添加和刪除的操作時，數(shù)組內(nèi)完成這類操作的時間復(fù)雜度則變成了O(n)。
鏈表進行插入和刪除操作上比數(shù)組更加高效，鏈表操作的時間復(fù)雜度僅為O(1)。
鏈表在內(nèi)存中不是連續(xù)存儲的，所以可以充分利用內(nèi)存中的碎片空間。
鏈表是很多算法的基礎(chǔ)，最常見的哈希表就是基于鏈表來實現(xiàn)的。
在程序運行期間，用動態(tài)內(nèi)存分配函數(shù)來申請的內(nèi)存都是從堆上分配的，動態(tài)內(nèi)存的生存期有程序員自己來決定，使用非常靈活，但也易出現(xiàn)內(nèi)存泄漏的問題，
為了防止內(nèi)存泄漏的發(fā)生，必須及時調(diào)用free（）釋放已不再使用的內(nèi)存。
鏈表存放在堆里。
問題一： 查找兩個鏈表的公共節(jié)點的幾種實現(xiàn)方案
公共節(jié)點：兩個鏈表擁有公共節(jié)點不是指兩個鏈表的節(jié)點的數(shù)據(jù)域相同，而是指兩個鏈表的指針指向同一個節(jié)點，即具有相同的地址。
由于單鏈表只有一個next域，所以只要找到兩個鏈表的第一個公共節(jié)點，那么從第一個公共節(jié)點開始，兩個鏈表的公共節(jié)點節(jié)點的next 指向是一致的。這個節(jié)點后面的節(jié)點均是重合的，有部分重合的單鏈表，拓?fù)湫螤羁雌饋硐馳。
參考：兩個鏈表的第一個公共節(jié)點, Masonry尋找2個view的公共父視圖_gcs的博客-CSDN博客
問題二： 判斷鏈表是否有環(huán)？
1. 判斷鏈表是否存在環(huán)，有環(huán)的話就沒有尾結(jié)點，不存在一個結(jié)點的next指針是null。鏈表如果很長，較為復(fù)雜。
或者： 把所有節(jié)點的next指針地址存起來，如果有節(jié)點的next 指向相同就有環(huán)。
2. 利用快慢指針
定義兩個指針，初始位置都放在頭節(jié)點，快慢指針一起走，快指針一次走兩步（需要注意邊界條件），慢指針一次走一步，如果快指針走到末節(jié)點NULL，該鏈表就不帶環(huán)。如果快慢指針相遇，該鏈表就帶環(huán)。
問題三： 鏈表逆序翻轉(zhuǎn)
1. 三個指針法
2. 創(chuàng)建新表，頭插法
3. 遞歸后移法
鏈表反轉(zhuǎn)步驟分解附圖_Pichairen-CSDN博客? 圖文講解較為詳細(xì)怎么一步一步替換，三個指針法，能看到明白
數(shù)據(jù)結(jié)構(gòu)中-實現(xiàn)單鏈表的反轉(zhuǎn)_伍華鋒的博客-CSDN博客_數(shù)據(jù)結(jié)構(gòu)單鏈表反轉(zhuǎn)
單向鏈表逆序_瀟灑的程序員-CSDN博客? ?三個指針的方法具體代碼實現(xiàn)
參考：
什么是單鏈表，鏈?zhǔn)酱鎯Y(jié)構(gòu)詳解
鏈表（單向鏈表的建立、刪除、插入、打?。?- 藍(lán)海人 - 博客園? ?有鏈表的內(nèi)存申請和銷毀講解
鏈表基礎(chǔ)知識總結(jié)_u012531536的專欄-CSDN博客_鏈表
環(huán)形鏈表專題_渣渣-CSDN博客_環(huán)形鏈表? ? 鏈表帶環(huán)的判斷
數(shù)組和鏈表的區(qū)別_博可睿的博客-CSDN博客_數(shù)組和鏈表的區(qū)別? ?數(shù)組和鏈表的區(qū)別 ?? ?????
