前面的文章中，我们通过分析java的排序，顺便分析了ArrayList和LinkedList，这两个各有优缺点，那么我们能不能折合两者优点呢？我思考了一个问题-信息率，也就是为了存一个我希望存的对象而额外耗费的空间，

• 对于ArrayList，每个数组的下标对于的地址单元存量一个对象指针，1：1的存，但是问题是在于增量导致的数组增长和整体数组的copy实在太损耗性能
• 对于LinkedList，每一个链表节点，要额外增加一个前续来维持链表结构，1：2，事实JDK的LinkedList是prev和next都记录的，是双向链表，为1：3

既然有这个问题，我们可不可以增加信息率来提高些平均性能呢？如下

• ArrayList： [a0,a1,a2,…,an]
• LinkedList:  a0<->a1<->a2<->…..an
• LinkedArray: [a0,a1,a2,….ai]<->[ai+1,….aj]<—>[aj+1,………an]

LinkedArray是用链表为基础，但是链表的节点是一个数组，这样节点的信息率上升为n:n+2，(n是数组的大小)，这样可以这种一些两者的性能。

package net.sourceforge.util;

import java.util.AbstractList;
/**
 * 
 * @author maoanapex88@163.com
 * 
 * @param <E>
 */
public class LinkedArray<E> extends AbstractList<E> {
	public static final int DEFAULT_ARRAY_SIZE=10;
	public static final int DEFAULT_CATACITY=10;
	
	private int arraySize=DEFAULT_ARRAY_SIZE;
	private int size;
	
	private transient ListNode<E> head,tail;
	
	public LinkedArray(){
		this(DEFAULT_CATACITY,DEFAULT_ARRAY_SIZE);
	}
	public LinkedArray(int initialCapacity){
		this(initialCapacity,DEFAULT_ARRAY_SIZE);
	}
	public LinkedArray(int initialCapacity, int arrayLengthInNode){
		if(initialCapacity<=0) throw new IllegalArgumentException("initialCapacity < 0");
		if(arrayLengthInNode<=0) throw new IllegalArgumentException("arrayLengthInNode < 0");
		
		arraySize=arrayLengthInNode;
		
		int nodeCount=initialCapacity/arrayLengthInNode;
		if(initialCapacity%arrayLengthInNode!=0) nodeCount++;
		
		ListNode<E> pre=null;
		for(int i=0;i<nodeCount;i++){
			ListNode<E> node=new ListNode<E>(arraySize);
			if(i==0) head=node;
			else{
				pre.next=node;
				node.previous=pre;
			}
			
			if(i==nodeCount-1) tail=node;
			pre=node;
		}
		size=0;
	}
	
	@Override
	public E remove(int index) {
		rangeCheck(index);
		ListNode<E> node=findNodeByIndex(index);// must not be null
		E ret=node.objArray[index-node.globalStartIndex];

		int start = index - node.globalStartIndex + 1;
		for (int i = start; i < node.localSize; i++) {
			node.objArray[i - 1] = node.objArray[i];
		}
		node.objArray[arraySize - 1] = null;
		node.localSize--;
		
		if(node.localSize==0) {// remove the empty node
			ListNode<E> pre=node.previous;
			ListNode<E>  next=node.next;
			
			if(pre==null){// equals node is the head node
				node.previous=null;
				head=node;
				updateNode(head,0);
			}
			else{
				pre.next=next;
				if(next!=null) next.previous=pre;
				
				updateNode(pre.next,pre.globalStartIndex+pre.localSize);
			}
		}
		
		else updateNode(node.next,node.globalStartIndex+node.localSize);
		
		size--;
		return ret;
	}
	@Override
	public E set(int index, E element) {
		rangeCheck(index);
		ListNode<E> node=findNodeByIndex(index);// must not be null
		E ret=node.objArray[index-node.globalStartIndex];
		node.objArray[index-node.globalStartIndex]=element;
		return ret;
	}
	@Override
	public void add(int index, E element) {
		if (index > size || index < 0) throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
		ListNode<E> node=findNodeByIndex(index);
		if(node==null){// equals to index==size
			if(tail.localSize==arraySize){//tail node's array is full, append a node
				ListNode<E> newNode=new ListNode<E>(arraySize);
				newNode.globalStartIndex=size;
				tail.next=newNode;
				tail=newNode;
			}
			tail.objArray[tail.localSize]=element;
			tail.localSize++;
			if(size==0) head.globalStartIndex=0;
		}
		else{//insert in the middle of node list
			if(node.localSize==arraySize) {//node's array is full
				ListNode<E> next=node.next;
				ListNode<E> newNode=new ListNode<E>(arraySize);
				node.next=newNode;
				newNode.previous=node;
				
				newNode.next=next;
				if(next!=null) next.previous=newNode;
				
				newNode.objArray[newNode.localSize]=element;
				newNode.localSize++;
				updateNode(newNode,node.globalStartIndex+node.localSize);
			}
			else {//node's array is not full
				node.objArray[node.localSize]=element;
				node.localSize++;
				updateNode(node.next,node.globalStartIndex+node.localSize);//node.next must not be null
			}
		}
		size++;
	}
	private void updateNode(ListNode<E> node, int myGlobalStartIndex) {
		if(node==null) return;
		node.globalStartIndex=myGlobalStartIndex;
		if(node.localSize!=0) updateNode(node.next,node.globalStartIndex+node.localSize);
	}
	
	public E get(int index) {
		rangeCheck(index);
		ListNode<E> cur=findNodeByIndex(index);
		if(cur==null) throw new IllegalStateException("This should be an inner error, findNodeByIndex can not return null when used by get method. index="+index);
		return cur.objArray[index-cur.globalStartIndex];
	}

	public int size() {
		return size;
	}
	private final ListNode<E> findNodeByIndex(final int index){
		ListNode<E> cur=head;
		while(cur!=null) {
			if(cur.globalStartIndex+cur.localSize>index) return cur;
			cur=cur.next;
		}
		return null;
	}
	private final void rangeCheck(int index) {
		if (index<0||index >= size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: "+ size);
	}
	
	public String toString() {
		StringBuilder builder=new StringBuilder();
		ListNode<E> node=head;
		builder.append("{").append(size).append(",");
		while(node!=null) {
			builder.append(node.toString()).append("->");
			node=node.next;
		}
		builder.append("}");
		return builder.toString();
	}
	
	private static class ListNode<E> {
		static final int NULL=-1;
		transient E[] objArray;
		ListNode<E> previous,next;
		int globalStartIndex=NULL, localSize=0;
		@SuppressWarnings("unchecked")
		public ListNode(int arrayLength) {
			super();
			objArray=(E[])new Object[arrayLength];
		}
		@Override
		public String toString() {
			StringBuilder sb=new StringBuilder();
			sb.append("(")
			.append(globalStartIndex).append(",")
			.append(localSize).append(",[");
			for(int i=0;i<localSize;i++) sb.append(objArray[i]).append(",");
			sb.append("])");
			return sb.toString();
		}
	}
}