写了一个list类SortedArrayList不知该叫什么名字写了一个SortedArrayList类我觉得应该是有普遍的用途（通用
写了一个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;}@Overridepublic boolean add(E obj) {doAdd(obj, 0, arr.size());return true;}@SuppressWarnings("unchecked")@Overridepublic boolean remove(Object obj) {int index = doFind((E) obj, 0, arr.size());if (index >= 0) {arr.remove(index);return true;}return false;}}?
以上贴出来的是简化版本，方便浏览，附件中是完全版本。
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接口的么，呵呵 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的其他数据接口类也是这样使用的。 14 楼 vlinux 2009-05-05 既然你用了泛型，要不你就这样进行定义<E extends Comparable>，要不你就在程序里面进行判断，否则我一旦掉用add方法就抛出异常那就没意思了 15 楼 fly_hyp 2009-05-05 thanks，
应该写成这样。
E extends Comparable<E> 16 楼 kaipingk 2009-05-05 多此一举，用treeset不就得了 17 楼 vlinux 2009-05-05 楼上.Set和List的区别还是很明显的吧...
汗，我的错，没注意看注释
# /**
# * 其中的元素的唯一的，其中的元素是排序的（从小到大）
# * @author hyp
# * @param <E>
# */
楼主的确应该是Set.. 18 楼 fly_hyp 2009-05-06 想了几天终于想到了确切的名字了 SortedArraySet 19 楼 jojo_java 2009-05-06 确实没必要！！！重复制造轮子，闭门造车！！！ 20 楼 fly_hyp 2009-05-06 jojo_java 写道确实没必要！！！重复制造轮子，闭门造车！！！
各种数据结构有特有的用途 SortedArraySet 具有找前后元素快的特点
21 楼 qamer 2009-05-07 Middle二分 22 楼 cats_tiger 2009-05-09 不是不欣赏算法，而是反对重复造轮子。有很多可排序的Collection，google code有，apache commons也有。 23 楼 prince1209 2009-05-09 TreeSet 和TreeMap的 实现肯定不一样额
TreeSet 是SortedSet的一个实现类 是一个有序集合 默认按升序排的
TreeMap 是一个键值队 （key-value） 24 楼 java.lang.Object 2009-05-13 没看出有什么闪光点，但是楼主的精神是可嘉的 25 楼 java.lang.Object 2009-05-13 prince1209 写道TreeSet 和TreeMap的 实现肯定不一样额
TreeSet 是SortedSet的一个实现类 是一个有序集合 默认按升序排的
TreeMap 是一个键值队 （key-value）
你这样说肯定是没看源码，想当然的认为，其实TreeSet里面就有一个TreeMap。它就是基于TreeMap来实现的。 26 楼 Feiing 2009-05-13 fly_hyp 写道jojo_java 写道确实没必要！！！重复制造轮子，闭门造车！！！
各种数据结构有特有的用途 SortedArraySet 具有找前后元素快的特点
不重复，排序， 能前后查找 你应该用 java.util.LinkedHashSet 27 楼 fly_hyp 2009-05-14 发了这个帖子收获还是挺大的。
修改了范型的使用代码。
对于SortedArraySet这个名字我还是比较满意的。
这个数据结构有如下特点
1.具有set所有的功能
2.插入速度慢
3.查询速度快，和 hash、tree是一个级别的
4.占用内存少
5.元素排序的（象一个优先级队列)
6.方面查找前后元素(处理队列时，可以查询前后的情况)
28 楼 jzc928 2009-05-16 二分查找如果不用递归实现是不是会好点。 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。 30 楼 sdh5724 2009-05-18 JE现在的规矩是：
1。 发表代码实现为新手
2。 有类似实现是重复造轮子
3。 业务无视技术
楼主，小心了。 31 楼 lovejavaei 2009-05-19 sdh5724 写道JE现在的规矩是：
1。 发表代码实现为新手
2。 有类似实现是重复造轮子
3。 业务无视技术
楼主，小心了。
搂住的精神绝对可嘉，值得发扬，痛恨那些再跟着瞎说“重复造轮子”的人，有本事，你造一个！从回复的帖子来看，相当一部分人不知道数据结构的东西，建议不懂数据结构没有深入研究过collection的，不要瞎评论。
对楼住代码给点看法
单纯的线性表要实现边插入边排序效率低下，不管是数组还是链表，因为数组做插入效率低，而链表做遍历效率低。
所以jdk里用的是红黑树来实现的，这是一种复杂的树结构，建议研究一下
