基于LinkedList实现的固定大小线性排序数据结构

插入：O(1),使用链表，无需移动元素

二分查找: O(lgn)

遍历集合: O(n)

public class ArenaList<E> { /*the arena capacity*/ private final int capacity; /*need user to define，int r = compare(e1, e2),when r > 0，e1 > e2,r = 0, e1 = e2, r < 0, e1 < e2*/ private final Comparator<E> comparator;  private final LinkedList<E> values; /*if there is an element in list e1, that e1 equal e2, which e2 is we want to add,  * if keepNewerElement is false,we will drop e2,else drop e1*/ private final boolean keepNewerElement; /*at this moment,the element count, when eCount < size, we can add new element into list and will not remove the last element*/ private volatile int eCount = 0;

容器定义的字段如上代码所示，

capacity必须在构造函数中传入，一旦初始化之后就不能更改。同时以后可能会实现序列化，虽然现在没有考虑序列化问题。

comparator是用户定义的比较器，也必须在构造时初始化。我们约定，调用比较器的compare(e1, e2)比较元素，当返回值r > 0，表示e1 > e2,当r < 0,表示e1 < e2。r = 0则表示元素相等。

values是存储元素的最终容器，因为增删频繁，因此使用链表，初始化之后就不能更改；

keepNewerElement是这样一个作用，当排在最后的两个元素en和em，如果en = em,em是待加入元素，并且擂台已满，是否用新加入的淘汰旧的。默认这个开关是false。

eCount，表示当前容器中添加了多少元素。当擂台没有满时，eCount < size，当擂台满了的时候 eCount = size。这里加了volatile修饰，是为了保证多线程下该变量的可见性。这里不深入探讨Java并发问题，因为这个问题要说清楚可以另开一篇文章来说。简单的说volatile是轻量级同步锁，可能保证变量的可见性但不能保证原子性。同时保证了一些可能引发潜在问题的重排序问题。这些涉及到Java内存模型(JMM)，不在多说。这里没有用J.U.C包下的原子变量是因为我们这里容器的增删也要加锁，为了更好的性能，就没必要CAS自旋消耗性能。

public ArenaList(int capacity, Comparator<E> comparator) {     if (capacity <= 0) {         throw new IllegalArgumentException("size can't be negative number");     }         this.capacity = capacity;     this.comparator = comparator;     this.keepNewerElement = false;     this.values = new LinkedList<E>(); }

public ArenaList(int capacity, Comparator<E> comparator, boolean keepNewerElement) {     if (capacity <= 0) {         throw new IllegalArgumentException("size can't be negative number");     }         this.capacity = capacity;     this.comparator = comparator;     this.keepNewerElement = keepNewerElement;     this.values = new LinkedList<E>(); }

/**  * add e into list with thread-safe  * @param e  */ public void add(E e) {     if (null == e) {         throw new NullPointerException("Null Element.");     }         synchronized (values) {         int index = findElementIndex(e);         if (values.size() >= capacity) {             if (keepNewerElement && index <= values.size()) {                 values.removeLast();             } else if (index < values.size()){                 //e is in the middle of this list                 values.removeLast();             } else {                 //e is at the end of this list and e equals the minElement, no need to add.                 return;             }         }         values.add(index, e);         eCount++;     } }

/**  * remove e from list with thread-safe  * @param e  * @return  */ public boolean remove(E e) {     if (null == e) {         throw new NullPointerException("Null Element.");     }     synchronized (values) {         if(values.remove(e)) {             eCount--;             return true;         }         return false;     } }

/**  * find the index of e should be  * @param e  * @return  */ private int findElementIndex(E e) {     int index = 0;     if (values.size() == 0) {         return index;     }     //values.size() > 0     E minElement = values.getLast();     //the largest element at the index of 0     int high = values.lastIndexOf(minElement);         E maxElement = values.getFirst();     //the least element at the index of values.size() - 1     int low = values.indexOf(maxElement);         if (compareTwoElement(minElement, e) >= 0) {         //minElement >= e         index = high + 1;         return index;     }         if (compareTwoElement(maxElement, e) <= 0) {         //maxElement <= e         return index;     }         //only one element     if (low == high) {         if (capacity == 1) {             return index;         }         if (compareTwoElement(minElement, e) > 0) {             //minElement > e             index = high + 1;             return index;         } else if (compareTwoElement(minElement, e) < 0) {             //minElement < e             return index;         } else {             //minElement = maxElement = e             return index;         }     }         //more than one element and e must at the middle of this list,use binary search to find index     int middle = 0;     while (low < high) {         middle = (low + high) / 2;         E minddleE = values.get(middle);         if (compareTwoElement(minddleE, e) == 0) {             //find it.             index = middle;             return index;         }                 if (compareTwoElement(minddleE, e) > 0) {             //middleE > e             low = middle;         } else {             //middleE < e             high = middle;         }         if (high - low == 1) {             //if there only two element, e is in the middle of this list,low will never be higher or equal high             //at this moment,should check out             //[4,2,1],3 need to insert into it or [4,3,1],2 need to insert into it             return low + 1;         }             }     //at this moment,low >= high,and (middle + 1)is we should find     index = middle + 1;     return index; }