结合JDK学习数据结构——线性表链式存储
???? 单链表比较简单，直接说双向循环链表，用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也能实现队列、栈等线性表，这些内容另开一篇文章来分析。