写了一个list类SortedArrayList不知该叫什么名字

写了一个SortedArrayList类我觉得应该是有普遍的用途（通用类），想取一个更好一点的名字，有兴趣的帮我想想。代码无偿奉献。哈哈。

我现在的用途是存放Id,其中没有重复数据，方便查找前后关系。

 

/**
 * 其中的元素的唯一的，其中的元素是排序的（从小到大）
 * @author hyp
 * @param <E>
 */
public class SortedArrayList<E> implements List<E> {
	ArrayList<E> arr;
	public SortedArrayList() {
		arr = new ArrayList<E>();
	}
	public SortedArrayList(int initialCapacity) {
		arr = new ArrayList<E>(initialCapacity);
	}
	@SuppressWarnings("unchecked")
	private void doAdd(E obj, int startPos, int endPos) {
		int dPos = endPos - startPos;
		if (dPos < 1) {
			// 初始情况
			arr.add(obj);
		} else if (dPos == 1) {
			E tmpObj = arr.get(startPos);
			if (((Comparable) tmpObj).compareTo(obj) > 0) {
				arr.add(startPos, obj);
			}
			if (((Comparable) tmpObj).compareTo(obj) < 0) {
				arr.add(startPos + 1, obj);
			}
		} else {
			int midPos = (endPos + startPos) / 2;
			E tmpObj = arr.get(midPos);
			if (((Comparable) tmpObj).compareTo(obj) > 0) {
				doAdd(obj, startPos, midPos);
			}
			if (((Comparable) tmpObj).compareTo(obj) < 0) {
				doAdd(obj, midPos, endPos);
			}
		}
	}
	@SuppressWarnings("unchecked")
	private int doFind(E obj, int startPos, int endPos) {
		int dPos = endPos - startPos;
		if (dPos < 1) {
			// 初始情况
			return -1;
		} else if (dPos == 1) {
			E tmpObj = arr.get(startPos);
			if (tmpObj.equals(obj)) {
				return startPos;
			}
		} else {
			int midPos = (endPos + startPos) / 2;
			E tmpObj = arr.get(midPos);
			if (((Comparable) tmpObj).compareTo(obj) > 0) {
				return doFind(obj, startPos, midPos);
			} else if (((Comparable) tmpObj).compareTo(obj) < 0) {
				return doFind(obj, midPos, endPos);
			} else {
				return midPos;
			}
		}
		return -1;
	}
	@Override
	public boolean add(E obj) {
		doAdd(obj, 0, arr.size());
		return true;
	}
	@SuppressWarnings("unchecked")
	@Override
	public boolean remove(Object obj) {
		int index = doFind((E) obj, 0, arr.size());
		if (index >= 0) {
			arr.remove(index);
			return true;
		}
		return false;
	}	
}

 

以上贴出来的是简化版本，方便浏览，附件中是完全版本。

评论

11 楼 keating 2009-05-05  

Xorcerer 写道

好奇一下，ArrayList不是链表吗？而Object[]不是数组吗？
如果以上都肯定的话，那么为什么ArrayList内部是Object[]？扩容时怎么操作？全部复制一份？还是每次申请大片的空间，然后拼接那种。

我认为啊，这个数据集结构都是数组写出来的吧。扩充时判断一下数组大小就行了。以前一本《探秘java》里看过。

10 楼 guooscar 2009-05-05  

fly_hyp 写道

guooscar 写道

TreeSet 和你这个类功能一样吧？

仔细考虑了一下这个实现和TreeSet TreeMap等还是不一样，他获得子序列的算法复杂度为 O(0) 常数时间。

那还有必要写这个吗？

9 楼 fly_hyp 2009-05-05  

guooscar 写道

TreeSet 和你这个类功能一样吧？

仔细考虑了一下这个实现和TreeSet TreeMap等还是不一样，他获得子序列的算法复杂度为 O(0) 常数时间。

8 楼 kimmking 2009-05-04  

LinkedList才是链表。
ArrayList没有链，就是Array而已。

7 楼 Xorcerer 2009-05-04  

好奇一下，ArrayList不是链表吗？而Object[]不是数组吗？
如果以上都肯定的话，那么为什么ArrayList内部是Object[]？扩容时怎么操作？全部复制一份？还是每次申请大片的空间，然后拼接那种。

6 楼 fly_hyp 2009-05-03  

kimmking 写道

ArrayList<E> arr换成一个Object[]然后使用二分法可以提高效率。

Object[]是会快一点，应该是差不多的，ArrayList内部也是Object[]

5 楼 fly_hyp 2009-05-03  

guooscar 写道

TreeSet 和你这个类功能一样吧？

刚刚仔细看了一遍TreeSet的功能，应该是一样的，谢谢了。不过可能性能上有少量差别

4 楼 fly_hyp 2009-05-03  

aquleo 写道

说真的,我觉得这个类没有太大必要,如果真想做排序还不如直接用Collections的sort方法...

SortedArrayList是一直保持排序状态的List和调用sort方法是不一样的。

3 楼 aquleo 2009-05-02  

说真的,我觉得这个类没有太大必要,如果真想做排序还不如直接用Collections的sort方法...

2 楼 guooscar 2009-05-02  

TreeSet 和你这个类功能一样吧？

1 楼 kimmking 2009-05-02  

ArrayList<E> arr换成一个Object[]然后使用二分法可以提高效率。