写了一个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;
	}	
}

 

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

评论

31 楼 lovejavaei 2009-05-19  

sdh5724 写道

JE现在的规矩是：
1。 发表代码实现为新手
2。 有类似实现是重复造轮子
3。 业务无视技术

楼主，小心了。

搂住的精神绝对可嘉，值得发扬，痛恨那些再跟着瞎说“重复造轮子”的人，有本事，你造一个！从回复的帖子来看，相当一部分人不知道数据结构的东西，建议不懂数据结构没有深入研究过collection的，不要瞎评论。

对楼住代码给点看法
单纯的线性表要实现边插入边排序效率低下，不管是数组还是链表，因为数组做插入效率低，而链表做遍历效率低。

所以jdk里用的是红黑树来实现的，这是一种复杂的树结构，建议研究一下

30 楼 sdh5724 2009-05-18  

JE现在的规矩是：
1。 发表代码实现为新手
2。 有类似实现是重复造轮子
3。 业务无视技术

楼主，小心了。

29 楼 captmjc 2009-05-17  

LZ的类毫无意义。LZ对List的认识有问题。
首先，没有理解接口（也包括抽象类）是一种契约，而不单单是把这个接口中的方法从public void foo();变成public void foo() {...}。LZ的所谓SortedArrayList一个错误的List实现，它违反了java.util.List中对add方法的约定——新添加的内容，位于List的最后（参照List的javadoc），进而导致get/addAll这样的方法也与List中的约定的不一致。

第二，建议LZ深入理解一下Java Collection Framework的设计理念。而且，LZ可以实际想像一下，Collections.sort可以在任何时候满足LZ的要求。而反过来，LZ的类，在绝大多数时候的效率都差很多，而且是差在毫无意义的地方。

应用LZ"SortedArrayList是一直保持排序状态的List和调用sort方法是不一样的。"
其实，实际使用的时候，很少会有一边插入，一边排序的要求，往往都是一次性往容器中添加N个元素，然后得到排序结果。

此外，读一下Thinking in Java这样的书，里面有关于ArrayList/Vector vs LinkedList（当然，包括其他Map、Set的比较）。（可能）需要频繁插入操作的时候，应当使用基于列表的LinkedList，因此，不考虑其他因素，LZ的arr对象应当使用LinkedList。

28 楼 jzc928 2009-05-16  

二分查找如果不用递归实现是不是会好点。

27 楼 fly_hyp 2009-05-14  

发了这个帖子收获还是挺大的。

修改了范型的使用代码。

对于SortedArraySet这个名字我还是比较满意的。
这个数据结构有如下特点

1.具有set所有的功能
2.插入速度慢
3.查询速度快，和 hash、tree是一个级别的
4.占用内存少
5.元素排序的（象一个优先级队列)
6.方面查找前后元素(处理队列时，可以查询前后的情况)

26 楼 Feiing 2009-05-13  

fly_hyp 写道

jojo_java 写道

确实没必要！！！重复制造轮子，闭门造车！！！

各种数据结构有特有的用途 SortedArraySet 具有找前后元素快的特点

不重复，排序， 能前后查找 你应该用 java.util.LinkedHashSet

25 楼 java.lang.Object 2009-05-13  

prince1209 写道

TreeSet  和TreeMap的  实现肯定不一样额
TreeSet 是SortedSet的一个实现类  是一个有序集合 默认按升序排的
TreeMap  是一个键值队  （key-value）

你这样说肯定是没看源码，想当然的认为，其实TreeSet里面就有一个TreeMap。它就是基于TreeMap来实现的。

24 楼 java.lang.Object 2009-05-13  

没看出有什么闪光点，但是楼主的精神是可嘉的

23 楼 prince1209 2009-05-09  

TreeSet  和TreeMap的  实现肯定不一样额
TreeSet 是SortedSet的一个实现类  是一个有序集合 默认按升序排的
TreeMap  是一个键值队  （key-value）

22 楼 cats_tiger 2009-05-09  

不是不欣赏算法，而是反对重复造轮子。有很多可排序的Collection，google code有，apache commons也有。

21 楼 qamer 2009-05-07  

Middle二分

20 楼 fly_hyp 2009-05-06  

jojo_java 写道

确实没必要！！！重复制造轮子，闭门造车！！！

各种数据结构有特有的用途 SortedArraySet 具有找前后元素快的特点

19 楼 jojo_java 2009-05-06  

确实没必要！！！重复制造轮子，闭门造车！！！

18 楼 fly_hyp 2009-05-06  

想了几天终于想到了确切的名字了 SortedArraySet

17 楼 vlinux 2009-05-05  

楼上.Set和List的区别还是很明显的吧...

汗，我的错，没注意看注释

# /**
#  * 其中的元素的唯一的，其中的元素是排序的（从小到大）
#  * @author hyp
#  * @param <E>
#  */ 

楼主的确应该是Set..

16 楼 kaipingk 2009-05-05  

多此一举，用treeset不就得了

15 楼 fly_hyp 2009-05-05  

thanks，
应该写成这样。
E extends Comparable<E>

14 楼 vlinux 2009-05-05  

既然你用了泛型，要不你就这样进行定义<E extends Comparable>，要不你就在程序里面进行判断，否则我一旦掉用add方法就抛出异常那就没意思了

13 楼 fly_hyp 2009-05-05  

vlinux 写道

呵呵，这么多人投新手帖，我觉得是和JavaEye上大多是技术方面特长，而不欣赏算法有关。


这里有个小问题

#             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); 
#             }

你就那么自信的肯定E是实现了Comparable接口的么，呵呵

其实这是约定，能放入这个List的对象必须实现Comparable接口，不然不能排序，大部分系统原生对象如Integer Float String 等都实现这个接口。jdk的其他数据接口类也是这样使用的。

12 楼 vlinux 2009-05-05  

呵呵，这么多人投新手帖，我觉得是和JavaEye上大多是技术方面特长，而不欣赏算法有关。


这里有个小问题

#             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); 
#             }

你就那么自信的肯定E是实现了Comparable接口的么，呵呵