鏈表
概念
說到鏈表，coder們都不會陌生修赞，在日常開發(fā)中或多或少都會用到它婶恼。
它是鏈?zhǔn)酱鎯Φ木€性表，簡稱鏈表。鏈表由多個(gè)鏈表元素組成勾邦，這些元素稱為節(jié)點(diǎn)蚣录。結(jié)點(diǎn)之間通過邏輯連接，形成鏈?zhǔn)酱鎯Y(jié)構(gòu)眷篇。存儲結(jié)點(diǎn)的內(nèi)存單元萎河，可以是連續(xù)的也可以是不連續(xù)的。邏輯連接與物理存儲次序沒有關(guān)系铅歼。
還是多說說概念上的東西公壤，來說說鏈表的分類，從內(nèi)存角度出發(fā)：鏈表可以分為靜態(tài)鏈表和動態(tài)鏈表椎椰，從鏈表存儲方式的角度出發(fā)：鏈表可以分為單鏈表厦幅，雙鏈表以及循環(huán)鏈表。
- 靜態(tài)鏈表:把線性表的元素放在數(shù)組中慨飘，不管物理上是不是連續(xù)存放的确憨，它們之間的邏輯關(guān)系來連接，數(shù)組單位存放鏈表結(jié)點(diǎn)瓤的，結(jié)點(diǎn)的鏈域指向下一個(gè)元素的位置休弃，也就是下一個(gè)元素所在的數(shù)組單元的下標(biāo)。既然需要數(shù)組來實(shí)現(xiàn)圈膏，那么數(shù)組的長度是不能預(yù)支的塔猾。
- 動態(tài)鏈表：克服了靜態(tài)鏈表的缺點(diǎn)。它動態(tài)地為節(jié)點(diǎn)分配存儲單元稽坤。當(dāng)有節(jié)點(diǎn)插入時(shí)丈甸，系統(tǒng)動態(tài)地為結(jié)點(diǎn)分配空間。在結(jié)點(diǎn)刪除時(shí)尿褪，應(yīng)該及時(shí)釋放相應(yīng)存儲單元睦擂，以防止內(nèi)存泄露。
-
單鏈表： 單鏈表是一種順序存儲的結(jié)構(gòu)杖玲。
有一個(gè)頭結(jié)點(diǎn)顿仇，沒有值域，只有連域摆马，專門存放第一個(gè)結(jié)點(diǎn)的地址臼闻。
有一個(gè)尾結(jié)點(diǎn)，有值域囤采，也有鏈域述呐，鏈域始終為NULL.
所以，在單鏈表中為找第i個(gè)結(jié)點(diǎn)或數(shù)據(jù)元素斑唬，必須先找到第i-1結(jié)點(diǎn)或數(shù)據(jù)元素，而且必須知道頭結(jié)點(diǎn)，否則整個(gè)鏈表無法訪問恕刘。
-
雙鏈表
雙鏈表也是基于單鏈表的缤谎，單鏈表是單向的。而雙鏈表則在單鏈表的基礎(chǔ)上添加了一個(gè)鏈域褐着。通過兩個(gè)鏈域坷澡，分別指向結(jié)點(diǎn)的前結(jié)點(diǎn)和后結(jié)點(diǎn)。這樣的話可以通過雙鏈表的任何結(jié)點(diǎn)訪問到它的前結(jié)點(diǎn)和后結(jié)點(diǎn)含蓉。但是雙鏈表還是不夠靈活频敛，在實(shí)際編程中比較常用的是循環(huán)雙鏈表，但是循環(huán)雙鏈表比較麻煩馅扣。
-
循環(huán)鏈接表
循環(huán)鏈表由單鏈表演化而來斟赚。單鏈表的最后一個(gè)結(jié)點(diǎn)的鏈域指向NULL，而循環(huán)鏈表的建立差油，不要專門的頭結(jié)點(diǎn)拗军，讓最后一個(gè)結(jié)點(diǎn)的鏈域指向鏈表結(jié)點(diǎn)。它與單鏈表的區(qū)別：
區(qū)別一：鏈表的建立蓄喇。單鏈表需要創(chuàng)建一個(gè)頭結(jié)點(diǎn)发侵，專門存放第一個(gè)結(jié)點(diǎn)的地址。單鏈表的鏈域指向NULL妆偏。而循環(huán)鏈表的建立刃鳄，不要專門的頭結(jié)點(diǎn)，讓最后一個(gè)結(jié)點(diǎn)的鏈域指向鏈表的頭結(jié)點(diǎn)钱骂。
區(qū)別二：鏈表表尾的判斷叔锐。單鏈表判斷結(jié)點(diǎn)是否為表尾結(jié)點(diǎn)，只需判斷結(jié)點(diǎn)的鏈域值是否是NULL罐柳。如果是掌腰，則為尾結(jié)點(diǎn)；否則不是张吉。而循環(huán)鏈表盤判斷是否為尾結(jié)點(diǎn)齿梁，則是判斷該節(jié)點(diǎn)的鏈域是不是指向鏈表的頭結(jié)點(diǎn)。
鏈表的實(shí)現(xiàn)
單鏈表(Single-Linked List)
public class SingleLinkedList<E> {
transient int size = 0;
private Node<E> first;
private class Node<E> {
E item;
Node<E> next;
}
}
插入節(jié)點(diǎn)
由于我們SIngleLinkedList類中維護(hù)了一個(gè)指向FirstNode的引用肮蛹，所以在表頭插入節(jié)點(diǎn)是很容易的勺择。
public void insert(E item) {
Node<E> oldFirst = first;
first = new Node<>();
first.item = item;
first.next = oldFirst;
size++;
}
刪除節(jié)點(diǎn)
/**
* 從頭結(jié)點(diǎn)開始刪除
* @return
*/
public E delete() {
if (first != null) {
E item=first.item;
//讓頭結(jié)點(diǎn)變成原來頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
first=first.next;
return item;
} else {
throw new NullPointerException("This SingleLinkedList is empty!");
}
}
雙向鏈表(DoubleLinkedList)
雙向鏈表相比與單鏈表的優(yōu)勢在于它同時(shí)支持高效的正向及反向遍歷，并且可以方便的在鏈表尾部刪除結(jié)點(diǎn)（單鏈表可以方便的在尾部插入結(jié)點(diǎn)伦忠，但不支持高效的表尾刪除操作）省核。
public class DoubleLinkedList<E> {
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
添加節(jié)點(diǎn)
public void addFirst(E e) {
Node<E> f = first;
Node<E> newNode = new Node<E>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
}
public void addLast(E e) {
Node<E> l = last;
Node<E> newNode = new Node<E>(l, e, null);
last = newNode;
if(l==null){
first=newNode;
}else{
l.next=newNode;
}
size++;
}
在指定位置之前添加節(jié)點(diǎn):
public void add(int index, E element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("index is illegal");
}
if (index == size) {
addLast(element);
}
addBefore(element, node(index));
}
private void addBefore(E element, Node<E> node) {
Node<E> prev = node.prev;
Node<E> newNode = new Node<E>(prev, element, node);
node.prev = newNode;
if (prev == null)
first = newNode;
else
prev.next = newNode;
size++;
}
private Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i++)
x = x.prev;
return x;
}
}
刪除操作
private E deleteFirst(Node<E> f) {//刪除第一個(gè)
E element = f.item;
Node<E> next = f.next;
f.item = null;
f.next = null;
first = next;
if (next == null) {
last = null;
} else {
next.prev = null;
}
size--;
return element;
}
private E deleteLast(Node<E> node) {//刪除最后一個(gè)
E element = node.item;
Node<E> prev = node.prev;
node.item = null;
node.prev = null;
if (prev == null)
first = null;
else
prev.next = null;
size--;
return element;
}
E delete(Node<E> x) {//刪除指定的Node
E element = x.item;
Node<E> next = x.next;
Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev=prev;
x.next=null;
}
x.item=null;
size--;
return element;
}
它們使用的地方
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
delete(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
delete(x);
return true;
}
}
}
return false;
}
直接看代碼就知道所謂鏈表到底是怎么一回事了。
鏈表的特性
1 優(yōu)點(diǎn)
鏈表的主要優(yōu)勢有兩點(diǎn)：1昆码，插入的時(shí)間復(fù)雜度為o(1);2气忠，可以動態(tài)的改變大小邻储。
2 缺點(diǎn)
由于其鏈?zhǔn)酱鎯Φ奶匦裕湵聿痪邆淞己玫目臻g局部性旧噪，也就是說吨娜，鏈表是一種緩存不友好的數(shù)據(jù)結(jié)構(gòu)。
LinkedList
java 中LinkedList中的源碼中添加刪除方法如我在上面寫的雙鏈表中的添加刪除方法基本一致淘钟。
LinkedList是基于雙向循環(huán)鏈表實(shí)現(xiàn)的(last.next=first,first.prev=last)宦赠。
LinkedList是非線程安全的，只在單線程下適合使用米母。
LinkedList實(shí)現(xiàn)了Serializable接口勾扭，因此它支持序列化，能夠通過序列化傳輸铁瞒，實(shí)現(xiàn)了Cloneable接口妙色，能被克隆。
除了可以當(dāng)作鏈表來操作外精拟，它還可以當(dāng)作棧燎斩，隊(duì)列和雙端隊(duì)列來使用。
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public boolean offer(E e) {
return add(e);
}
public void push(E e) {
addFirst(e);
}
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E pop() {
return removeFirst();
}
....
從源碼可以看出LinkedList不僅有鏈表的特征方法還是棧和隊(duì)列的特性方法蜂绎。
對于LinkedList還有幾點(diǎn)要說的栅表。
* 在查找和刪除某元素時(shí)，源碼中都劃分為該元素為null和不為null兩種情況來處理师枣，LinkedList中允許元素為null怪瓶。
* LinkedList是基于鏈表實(shí)現(xiàn)的，因此不存在容量不足的問題践美，所以這里沒有擴(kuò)容的方法洗贰。
* 注意源碼中的Entry entry(int index)方法。該方法返回雙向鏈表中指定位置處的節(jié)點(diǎn)陨倡，而鏈表中是沒有下標(biāo)索引的敛滋，要指定位置出的元素，就要遍歷該鏈表兴革，從源碼的實(shí)現(xiàn)中绎晃，我們看到這里有一個(gè)加速動作。源碼中先將index與長度size的一半比較杂曲，如果indexsize/2庶艾，就只從位置size往前遍歷到位置index處。這樣可以減少一部分不必要的遍歷擎勘，從而提高一定的效率（實(shí)際上效率還是很低）咱揍。
* LinkedList是基于鏈表實(shí)現(xiàn)的，因此插入刪除效率高棚饵，查找效率低（雖然有一個(gè)加速動作）煤裙。
* 要注意源碼中還實(shí)現(xiàn)了棧和隊(duì)列的操作方法掩完，因此也可以作為棧、隊(duì)列和雙端隊(duì)列來使用硼砰。
## 一道鏈表的測試題
這道題來自[劍指offer](https://www.nowcoder.com/ta/coding-interviews?page=)上的一道題：
在一個(gè)排序的鏈表中藤为，存在重復(fù)的結(jié)點(diǎn)，請刪除該鏈表中重復(fù)的結(jié)點(diǎn)夺刑，重復(fù)的結(jié)點(diǎn)不保留，返回鏈表頭指針分别。 例如遍愿，鏈表1->2->3->3->4->4->5 處理后為 1->2->5
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public class Solution {
public ListNode deleteDuplication(ListNode pHead)
{
int maxNum = 0;
//int minNum = pHead.val;
//int length = 0;
for (ListNode x = pHead; x != null; x = x.next) {
// length++;
if (x.val > maxNum) {
maxNum = x.val;
}
}
int[] nums = new int[maxNum + 1];
for (ListNode x = pHead; x != null; x = x.next) {
nums[x.val]++;
}
ListNode first = null;
ListNode pFirst=null;
for (int index = 0; index <= maxNum; index++) {
if (nums[index] > 1) {
nums[index] = 0;
}
if (nums[index] > 0 && index > ( first==null?-1:first.val)) {
if (first != null) {
ListNode oldFirst = first;
first = new ListNode(index);
// first.val=index;
oldFirst.next = first;
} else {
first = new ListNode(index);
pFirst = first;
}
}
}
return pFirst;
}
}
這是我寫出的一種答案，可能有待精簡和優(yōu)化耘斩，時(shí)間關(guān)系就在這里提供一種解法沼填。等有時(shí)間加上注釋。