用动态数组模拟双向循环链表

简单来说其实使用数组模拟LinkedList。同LinkedList的操作基本相似。
基本原理为：数组存放Entry对象，包含数据部分，指针部分(数组下标)
添加，删除基本操作改变指针。数组包含两个链表，一个备用链表(空数据，仅含指针)与
实际存放数据的链表(即保存存入的数)。添加先从备用链表中获取一个空闲节点，
移除把节点重新放入备用链表等待获取。采用ArrayList的数组自动扩张的方法。
具体代码如下：

package com.utils;

import java.util.AbstractSequentialList;
import java.util.Arrays;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;




/**
 * 用数组模拟双向循环列表
 */
public class ArrayLinkedList<E> extends AbstractSequentialList<E> implements 
		List<E>{
	
	//空闲链表头结点,索引为0的位置设置头结点
	private transient Entry<E> freeHeader;	
	//实际链表头结点，索引为1的位置设置头结点
	private transient Entry<E> header;
	private transient int size = 0;		//数组中存储的Entry对象个数
	
	private transient Object[] data;	//Object数组，因为java不支持泛型数组，即Entry<E>[] data = new Entry<E>[10] //error
										//遍历时进行强制类型转换即可
	/**
	 * 构造方法一，初始化化数组 
	 */
	public ArrayLinkedList(int initialCapacity) {
		super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        initArray(initialCapacity);
	}
	
	/**
	 * 构造方法二，构造含有指定集合c中所有元素的链表
	 * 具体见addAll方法
	 */
	public ArrayLinkedList(Collection<? extends E> c) {
		this();
		addAll(c);
	}
	
	/**
	 * 默认数组长度
	 */
	public ArrayLinkedList(){
		this(10);
	}
	
	/**
	 * 初始化数组.
	 * 除header，其他都是备用链表的元素
	 * 实际链表此时为空。数据项都为空
	 */
	private void initArray(int initialCapacity) {
		data = new Object[initialCapacity];
		for(int i = 0 ;i < data.length;i++){
			if(freeHeader==null){
				freeHeader = new Entry<E>(null, i, i+2, data.length-1);
				data[i] = freeHeader;
				continue;
			}
			if(header == null){
				header = new Entry<E>(null, i, i, i);	//初始实际链表头结点,此链表为空
				data[i] = header;
				continue;
			}
			Entry<E> e = new Entry<E>(null, i, 
					i+1==data.length ? 0 : i+1, i-1 == 1 ? 0 : i-1);
			data[i] = e;
		}
	}
	
	/**
	 * 获取一个备用链表的节点
	 * */
	public int getFreeNode(){
		int i = freeHeader.next;
		if(i > 0 ){
			Entry e = (Entry)data[i];
			freeHeader.next = e.next;
			((Entry)data[e.next]).pre = freeHeader.cur;
		}
		return i;
	}
	
	/**
	 * 将空闲节点回收到备用链表
	 * */
	public void free(Entry<E> e){
		e.next  = freeHeader.next;
		e.pre = freeHeader.cur;
		freeHeader.next = e.cur;
		e.element = null;
	}
	
	public void ensureCapacity(int minCapacity) {
		modCount++;
		int oldCapacity = data.length;
		if (minCapacity > oldCapacity) {
			int newCapacity = (oldCapacity * 3) / 2 + 1;
			if (newCapacity < minCapacity)
				newCapacity = minCapacity;
			data = Arrays.copyOf(data, newCapacity);
			//初始化增加的节点
			for(int i = oldCapacity; i < newCapacity;i++){
				Entry<E> e = new Entry<E>(null, i, 
						i+1==data.length ? 0 : i+1, i-1 == 1 ? 0 : i-1);
				data[i] = e;
				//修改备用头结点
				freeHeader.pre = newCapacity - 1;
				freeHeader.next = oldCapacity;
			}
		}
	}

	public E getFirst(){
		if(size == 0)
			throw new NoSuchElementException();
		return ((Entry<E>)data[header.next]).element;
	}
	
	public E getLast(){
		if(size == 0)
			throw new NoSuchElementException();
		return  ((Entry<E>)data[header.pre]).element;
	}
	
	/**
	 * 移除第一个元素，具体见remove()方法
	 */
	public E removeFirst() {
		return remove((Entry<E>)data[header.next]);
	}

	/**
	 * 移除最后一个元素
	 */
	public E removeLast() {
		return remove((Entry<E>)data[header.pre]);
	}
	
	/**
	 * 
	 * 在链表开始位置添加一个元素
	 * 详情见addBefore()
	 */
	public void addFirst(E e) {
		addBefore(e, (Entry<E>)data[header.next]);
	}

	/**
	 * 在链表最后位置添加一个元素
	 * 详情见addBefore()
	 */
	public void addLast(E e) {
		addBefore(e, header);
	}
	
	/**
	 * 查看链表是否包含元素o
	 * 详细见indexOf()方法
	 */
	public boolean contains(Object o) {
		return indexOf(o) != -1;
	}
	
	/**
	 * 
	 * 返回o第一次出现的位置，如果在List中找不到o返回-1
	 */
	public int indexOf(Object o) {
		int index = 0;	//链表的索引也是从0开始
		if (o == null) {
			for (Entry e = (Entry)data[header.next]; e != header; e = (Entry)data[e.next]) {	//从头结点开始，依次遍历
				if (e.element == null)
					return index;
				index++;
			}
		} else {
			for (Entry e = (Entry)data[header.next]; e != header; e = (Entry)data[e.next]) {
				if (o.equals(e.element))
					return index;
				index++;
			}
		}
		return -1;
	}
	
	/**
	 * 双向循环链表，从后面开始遍历即可
	 */
	public int lastIndexOf(Object o) {
		int index = size;
		if (o == null) {
			for (Entry e = (Entry)data[header.pre]; e != header; e = (Entry)data[e.pre]) {
				index--;
				if (e.element == null)
					return index;
			}
		} else {
			for (Entry e = (Entry)data[header.pre]; e != header; e = e = (Entry)data[e.pre]) {
				index--;
				if (o.equals(e.element))
					return index;
			}
		}
		return -1;
	}

	/**
	 * 跟addLast()方法类似，添加成功返回true
	 */
	public boolean add(E e) {
		addBefore(e, header);
		return true;
	}
	
	/**
	 * 假如链表中含有一个或多个o对象，移除第一次出现的o
	 * 如果找不到o返回false
	 */
	public boolean remove(Object o) {
		if (o == null) {
			for (Entry<E> e = (Entry<E>)data[header.next]; e != header; e = (Entry<E>)data[e.next]) {	//从第一个元素开始遍历，没一个Entry对象都包含它下一个元素的信息
				if (e.element == null) {
					remove(e);
					return true;
				}
			}
		} else {
			for (Entry<E> e = (Entry<E>)data[header.next]; e != header; e = (Entry<E>)data[e.next]) {
				if (o.equals(e.element)) {
					remove(e);
					return true;
				}
			}
		}
		return false;
	}
	
	/**
	 * 
	 * 把c中所有元素按顺序添加到链表尾部
	 */
	public boolean addAll(Collection<? extends E> c) {
		return addAll(size, c);
	}
	
	/**
	 * 
	 * 在指定位置按顺序添加c中所有元素带List中
	 * 
	 */
	public boolean addAll(int index, Collection<? extends E> c) {
		if (index < 0 || index > size)	//检查是否越界，=size表示添加到最后
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
					+ size);
		Object[] a = c.toArray();
		int numNew = a.length;
		if (numNew == 0)
			return false;
		ensureCapacity(size + numNew + 2);

		Entry<E> successor = (index == size ? header : entry(index));
		Entry<E> predecessor = (Entry<E>)data[successor.pre];
		for (int i = 0; i < numNew; i++) {	//这里不难，画一个图就出来了，主要是初始化c和修改指针
			//暂时使其next为successor，因为e会赋给前驱,而每次遍历都要修改其前驱的next
			int node = getFreeNode();
			Entry<E> e = (Entry<E>)data[node];
			e.next = successor.cur;
			e.pre = predecessor.cur;
			e.element = (E)a[i];
			predecessor.next = e.cur;   //重新设置前驱的next指针
			predecessor = e;	//让e变为前驱
		}
		successor.pre = predecessor.cur;	//successor的前驱为c中最后一个元素的引用

		size += numNew;		//长度加
		return true;
	}
	
	/**
	 * 移除链表中所有元素
	 */
	public void clear() {
		Entry<E> e = (Entry<E>)data[header.next];
		while (e != header) {	//表示不是只有一个头结点的空链表
			Entry<E> next = (Entry<E>)data[e.next];
			free(e);
			e = next;
		}
		header.next = header.pre = header.cur = 1;	//初始头结点
		size = 0;
		modCount++;
	}
	
	/**
	 * 返回指定位置的元素时
	 */
	public E get(int index) {
		return entry(index).element;
	}

	/**
	 * 设置指定位置的元素
	 */
	public E set(int index, E element) {
		Entry<E> e = entry(index);
		E oldVal = e.element;
		e.element = element;
		return oldVal;
	}
	
	/**
	 * 
	 * 把指定元素添加到指定位置，需先定位到此位置的节点
	 * 详情见addBefore()
	 */
	public void add(int index, E element) {
		addBefore(element, (index == size ? header : entry(index)));
	}

	/**
	 * 移除指定位置的元素
	 */
	public E remove(int index) {
		return remove(entry(index));
	}
	
	/**
	 * 
	 * 返回指定索引位置的Entry对象，需要依次遍历得到。
	 * 这里稍做了一下优化，如果index < size/2 从前面开始遍历
	 * 如果index >= size/2 从后面开始遍历
	 */
	private Entry<E> entry(int index) {
		if (index < 0 || index >= size)	//index在0(包含)到size(不包含)之间，索引从0开始
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
					+ size);
		Entry<E> e = header;
		if (index < (size >> 1)) {
			for (int i = 0; i <= index; i++)
				e = (Entry<E>)data[e.next];	//依次调用e.next才能得到,需调用index+1次，因为它是从头结点开始的
		} else {
			for (int i = size; i > index; i--)
				e = (Entry<E>)data[e.pre]; //依次调用e.previous才能得到
		}
		return e;
	}
	
	
	private Entry<E> addBefore(E e,Entry<E> entry){
		ensureCapacity(size + 1 + 2);
		int node = getFreeNode();
		Entry<E> newEntry = (Entry<E>)data[node];
		newEntry.element = e;
		newEntry.cur = node;
		newEntry.pre = entry.pre;
		newEntry.next = entry.cur;
		
		((Entry<E>)data[newEntry.pre]).next = node;
		((Entry<E>)data[newEntry.next]).pre = node;
		size++;
		return newEntry;
	}
	
	private E remove(Entry<E> e){
		if(e == header)
			throw new NoSuchElementException();
		E result = e.element;
		//改变实际链表的节点指针
		((Entry<E>)data[e.pre]).next = e.next;
		((Entry<E>)data[e.next]).pre = e.pre;
		free(e);
		size--;		//size--
		modCount++;
		return result;
	}
	
	@Override
	public ListIterator<E> listIterator(int index) {
		return new ListItr(index);
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return size;
	}
	

	private static class Entry<E>{
		E element;
		int next;
		int pre;
		int cur;
		
		Entry(E element,int cur,int next,int pre){
			this.element = element;
			this.next = next;
			this.pre = pre;
			this.cur = cur;
		}
		public String toString(){
			return "element:"+ element +" cur:"+cur+" next:"+next+" pre:"+pre;
		}
	}
	

	private class ListItr implements ListIterator<E> {
		private Entry<E> lastReturned = header;		//上一次调用next或previous返回的元素，没有调用next则为头结点
		private Entry<E> next;	//下一次调用next方法返回的元素
		private int nextIndex;	//下一次调用next返回的元素的索引
		private int expectedModCount = modCount;	//用来检测遍历过程中是否产生了并发操作

		ListItr(int index) {	//构造器，是迭代器定位到index位置，要返回index位置的元素需调用一次next()方法时
			if (index < 0 || index > size)	
				throw new IndexOutOfBoundsException("Index: " + index
						+ ", Size: " + size);
			if (index < (size >> 1)) {	//从前面开始遍历
				next = (Entry<E>)data[header.next];	 //这是index为0的元素
				for (nextIndex = 0; nextIndex < index; nextIndex++)
					next = (Entry<E>)data[next.next];	//最终next为第index个元素，index从0开始
			} else {		//从后面开始遍历
				next = header;
				for (nextIndex = size; nextIndex > index; nextIndex--)
					next = (Entry<E>)data[next.pre];	//最终next为第index个元素，index从0开始
			}
		}

		public boolean hasNext() {	//size位置可没有元素
			return nextIndex != size;
		}

		public E next() {
			checkForComodification();
			if (nextIndex == size)
				throw new NoSuchElementException();

			lastReturned = next;
			next = (Entry<E>)data[next.next];	//这里与ArrayList中的cursor何其相似
			nextIndex++;
			return lastReturned.element;
		}

		public boolean hasPrevious() {
			return nextIndex != 0;
		}

		public E previous() {
			if (nextIndex == 0)
				throw new NoSuchElementException();

			lastReturned = next = (Entry<E>)data[next.pre];
			nextIndex--;
			checkForComodification();
			return lastReturned.element;
		}

		public int nextIndex() {	//返回下一次调用next返回的元素的索引
			return nextIndex;
		}

		public int previousIndex() {	//返回下一次调用previous返回的元素的索引
			return nextIndex - 1;
		}

		public void remove() {
			checkForComodification();
			Entry<E> lastNext = (Entry)data[lastReturned.next];
			try {
				ArrayLinkedList.this.remove(lastReturned);	//移除上一层调用next()或previous返回的元素
			} catch (NoSuchElementException e) {
				throw new IllegalStateException();
			}
			if (next == lastReturned)	//表明是调用previous后才调用remove方法
				next = lastNext;
			else
				nextIndex--;		//元素减少。nextIndex--
			lastReturned = header;	//重置lastReturned
			expectedModCount++;
		}

		public void set(E e) {
			if (lastReturned == header)
				throw new IllegalStateException();
			checkForComodification();
			lastReturned.element = e;
		}

		public void add(E e) {
			checkForComodification();
			lastReturned = header;
			addBefore(e, next);	//在上一次调用next返回的元素之后，在上次调用previous返回的元素之前添加e
			nextIndex++;	//元素增加，索引增加，保证下次调用next()不是返回添加的元素
			expectedModCount++;
		}

		final void checkForComodification() {
			if (modCount != expectedModCount)
				throw new ConcurrentModificationException();
		}
	}
}