单链表比较简单,直接说双向循环链表,用c语言双向链表的结构定义如下:
typedef struct DNode
{
ElemType data;
struct DNode *priror, *next ;
} DNode ,*DoubleList;
如果p指向双链表中某一节点,则有:p->prior->next = p = p->next->prior。
再来看看jdk中LinkedList是如何实现双向链表的:
private static class Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
用到内部私有静态类来定义双向链表结构。
实例变量和初始化的定义如下:
//这个节点永远不会保存值
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;
//定义一个空的双向链表
public LinkedList() {
header.next = header.previous = header;
}
下面在来看看默认的插入操作:
public boolean add(E e) {
//循环链表,实际上header可以说是新节点的后一个元素
//把header当做头节点,e当做尾节点更好理解一些
addBefore(e, header);
return true;
}
private Entry<E> addBefore(E e, Entry<E> entry) {
/**新节点的数据为e,此处新节点的初始化干了不少活,
*非常之妙,把header的前驱(即最后一个元素)赋值给新值的前驱,把
*header赋值给新值的后驱,
*/
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
//最后一个元素指向新节点
newEntry.previous.next = newEntry;
//header的前驱指向新节点
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
上面是尾插法。其实头插法也是调用addBefore方法。你能想到怎么调用吗?其实这个时候把第一个节点作为头节点考虑就一目了然了,即尾插法是在头节点之前插入新节点,那头插法是在头结点之后或者说是在第一个节点之前插入新节点。
把addBefore(e, header)换成addBefore(e, header.next)即可,太清晰易懂了,如果让我们去实现代码,能做到复用得如此完美吗?
再看看按序号删除又是如何实现的。原以为会从头遍历,然后计数器==序号即开始删除,结果却又想错了。jdk的实现也考虑到了效率问题,稍微做了点优化,其实既然是双向循环,那当然是往前找也可以,往后找也可以了。
public E remove(int index) {
return remove(entry(index));
}
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry<E> e = header;
//小于size的一半时从前往后遍历,大于size的一半时从后往前遍历
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}
//具体的删除方法,没有什么特别的,不过按值、按序号删除都复用了这个方法
private E remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementException();
E result = e.element;
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous = null;
e.element = null;
size--;
modCount++;
return result;
}
查找、替换等方法比较简单,就不在这浪费笔墨了。当然LinkedList也能实现队列、栈等线性表,这些内容另开一篇文章来分析。
分享到:
相关推荐
Java JDK 6学习笔记——ppt简体版.rar
Java JDK 6学习笔记——ppt简体版加课本代码
Java JDK 6学习笔记——ppt简体版
linux安装jdk(csdn)————程序
Java JDK 6学习笔记——ppt简体版 第21章.ppt
Java JDK 6学习笔记——ppt简体版 第20章.ppt
Java JDK 6学习笔记——ppt简体版 第19章.ppt
Java JDK 6学习笔记——ppt简体版 第18章.ppt
Java JDK 6学习笔记——ppt简体版 第17章.ppt
JDK 6.0安装手册——jdk,linux,aix,widow,Solarise.docx
JDK1.6 的学习,包含很多java 的基础教程,可以参考
学习java的不错资料啊,并给出课程中所讲的源代码,方便调试
良葛格出版的java学习笔记,对于初学者来说是一本很不错的书。(前6章和附录A\B)