????上文分析了單向鏈表萧求，單向鏈表的實(shí)現(xiàn)很簡單腕巡，但是他的局限性也很明顯：因?yàn)槊總€節(jié)點(diǎn)只能找到他的下線節(jié)點(diǎn)，找不到他的上線節(jié)點(diǎn)嫩挤，所以遍歷的時(shí)候害幅，只能從頭節(jié)點(diǎn)開始遍歷，沒辦法從任意位置開始遍歷岂昭，但是雙向鏈表可以做到從任意位置開始遍歷．
????與單向鏈表相比以现，雙向鏈表的節(jié)點(diǎn)除了數(shù)據(jù)data，下線節(jié)點(diǎn)next這兩個基本屬性外约啊，還增加了一個上線節(jié)點(diǎn)prev邑遏，因?yàn)槊總€節(jié)點(diǎn)保存了上線節(jié)點(diǎn)和下線節(jié)點(diǎn)(比較專業(yè)的說法是前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn))，所以拿到任意一個節(jié)點(diǎn)恰矩，都能夠遍歷整個鏈表记盒，這是單向鏈表所不具備的特性．
double.png
????另外還有一種循環(huán)雙向鏈表，就是頭節(jié)點(diǎn)的prev指向尾節(jié)點(diǎn)外傅，尾節(jié)點(diǎn)的next指向頭節(jié)點(diǎn)．
????來看一個關(guān)于雙向鏈表的Demo：
public class DoubleLinked {
/**
* 頭節(jié)點(diǎn)
*/
private Node head;
/**
* 尾節(jié)點(diǎn)
*/
private Node tail;
public static void main(String[] args) {
}
/**
* 打印鏈表
*/
private void showDoubleLinked() {
String str = "";
if(length == 0) {
System.out.println("鏈表為空");
}else {
Node tmp = head;
str += tmp;
while(tmp.next != null) {
str += "<--->" + tmp.next;
tmp = tmp.next;
}
System.out.println(str);
}
}
}
/**
* 節(jié)點(diǎn)類纪吮，成員屬性就不設(shè)為private了俩檬，省去get,set方法
* @author tushihao
*
*/
class Node{
/**
* 節(jié)點(diǎn)數(shù)據(jù)
*/
Object o;
/**
* 前驅(qū)節(jié)點(diǎn)
*/
Node prev;
/**
* 后繼節(jié)點(diǎn)
*/
Node next;
public Node(Object o) {
this.o = o;
}
@Override
public String toString() {
return "Node[" + o + "]";
}
}
????1.增加節(jié)點(diǎn)：
/**
* 將指定的節(jié)點(diǎn)添加進(jìn)雙向鏈表指定的位置(返回值視需求而定，這里不返回?cái)?shù)據(jù))
* @param node 待添加的節(jié)點(diǎn)
* @param index 待添加的節(jié)點(diǎn)要插入的位置碾盟，0代表插到頭棚辽，-1代表插到尾，其他大于0的值就插入到指定位置
*/
private void addNode(Node node , int index) {
//空節(jié)點(diǎn)或者數(shù)據(jù)為空的節(jié)點(diǎn)不允許插入(視需求而定)
if(node == null || node.o == null || index < -1 || index > length) {
return;
}
Node tmp = head;
//如果鏈表為空巷疼，那么目標(biāo)節(jié)點(diǎn)就是頭節(jié)點(diǎn)晚胡，同時(shí)也是尾節(jié)點(diǎn)
if(length == 0) {
head = node;
tail = node;
length++;
return;
}
if(index == 0) {
//如果插入頭節(jié)點(diǎn)，只需要把原來的頭結(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)指向目標(biāo)節(jié)點(diǎn)
//后繼節(jié)點(diǎn)不動嚼沿，同時(shí)將目標(biāo)節(jié)點(diǎn)賦值給頭結(jié)點(diǎn)head估盘，目標(biāo)節(jié)點(diǎn)的后
//繼節(jié)點(diǎn)賦值指向原來的頭節(jié)點(diǎn)
tmp.prev = node;
node.next = tmp;
head = node;
}else if(index == -1 || index == length){
//插入尾節(jié)點(diǎn)的話，只需要將原來尾節(jié)點(diǎn)的后繼結(jié)點(diǎn)指向目標(biāo)節(jié)點(diǎn)骡尽，
//前驅(qū)節(jié)點(diǎn)不動遣妥，同時(shí)將目標(biāo)節(jié)點(diǎn)賦值給尾節(jié)點(diǎn)tail，將目標(biāo)節(jié)點(diǎn)
//的前驅(qū)節(jié)點(diǎn)賦值給原來的尾節(jié)點(diǎn)
tmp = tail;
tmp.next = node;
tail = node;
tail.prev = tmp;
}else {
int len = 0;
//插入任意位置攀细，首先判斷目標(biāo)索引位于鏈表的前半部分還是后半部分箫踩，如果是
//前半部分，那么從頭開始插谭贪；如果是后半部分境钟，那么從尾開始插
if(index < length/2){
while(tmp.next != null) {
len++;
if(len == index + 1 ) {
//首先將遍歷到的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向目標(biāo)節(jié)點(diǎn)
tmp.prev.next = node;
//然后將目標(biāo)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)指向遍歷到的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
node.prev = tmp.prev;
//接著將目標(biāo)節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向遍歷到的節(jié)點(diǎn)
node.next = tmp;
//最后將遍歷到的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)執(zhí)行目標(biāo)節(jié)點(diǎn)
tmp.prev = node;
break;
}else {
tmp = tmp.next;
}
}
}else {
tmp = tail;
len = length;
while(tmp.prev != null) {
len--;
if(index == len) {
//首先將遍歷到的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向目標(biāo)節(jié)點(diǎn)
tmp.prev.next = node;
//然后將目標(biāo)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)指向遍歷到的節(jié)點(diǎn)前驅(qū)節(jié)點(diǎn)
node.prev = tmp.prev;
//接著將目標(biāo)節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向遍歷到的節(jié)點(diǎn)
node.next = tmp;
//最后將遍歷到的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)指向目標(biāo)節(jié)點(diǎn)
tmp.prev = node;
}else {
tmp = tmp.prev;
}
}
}
}
length++;
}
????測試代碼：
DoubleLinked dl = new DoubleLinked();
dl.addNode(new Node("E"), 0);
dl.addNode(new Node("D"), 0);
dl.addNode(new Node("C"), 0);
dl.addNode(new Node("B"), 0);
dl.addNode(new Node("A"), 0);
System.out.println("鏈表長度：" + dl.length + "罚舱，鏈表內(nèi)容：");
dl.showDoubleLinked();
System.out.println("將tuhao插入頭結(jié)點(diǎn)");
dl.addNode(new Node("tuhao"), 0);
System.out.println("鏈表長度：" + dl.length + "遏餐，鏈表內(nèi)容：");
dl.showDoubleLinked();
System.out.println("將dana插入尾結(jié)點(diǎn)");
dl.addNode(new Node("dana"), -1);
System.out.println("鏈表長度：" + dl.length + "，鏈表內(nèi)容：");
dl.showDoubleLinked();
System.out.println("將topwise插入第三個結(jié)點(diǎn)");
dl.addNode(new Node("topwise"), 2);
System.out.println("鏈表長度：" + dl.length + "嫂沉，鏈表內(nèi)容：");
dl.showDoubleLinked();
????測試結(jié)果：
鏈表長度：5套媚，鏈表內(nèi)容：
Node[A]<--->Node[B]<--->Node[C]<--->Node[D]<--->Node[E]
將tuhao插入頭結(jié)點(diǎn)
鏈表長度：6缚态，鏈表內(nèi)容：
Node[tuhao]<--->Node[A]<--->Node[B]<--->Node[C]<--->Node[D]<--->Node[E]
將dana插入尾結(jié)點(diǎn)
鏈表長度：7，鏈表內(nèi)容：
Node[tuhao]<--->Node[A]<--->Node[B]<--->Node[C]<--->Node[D]<--->Node[E]<--->Node[dana]
將topwise插入第三個結(jié)點(diǎn)
鏈表長度：8堤瘤，鏈表內(nèi)容：
Node[tuhao]<--->Node[A]<--->Node[topwise]<--->Node[B]<--->Node[C]<--->Node[D]<--->Node[E]<--->Node[dana]
????2.刪除節(jié)點(diǎn)：
/**
* 根據(jù)節(jié)點(diǎn)數(shù)據(jù)移除指定的節(jié)點(diǎn)(還可以根據(jù)索引移除目標(biāo)節(jié)點(diǎn)玫芦，比較簡單，不額外寫了)
*
* @param o 要移除的節(jié)點(diǎn)的數(shù)據(jù)
* @return 目標(biāo)節(jié)點(diǎn)的索引,-1表示刪除失敗
*/
public int removeNoe(Object o) {
if(length == 0) {
return -1;
}
Node tmp = head;
Node mPrev = null;
int len = 0;
//判斷節(jié)點(diǎn)內(nèi)容相等是用equals還是==本辐，視需求而定
if(o.equals(head.o)) {
length--;
head = head.next;
return 0;
}else if(o.equals(tail.o)) {
length--;
tail = tail.prev;
tail.next = null;
return length;
}else {
while(tmp.next != null) {
if(o.equals(tmp.o)) {
length--;
mPrev.next = tmp.next;
tmp.next.prev = mPrev;
return len;
}else {
len++;
mPrev = tmp;
tmp = tmp.next;
}
}
}
return -1;
}
????測試代碼：
System.out.println("tuhao太高調(diào)了桥帆，干掉：");
int i = dl.removeNoe("tuhao");
System.out.println("tuhao的索引是：" + i + " , 干掉tuhao后鏈表長度：" + dl.length + "，鏈表內(nèi)容：");
dl.showDoubleLinked();
System.out.println("dana太俗了慎皱，干掉：");
int j = dl.removeNoe("dana");
System.out.println("dana的索引是：" + j + " , 干掉dana后鏈表長度：" + dl.length + "环葵，鏈表內(nèi)容：");
dl.showDoubleLinked();
System.out.println("隱藏公司信息，干掉topwise：");
int k = dl.removeNoe("topwise");
System.out.println("topwise的索引是：" + k + " , 干掉topwise后鏈表長度：" + dl.length + "宝冕，鏈表內(nèi)容：");
dl.showDoubleLinked();
????測試結(jié)果：
tuhao太高調(diào)了张遭，干掉：
tuhao的索引是：0 , 干掉tuhao后鏈表長度：7，鏈表內(nèi)容：
Node[A]<--->Node[topwise]<--->Node[B]<--->Node[C]<--->Node[D]<--->Node[E]<--->Node[dana]
dana太俗了地梨，干掉：
dana的索引是：6 , 干掉dana后鏈表長度：6菊卷，鏈表內(nèi)容：
Node[A]<--->Node[topwise]<--->Node[B]<--->Node[C]<--->Node[D]<--->Node[E]
隱藏公司信息缔恳，干掉topwise：
topwise的索引是：1 , 干掉topwise后鏈表長度：5，鏈表內(nèi)容：
Node[A]<--->Node[B]<--->Node[C]<--->Node[D]<--->Node[E]
????3.查找節(jié)點(diǎn)：
/**
* 根據(jù)內(nèi)容查找目標(biāo)節(jié)點(diǎn)
* @param o 要查找的節(jié)點(diǎn)的內(nèi)容
* @return 目標(biāo)節(jié)點(diǎn)洁闰，查找失敗的話返回null
*/
private Node findNodeByData(Object o) {
if(length == 0 || o == null) {
return null;
}
Node tmp = head;
if(o.equals(head.o)) {
return head;
}else if(o.equals(tail.o)) {
return tail;
}else {
while(tmp.next != null) {
if(o.equals(tmp.o)) {
return tmp;
}else {
tmp = tmp.next;
}
}
}
return null;
}
????測試代碼：
System.out.println("我要A：" + dl.findNodeByData("A"));
System.out.println("我要B：" + dl.findNodeByData("B"));
System.out.println("我要E：" + dl.findNodeByData("E"));
System.out.println("我要qian：" + dl.findNodeByData("qian"));
????測試結(jié)果：
我要A：Node[A]
我要B：Node[B]
我要E：Node[E]
我要qian：null
????上面的Demo應(yīng)該是自從改革開放以來最簡單的雙向鏈表使用的例子歉甚，僅適合入門；下面結(jié)合源碼來分析雙向鏈表在JDK中的運(yùn)用扑眉。
????JAVA中運(yùn)用到雙向鏈表的典型場景是LinkedList纸泄，在JDK1.6之前(包括1.6)，LinkedList中的雙向鏈表是閉環(huán)雙向鏈表腰素，也就是說頭結(jié)點(diǎn)和尾節(jié)點(diǎn)是連著的聘裁；1.6之后，LinkedList中的雙向鏈表改成了開環(huán)雙向鏈表弓千，就是上面的Demo中的那種衡便，頭和尾節(jié)點(diǎn)不連在一起，下面基于JDK1.8粗略分析下LinkList的源碼：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
//LinkedList的長度洋访，transient關(guān)鍵字的意思是LinkedList的長度不參與序列化
transient int size = 0;
//頭節(jié)點(diǎn)镣陕，不參與序列化
transient Node<E> first;
//尾節(jié)點(diǎn)，不參與序列化
transient Node<E> last;
}
......
/**
* Links e as first element.
* 在鏈表頭插入一個節(jié)點(diǎn)
*/
private void linkFirst(E e) {
//將頭結(jié)點(diǎn)賦值給臨時(shí)節(jié)點(diǎn)f
final Node<E> f = first;
//首先創(chuàng)建一個節(jié)點(diǎn)
final Node<E> newNode = new Node<>(null, e, f);
//將新的節(jié)點(diǎn)賦值給頭結(jié)點(diǎn)
first = newNode;
//如果f為空姻政，也就是原來的頭結(jié)點(diǎn)為空呆抑，說明鏈表是空的，插
//入一個節(jié)點(diǎn)后汁展，頭結(jié)點(diǎn)和尾節(jié)點(diǎn)都是新建的節(jié)點(diǎn)newNode
if (f == null)
last = newNode;
else
//如果f不為空鹊碍，那么將原來的頭結(jié)點(diǎn)指向新的頭節(jié)點(diǎn)
//這樣的話，原來的頭結(jié)點(diǎn)就變成了第二個節(jié)點(diǎn)
f.prev = newNode;
//鏈表長度+1
size++;
//modCount自增善镰，modCount這玩意比較重要妹萨，ArrayList,LinkedList,HashMap
//等容器都有這貨年枕；因?yàn)檫@些容器都是線程不安全的炫欺，在迭代器迭代這些容器的時(shí)候，可
//能存在某個線程修改這些容器熏兄，這時(shí)候迭代肯定會出意想不到的結(jié)果品洛；所以在創(chuàng)建迭代
//器的時(shí)候，會傳入這個值摩桶，這個值代表的是容器修改的次數(shù)桥状，如果在迭代的時(shí)候發(fā)現(xiàn)這
//貨被改了，那么就會拋出異常硝清，停止迭代辅斟。modCount的含義就是容器的修改次數(shù)
modCount++;
}
/**
* Links e as last element.
* 在鏈表尾插入一個節(jié)點(diǎn)
*/
void linkLast(E e) {
//原理linkFirst()，不贅述
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
/**
* Inserts element e before non-null Node succ.
* 在指定節(jié)點(diǎn)的前面插入一個節(jié)點(diǎn)
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//首先記錄指定節(jié)點(diǎn)前驅(qū)節(jié)點(diǎn)芦拿，這個前驅(qū)節(jié)點(diǎn)
//的位置就是目標(biāo)節(jié)點(diǎn)要插入的位置
final Node<E> pred = succ.prev;
//根據(jù)傳進(jìn)來的節(jié)點(diǎn)內(nèi)容創(chuàng)建一個新的節(jié)點(diǎn)
final Node<E> newNode = new Node<>(pred, e, succ);
//將指定節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)指向目標(biāo)節(jié)點(diǎn)
succ.prev = newNode;
//如果指定節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)是空士飒，說明指定節(jié)點(diǎn)是頭節(jié)點(diǎn);也就
//是說往頭節(jié)點(diǎn)的前面 插入一個節(jié)點(diǎn)查邢，相當(dāng)于linkFirst方法
if (pred == null)
//重新賦值頭結(jié)點(diǎn)
first = newNode;
else
//如果不是插入鏈表頭，那么將指定節(jié)點(diǎn)的
//前驅(qū)節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向目標(biāo)節(jié)點(diǎn)酵幕，簡單
pred.next = newNode;
//兩個自增在linkFirst方法中分析過
size++;
modCount++;
}
......
/**
* Unlinks non-null node x.
* 刪除指定節(jié)點(diǎn)
*/
E unlink(Node<E> x) {
// assert x != null;
//指定節(jié)點(diǎn)的數(shù)據(jù)
final E element = x.item;
//指定節(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//如果前驅(qū)節(jié)點(diǎn)是空扰藕，說明要刪除的節(jié)點(diǎn)是頭結(jié)點(diǎn)
if (prev == null) {
//頭結(jié)點(diǎn)指向第二個節(jié)點(diǎn)即可
first = next;
} else {
//如果不是刪除頭節(jié)點(diǎn)，那么將指定節(jié)點(diǎn)的前
//驅(qū)節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向指定節(jié)點(diǎn)的后繼節(jié)點(diǎn)
prev.next = next;
//將指定節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)置空
x.prev = null;
}
//如果指定節(jié)點(diǎn)的后繼節(jié)點(diǎn)為空芳撒，說明要刪除為節(jié)點(diǎn)邓深，原理同上
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
/**
* Returns the first element in this list.
* 獲取頭節(jié)點(diǎn)，簡單
* @return the first element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
/**
* Returns the last element in this list.
* 獲取尾節(jié)點(diǎn)笔刹，簡單
* @return the last element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
......
}
????以上就是LinkedList的部分方法的分析芥备，很簡單，更多方法徘熔，以后專題研究LinkedList的時(shí)候再分析.
