鏈表是一種數(shù)據(jù)結(jié)構(gòu)，和數(shù)組同級。比如，Java中我們使用的ArrayList，其實現(xiàn)原理是數(shù)組。而LinkedList的實現(xiàn)原理就是鏈表了。鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點（鏈表中每一個元素稱為結(jié)點）組成，結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域。
鏈表在進行循環(huán)遍歷時效率不高，但是插入和刪除時優(yōu)勢明顯。與之相對應(yīng)的概念是線性表和順序表，線性表是n個數(shù)據(jù)元素的有限序列，數(shù)據(jù)之間存在順序關(guān)系，一般同一個線性表屬于同一類數(shù)據(jù)對象（例如A~Z的字母表）。線性表存在唯一一個首位元素和末位元素，除了第一個元素和最后一個元素，每個元素存在著一個前驅(qū)和一個后繼（A的后繼是B，B的前驅(qū)是A）。線性表主要有順序表和鏈表兩種存儲形式，線性表是一種邏輯結(jié)構(gòu)，順序表和鏈表是物理存儲結(jié)構(gòu)。
線性表是邏輯概念，只要所有的數(shù)據(jù)在邏輯上是一維的都可以認為是線性表。線性表包括順序表（棧，隊列等），鏈表（棧，隊列等）。跟線性表相對的概念應(yīng)該是樹或者堆。順序表是空間概念，指的是所有的數(shù)據(jù)在存儲空間上順序排列，而跟具體的操作方式無關(guān)。順序表是線性表的順序表示，用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，數(shù)組即是最簡單的順序表。與順序表相對的概念只有鏈表。
相比于線性表順序結(jié)構(gòu)，操作復(fù)雜。由于不必須按順序存儲，鏈表在插入的時候可以達到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O(n)的時間，而順序表相應(yīng)的時間復(fù)雜度是O(1)。
詳細代碼請參考Algorithm。參考代碼比文字好理解。
使用鏈表結(jié)構(gòu)可以克服數(shù)組需要預(yù)先知道數(shù)據(jù)大小的缺點，鏈表結(jié)構(gòu)可以充分利用計算機內(nèi)存空間，實現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈表失去了數(shù)組隨機讀取的優(yōu)點，同時鏈表由于增加了結(jié)點的指針域，空間開銷比較大。常規(guī)數(shù)組排列關(guān)聯(lián)項目的方式可能不同于這些數(shù)據(jù)項目在記憶體或磁盤上順序，數(shù)據(jù)的存取往往要在不同的排列順序中轉(zhuǎn)換。鏈表允許插入和移除表上任意位置上的節(jié)點，但是不允許隨機存取。鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環(huán)鏈表。
總結(jié)來說，相比較普通的線性結(jié)構(gòu)，鏈表結(jié)構(gòu)的優(yōu)勢是單個節(jié)點創(chuàng)建非常方便，普通的線性內(nèi)存通常在創(chuàng)建的時候就需要設(shè)定數(shù)據(jù)的大??；節(jié)點的刪除非常方便，不需要像線性結(jié)構(gòu)那樣移動剩下的數(shù)據(jù)；節(jié)點的訪問方便，可以通過循環(huán)或者遞歸的方法訪問到任意數(shù)據(jù)，但是平均的訪問效率低于順序表。
單向鏈表(Singly linked lis)
單向鏈表是最簡單的鏈表形式。我們將鏈表中最基本的數(shù)據(jù)稱為節(jié)點(node)，每一個節(jié)點包含了數(shù)據(jù)塊和指向下一個節(jié)點的指針。
單向鏈表有時候也分為有頭結(jié)點和無頭結(jié)點。有頭結(jié)點的鏈表實現(xiàn)比較方便(每次插入新元素的時候，不需要每次判斷第一個節(jié)點是否為空)，并且可以直接在頭結(jié)點的數(shù)據(jù)塊部分存儲鏈表的長度，而不用每次都遍歷整個鏈表。
在單向鏈表中插入一個新的元素有兩種方式：后插和前插。后插就是每次在鏈表的末尾插入新元素，前插就是在鏈表的頭插入新元素。后插法比較符合平常的思維方式，并且保證插入數(shù)據(jù)的先后順序。但是由于只保存了頭結(jié)點，所以每次插入新元素必須重新遍歷到鏈表末尾。為了解決這個問題，考慮增加一個尾指針，指向鏈表的最后一個節(jié)點。由于單向鏈表只存儲了頭指針，所以刪除單向鏈表中的元素時，需要找到目標節(jié)點的前驅(qū)節(jié)點。鏈表里面的內(nèi)存是手動分配的，當不再使用這些內(nèi)存時需要手動刪除。
雙向鏈表(Doubly linked list)
雙向鏈表就是有兩個方向的鏈表。同單向鏈表不同，在雙向鏈表中每一個節(jié)點不僅存儲指向下一個節(jié)點的指針，而且存儲指向前一個節(jié)點的指針。通過這種方式，能夠通過在O(1)時間內(nèi)通過目的節(jié)點直接找到前驅(qū)節(jié)點，但是同時會增加大量的指針存儲空間。
在雙向鏈表中插入新元素的操作跟在單向鏈表中插入新元素的操作類似。由于雙向鏈表中每個節(jié)點記錄了它的前驅(qū)結(jié)點，所以不需要像單向鏈表中一樣索引目標節(jié)點的前驅(qū)節(jié)點，而是可以通過目標節(jié)點直接獲得。在雙向鏈表中，第一個節(jié)點的前驅(qū)節(jié)點不是頭結(jié)點，而是指向一個空指針。同樣的，最后一個節(jié)點的后驅(qū)指向了一個空指針。
循環(huán)鏈表(Circular Linked list)
循環(huán)鏈表與雙向鏈表相似，不同的地方在于：在鏈表的尾部增加一個指向頭結(jié)點的指針，頭結(jié)點也增加一個指向尾節(jié)點的指針，以及第一個節(jié)點指向頭節(jié)點的指針，從而更方便索引鏈表元素。
線索二叉樹
二叉樹的遍歷本質(zhì)上是將一個復(fù)雜的非線性結(jié)構(gòu)轉(zhuǎn)換為線性結(jié)構(gòu)，使每個結(jié)點都有了唯一前驅(qū)和后繼（第一個結(jié)點無前驅(qū)，最后一個結(jié)點無后繼）。對于二叉樹的一個結(jié)點，查找其左右子女是方便的，其前驅(qū)后繼只有在遍歷中得到。為了容易找到前驅(qū)和后繼，有兩種方法。一是在結(jié)點結(jié)構(gòu)中增加向前和向后的指針fwd和bkd，這種方法增加了存儲開銷，不可??；二是利用二叉樹的空鏈指針。
線索二叉樹是對二叉鏈表中空指針的充分利用，線索二叉樹是一種物理結(jié)構(gòu)。以這種結(jié)點結(jié)構(gòu)構(gòu)成的二叉線索鏈表，鏈表作為二叉樹的存儲結(jié)構(gòu)，其中指向結(jié)點前驅(qū)和后繼的指針叫做線索，加上線索的二叉樹稱為線索二叉樹。利用二叉鏈表中的空指針域，存放指向結(jié)點在某種遍歷次序下的前驅(qū)和后繼結(jié)點的指針（這種附加的指針稱為"線索"）。使得原本是空指針的轉(zhuǎn)化成在某種遍歷的順序下，指向該結(jié)點的前驅(qū)和后繼。
在二叉鏈表中，每個結(jié)點都帶有leftChild和rightChild兩個指針，線索二叉樹在二叉鏈表的基礎(chǔ)上增加了兩個成員數(shù)據(jù)：leftTag、rightTag，用來標記當前結(jié)點的leftChild，rightChild指針指向的是孩子，還是線索。leftTag=rightTag=1,表示線索，leftTag=rightTag=0;表示孩子。
對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做線索化。根據(jù)線索性質(zhì)的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。若對二叉樹進行中序遍歷，則所得的線索二叉樹稱為中序線索二叉樹，線索鏈表稱為中序線索鏈表。
建立線索二叉樹，或者說對二叉樹線索化，實質(zhì)上就是遍歷一棵二叉樹。在遍歷過程中，訪問結(jié)點的操作是檢查當前的左，右指針域是否為空，將它們改為指向前驅(qū)結(jié)點或后續(xù)結(jié)點的線索。在對一顆二叉樹加線索時，必須首先申請一個頭結(jié)點，建立頭結(jié)點與二叉樹的根結(jié)點的指向關(guān)系，對二叉樹線索化后，還需建立最后一個結(jié)點與頭結(jié)點之間的線索。
在中序線索樹找結(jié)點后繼的規(guī)律是：若其右標志為1，則右鏈為線索，指示其后繼，否則遍歷其右子樹時訪問的第一個結(jié)點（右子樹最左下的結(jié)點）為其后繼；找結(jié)點前驅(qū)的規(guī)律是：若其左標志為1，則左鏈為線索，指示其前驅(qū)，否則遍歷左子樹時最后訪問的一個結(jié)點（左子樹中最右下的結(jié)點）為其前驅(qū)。
在后序線索樹中找到結(jié)點的后繼分三種情況：
若結(jié)點是二叉樹的根，則其后繼為空；若結(jié)點是其雙親的右孩子，或是其雙親的左孩子且其雙親沒有右子樹，則其后繼即為雙親結(jié)點；若結(jié)點是其雙親的左孩子，且其雙親有右子樹，則其后繼為雙親右子樹上按后序遍歷列出的第一個結(jié)點。
詳細代碼請參考Algorithm。參考代碼比文字好理解。
