结合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也能实现队列、栈等线性表，这些内容另开一篇文章来分析。