上文分析了单向链表，单向链表的实现很简单，但是他的局限性也很明显：因为每个节点只能找到他的下线节点，找不到他的上线节点，所以遍历的时候，只能从头节点开始遍历，没办法从任意位置开始遍历，但是双向链表可以做到从任意位置开始遍历．
与单向链表相比，双向链表的节点除了数据data，下线节点next这两个基本属性外，还增加了一个上线节点prev，因为每个节点保存了上线节点和下线节点(比较专业的说法是前驱节点和后继节点)，所以拿到任意一个节点，都能够遍历整个链表，这是单向链表所不具备的特性．
double.png
另外还有一种循环双向链表，就是头节点的prev指向尾节点，尾节点的next指向头节点．
来看一个关于双向链表的Demo：
public class DoubleLinked {
/**
* 头节点
*/
private Node head;
/**
* 尾节点
*/
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);
}
}
}
/**
* 节点类，成员属性就不设为private了，省去get,set方法
* @author tushihao
*
*/
class Node{
/**
* 节点数据
*/
Object o;
/**
* 前驱节点
*/
Node prev;
/**
* 后继节点
*/
Node next;
public Node(Object o) {
this.o = o;
}
@Override
public String toString() {
return "Node[" + o + "]";
}
}
1.增加节点：
/**
* 将指定的节点添加进双向链表指定的位置(返回值视需求而定，这里不返回数据)
* @param node 待添加的节点
* @param index 待添加的节点要插入的位置，0代表插到头，-1代表插到尾，其他大于0的值就插入到指定位置
*/
private void addNode(Node node , int index) {
//空节点或者数据为空的节点不允许插入(视需求而定)
if(node == null || node.o == null || index < -1 || index > length) {
return;
}
Node tmp = head;
//如果链表为空，那么目标节点就是头节点，同时也是尾节点
if(length == 0) {
head = node;
tail = node;
length++;
return;
}
if(index == 0) {
//如果插入头节点，只需要把原来的头结点的前驱节点指向目标节点
//后继节点不动，同时将目标节点赋值给头结点head，目标节点的后
//继节点赋值指向原来的头节点
tmp.prev = node;
node.next = tmp;
head = node;
}else if(index == -1 || index == length){
//插入尾节点的话，只需要将原来尾节点的后继结点指向目标节点，
//前驱节点不动，同时将目标节点赋值给尾节点tail，将目标节点
//的前驱节点赋值给原来的尾节点
tmp = tail;
tmp.next = node;
tail = node;
tail.prev = tmp;
}else {
int len = 0;
//插入任意位置，首先判断目标索引位于链表的前半部分还是后半部分，如果是
//前半部分，那么从头开始插；如果是后半部分，那么从尾开始插
if(index < length/2){
while(tmp.next != null) {
len++;
if(len == index + 1 ) {
//首先将遍历到的节点的前驱节点的后继节点指向目标节点
tmp.prev.next = node;
//然后将目标节点的前驱节点指向遍历到的节点的前驱节点
node.prev = tmp.prev;
//接着将目标节点的后继节点指向遍历到的节点
node.next = tmp;
//最后将遍历到的节点的前驱节点执行目标节点
tmp.prev = node;
break;
}else {
tmp = tmp.next;
}
}
}else {
tmp = tail;
len = length;
while(tmp.prev != null) {
len--;
if(index == len) {
//首先将遍历到的节点的前驱节点的后继节点指向目标节点
tmp.prev.next = node;
//然后将目标节点的前驱节点指向遍历到的节点前驱节点
node.prev = tmp.prev;
//接着将目标节点的后继节点指向遍历到的节点
node.next = tmp;
//最后将遍历到的节点的前驱节点指向目标节点
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 + "，链表内容：");
dl.showDoubleLinked();
System.out.println("将tuhao插入头结点");
dl.addNode(new Node("tuhao"), 0);
System.out.println("链表长度：" + dl.length + "，链表内容：");
dl.showDoubleLinked();
System.out.println("将dana插入尾结点");
dl.addNode(new Node("dana"), -1);
System.out.println("链表长度：" + dl.length + "，链表内容：");
dl.showDoubleLinked();
System.out.println("将topwise插入第三个结点");
dl.addNode(new Node("topwise"), 2);
System.out.println("链表长度：" + dl.length + "，链表内容：");
dl.showDoubleLinked();
测试结果：
链表长度：5，链表内容：
Node[A]<--->Node[B]<--->Node[C]<--->Node[D]<--->Node[E]
将tuhao插入头结点
链表长度：6，链表内容：
Node[tuhao]<--->Node[A]<--->Node[B]<--->Node[C]<--->Node[D]<--->Node[E]
将dana插入尾结点
链表长度：7，链表内容：
Node[tuhao]<--->Node[A]<--->Node[B]<--->Node[C]<--->Node[D]<--->Node[E]<--->Node[dana]
将topwise插入第三个结点
链表长度：8，链表内容：
Node[tuhao]<--->Node[A]<--->Node[topwise]<--->Node[B]<--->Node[C]<--->Node[D]<--->Node[E]<--->Node[dana]
2.删除节点：
/**
* 根据节点数据移除指定的节点(还可以根据索引移除目标节点，比较简单，不额外写了)
*
* @param o 要移除的节点的数据
* @return 目标节点的索引,-1表示删除失败
*/
public int removeNoe(Object o) {
if(length == 0) {
return -1;
}
Node tmp = head;
Node mPrev = null;
int len = 0;
//判断节点内容相等是用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太高调了，干掉：");
int i = dl.removeNoe("tuhao");
System.out.println("tuhao的索引是：" + i + " , 干掉tuhao后链表长度：" + dl.length + "，链表内容：");
dl.showDoubleLinked();
System.out.println("dana太俗了，干掉：");
int j = dl.removeNoe("dana");
System.out.println("dana的索引是：" + j + " , 干掉dana后链表长度：" + dl.length + "，链表内容：");
dl.showDoubleLinked();
System.out.println("隐藏公司信息，干掉topwise：");
int k = dl.removeNoe("topwise");
System.out.println("topwise的索引是：" + k + " , 干掉topwise后链表长度：" + dl.length + "，链表内容：");
dl.showDoubleLinked();
测试结果：
tuhao太高调了，干掉：
tuhao的索引是：0 , 干掉tuhao后链表长度：7，链表内容：
Node[A]<--->Node[topwise]<--->Node[B]<--->Node[C]<--->Node[D]<--->Node[E]<--->Node[dana]
dana太俗了，干掉：
dana的索引是：6 , 干掉dana后链表长度：6，链表内容：
Node[A]<--->Node[topwise]<--->Node[B]<--->Node[C]<--->Node[D]<--->Node[E]
隐藏公司信息，干掉topwise：
topwise的索引是：1 , 干掉topwise后链表长度：5，链表内容：
Node[A]<--->Node[B]<--->Node[C]<--->Node[D]<--->Node[E]
3.查找节点：
/**
* 根据内容查找目标节点
* @param o 要查找的节点的内容
* @return 目标节点，查找失败的话返回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"));
测试结果：
我要A：Node[A]
我要B：Node[B]
我要E：Node[E]
我要qian：null
上面的Demo应该是自从改革开放以来最简单的双向链表使用的例子，仅适合入门；下面结合源码来分析双向链表在JDK中的运用。
JAVA中运用到双向链表的典型场景是LinkedList，在JDK1.6之前(包括1.6)，LinkedList中的双向链表是闭环双向链表，也就是说头结点和尾节点是连着的；1.6之后，LinkedList中的双向链表改成了开环双向链表，就是上面的Demo中的那种，头和尾节点不连在一起，下面基于JDK1.8粗略分析下LinkList的源码：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
//LinkedList的长度，transient关键字的意思是LinkedList的长度不参与序列化
transient int size = 0;
//头节点，不参与序列化
transient Node<E> first;
//尾节点，不参与序列化
transient Node<E> last;
}
......
/**
* Links e as first element.
* 在链表头插入一个节点
*/
private void linkFirst(E e) {
//将头结点赋值给临时节点f
final Node<E> f = first;
//首先创建一个节点
final Node<E> newNode = new Node<>(null, e, f);
//将新的节点赋值给头结点
first = newNode;
//如果f为空，也就是原来的头结点为空，说明链表是空的，插
//入一个节点后，头结点和尾节点都是新建的节点newNode
if (f == null)
last = newNode;
else
//如果f不为空，那么将原来的头结点指向新的头节点
//这样的话，原来的头结点就变成了第二个节点
f.prev = newNode;
//链表长度+1
size++;
//modCount自增，modCount这玩意比较重要，ArrayList,LinkedList,HashMap
//等容器都有这货；因为这些容器都是线程不安全的，在迭代器迭代这些容器的时候，可
//能存在某个线程修改这些容器，这时候迭代肯定会出意想不到的结果；所以在创建迭代
//器的时候，会传入这个值，这个值代表的是容器修改的次数，如果在迭代的时候发现这
//货被改了，那么就会抛出异常，停止迭代。modCount的含义就是容器的修改次数
modCount++;
}
/**
* Links e as last element.
* 在链表尾插入一个节点
*/
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.
* 在指定节点的前面插入一个节点
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//首先记录指定节点前驱节点，这个前驱节点
//的位置就是目标节点要插入的位置
final Node<E> pred = succ.prev;
//根据传进来的节点内容创建一个新的节点
final Node<E> newNode = new Node<>(pred, e, succ);
//将指定节点的前驱节点指向目标节点
succ.prev = newNode;
//如果指定节点的前驱节点是空，说明指定节点是头节点;也就
//是说往头节点的前面 插入一个节点，相当于linkFirst方法
if (pred == null)
//重新赋值头结点
first = newNode;
else
//如果不是插入链表头，那么将指定节点的
//前驱节点的后继节点指向目标节点，简单
pred.next = newNode;
//两个自增在linkFirst方法中分析过
size++;
modCount++;
}
......
/**
* Unlinks non-null node x.
* 删除指定节点
*/
E unlink(Node<E> x) {
// assert x != null;
//指定节点的数据
final E element = x.item;
//指定节点的前驱和后继节点
final Node<E> next = x.next;
final 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--;
modCount++;
return element;
}
/**
* Returns the first element in this list.
* 获取头节点，简单
* @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.
* 获取尾节点，简单
* @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的时候再分析.
网友评论