什么是鏈表粟誓？
鏈表是一種線性表枷邪，但并不會按線性的順序存儲數(shù)據(jù)隙畜，而是在每一個(gè)節(jié)點(diǎn)里存儲到下一個(gè)節(jié)點(diǎn)的指針 (Pointer)抖部。因此它不需要分配連續(xù)的存儲空間，也不需要預(yù)先固定元素的大小议惰，它可以動(dòng)態(tài)的添加和刪除元素慎颗，而且時(shí)間復(fù)雜度是 O(1)。只不過查找某個(gè)元素時(shí)言询，時(shí)間復(fù)雜度是 O(n)俯萎。
鏈表有多種不同的類型：單向鏈表，雙向鏈表和循環(huán)鏈表运杭。
單向鏈表
單向鏈表是最簡單的一種夫啊，它包含兩個(gè)域，一個(gè)信息域和一個(gè)指針域辆憔。這個(gè)指針域指向列表中的下一個(gè)節(jié)點(diǎn)撇眯，而最后一個(gè)節(jié)點(diǎn)則指向一個(gè)空值。
雙向鏈表
雙向鏈表中不僅有指向后一個(gè)節(jié)點(diǎn)的指針躁愿，還有指向前一個(gè)節(jié)點(diǎn)的指針叛本。這樣可以從任何一個(gè)節(jié)點(diǎn)訪問前一個(gè)節(jié)點(diǎn)沪蓬，當(dāng)然也可以訪問后一個(gè)節(jié)點(diǎn)彤钟。
循環(huán)鏈表
循環(huán)鏈表是把鏈表的首節(jié)點(diǎn)和末節(jié)點(diǎn)連接在一起，形成一個(gè)環(huán)跷叉。這種方式在單向和雙向鏈表中皆可實(shí)現(xiàn)逸雹。
鏈表有什么作用？
根據(jù)鏈表的特性云挟，動(dòng)態(tài)的把元素加入到鏈表中梆砸，不需要預(yù)先指定鏈表長度，理論上鏈表可以無限長园欣，直到內(nèi)存耗盡帖世。鏈表會存儲下一個(gè)元素的地址，因此插入和刪除會很方便沸枯，但查詢指定元素時(shí)日矫，最壞的情況是遍歷整個(gè)鏈表。
鏈表該怎么使用绑榴？
這里我用 Java 語言來簡單實(shí)現(xiàn)鏈表哪轿，可參考 JDK 的 LinkedList。
構(gòu)建鏈表結(jié)構(gòu)
//創(chuàng)建一個(gè)私有的靜態(tài)的Node泛型對象
public class LinkedList<E> {
Node<E> first;//第一個(gè)節(jié)點(diǎn)
Node<E> last;//最后一個(gè)節(jié)點(diǎn)
private static class Node<E> {
E item;//存儲元素
Node<E> next;//下一個(gè)元素
Node<E> prev;//上一個(gè)元素
//通過構(gòu)造器設(shè)置值
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
在鏈表后插入元素翔怎，前面插入也類似
//中間變量存儲鏈表的最后一個(gè)節(jié)點(diǎn)
Node<E> l = last;
//構(gòu)建新節(jié)點(diǎn)窃诉，頭節(jié)點(diǎn)指向鏈表的最后節(jié)點(diǎn)
Node<E> newNode = new Node<>(l, 5, null);
//把新節(jié)點(diǎn)當(dāng)作最后一個(gè)節(jié)點(diǎn)
last = newNode;
//if 最后節(jié)點(diǎn)為空杨耙，說明是一個(gè)新鏈表
if (l == null)
first = newNode;
//否則把鏈表最后一個(gè)節(jié)點(diǎn)的 next 節(jié)點(diǎn)指向新節(jié)點(diǎn)
else
l.next = newNode;
刪除指定節(jié)點(diǎn) d
E element = d.item;
Node<E> next = d.next;
Node<E> prev = d.prev;
//if 當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)為空，
//說明刪除的是第一個(gè)節(jié)點(diǎn)飘痛，
//把當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)置為第一個(gè)節(jié)點(diǎn)珊膜。
if (prev == null) {
first = next;
//否則把上一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，
//相當(dāng)于跳過了當(dāng)前節(jié)點(diǎn)宣脉，并把當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)置空辅搬。
} else {
prev.next = next;
d.prev = null;
}
//if 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為空，說明是最后一個(gè)節(jié)點(diǎn)脖旱。
//把最后一個(gè)節(jié)點(diǎn)置為上一個(gè)節(jié)點(diǎn)堪遂。
if (next == null) {
last = prev;
//否則把當(dāng)前的上一節(jié)點(diǎn)指向當(dāng)前的下一個(gè)節(jié)點(diǎn)，
//相當(dāng)于跳過當(dāng)前節(jié)點(diǎn)萌庆，在把當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)置空溶褪。
} else {
next.prev = prev;
d.next = null;
}
//置空當(dāng)前節(jié)點(diǎn)元素，幫助 GC 回收
d.item = null;
遍歷鏈表
Node<E> d = first;
while (d != null && d.next != null) {
System.out.println(d.item);
d = d.next;
}
總結(jié)
數(shù)組需要初始化確定好長度践险，并且不能修改數(shù)組的長度猿妈。在有的場景下，是不知道有多少元素的巍虫，因此我們是不能準(zhǔn)確的分配數(shù)組的長度彭则。但也提供了數(shù)組擴(kuò)容的方案，就是在現(xiàn)有的數(shù)組大小上占遥，在按一定算法來創(chuàng)建一個(gè)新的數(shù)組俯抖，并把數(shù)組的數(shù)據(jù)拷貝進(jìn)擴(kuò)容后的數(shù)組里去，但數(shù)組的擴(kuò)容是很影響性能的瓦胎。因此需要一種新的數(shù)據(jù)結(jié)構(gòu)來存儲不能確定有多少元素的數(shù)據(jù)芬萍，這就是鏈表的應(yīng)用場景。
但它也有缺點(diǎn)搔啊，每個(gè)節(jié)點(diǎn)多需要多的空間來存儲下一個(gè)節(jié)點(diǎn)的地址柬祠，查詢時(shí)最壞情況是遍歷整個(gè)數(shù)組。
它的優(yōu)點(diǎn)是不需要預(yù)分配固定大小负芋，不限制元素個(gè)數(shù)漫蛔，理論上可以直到內(nèi)存耗盡，插入和刪除時(shí)間復(fù)雜度是 O(1)旧蛾。
