在很多的实际应用中，经常会遇过这种情况。就是要求排序(升序或降序)只保存N个对象信息，如我发表的其中一篇文件 (原创)设计一个Tomcat访问日志分析工具 这个工具需要解析非常多的数据，再排出前10位流量最大的页面信息。我们知道 Java中有Collections.sort方法可以对list进行排序，但在数据量很大的情况，每次要取时进行一次排序，效率就比较的低，所以我实现下面这个 SortedList工具类，供大家参考学习。有什么问题和建议也希望大家回复给我，Thx!
SortedList工具类实现以下功能：
* 自动排序
* 可以设置list的最大size，超过该size后，list会根据排序的类型(升序去掉最大的或降序去掉最小的)保证list的size不超过最大设置
* 可以对元素进行设置唯一设置
* 注意事项：
SortedList支持泛型，所以需要使用jdb5.0或以版本编译运行。
SortedList是非线程安全的，如果是多线程的情况，请加上安全锁
下面是一个使用的例子：
1 //size is 5. element is unique. use ascending order
2 SortedList<String> list = new SortedList<String>(5, true, true);
3
4 list.add("r");
5 list.add("a");
6 list.add("c");
7 list.add("b");
8 list.add("e");
9 list.add("g");
10 list.add("a");
11
12 System.out.println(list);
打印出来的结果：
util.SortedList@69b332[1=a,2=b,3=c,4=e,5=g]
源代码如下：
1 import java.util.Collection;
2 import java.util.LinkedList;
3 import java.util.ListIterator;
4
5 import org.apache.commons.lang.builder.ToStringBuilder;
6
7 /**
8 * <p>
9 * Sorted linked list.
10 * </p>
11 * <p>
12 * <pre>
13 * it could provide a sorted list by certain size. default szie is -1(size is not limit).
14 * it also support unique item sort by setUnique method. default is not unique element sort.
15 * if szie is great than certain count,we have two choices.
16 * if desc then the smallest one will be removed,
17 * if asc then the biggest one will be removed.
18 *
19 * Notice: the element in the list must implement Comparable interface.
20 * </per>
21 * <p>
22 *
23 * @author Matthew Xie
24 * @version 2006-6-2
25 */
26 public class SortedList<T extends Comparable<T>> extends LinkedList<T> {
27
28 public static final int DEFAULT_LIST_SIZE = -1;
29
30 /**
31 * serial version uid
32 */
33 private static final long serialVersionUID = -9019444166911394396L;
34
35 private int item_num;
36
37 private boolean isUnique = false;
38 private boolean isAsc = true;
39
40 /**
41 * get the ordered item number
42 * @return item number
43 */
44 public int getItem_num() {
45 return item_num;
46 }
47
48 /**
49 * set the ordered item number.
50 * @param item_num item number.
51 */
52 public void setItem_num(int item_num) {
53 this.item_num = item_num;
54 }
55
56
57 /**
58 * @param item_num
59 */
60 public SortedList(int item_num) {
61 this(item_num, false, true);
62
63 }
64
65 /**
66 * @param item_num
67 * @param isUnique
68 * @param isAsc
69 */
70 public SortedList(int item_num, boolean isUnique, boolean isAsc) {
71 super();
72 this.item_num = item_num;
73 this.isUnique = isUnique;
74 this.isAsc = isAsc;
75 }
76
77 /**
78 * default construct method
79 */
80 public SortedList() {
81 this(DEFAULT_LIST_SIZE);
82 }
83
84 /**
85 * <p>
86 * add to the list, and then ordered the item.</p>
87 * @param t object
88 */
89 private void addToItemList(T t) {
90 int len = size();
91
92 if (len == 0) {
93 super.add(t);
94 return;
95 }
96
97 T tTemp;
98 if (item_num > 0) {
99 tTemp = getLast();
100 if (!compareTo(t, tTemp) && len >= item_num) {
101 return;
102 }
103 }
104
105 boolean isContained = false;
106 if (isUnique && contains(t)) {
107 isContained = true;
108 }
109
110 boolean added = false;
111 ListIterator<T> listIter = listIterator();
112 int previousIndex;
113 while (listIter.hasNext()) {
114 tTemp = listIter.next();
115 if (compareTo(t, tTemp)) {
116 previousIndex = listIter.previousIndex();
117 super.add(previousIndex, t);
118 added = true;
119 break;
120 }
121 }
122 int nowSize = size();
123
124 if (!added) {
125 if (item_num > 0) {
126 if (nowSize < item_num) {
127 super.add(t);
128 added = true;
129 }
130 } else {
131 super.add(t);
132 added = true;
133 }
134 }
135
136 if (isUnique && isContained && added) {
137 int pos = lastIndexOf(t);
138 if (pos != -1) {
139 remove(pos);
140 }
141 }
142
143 if (item_num > 0) {
144 if (size() > item_num) {
145 removeLast();
146 }
147 }
148 }
149
150 /**
151 * Appends all of the elements in the specified collection to the end of
152 * this list, in the order that they are returned by the specified
153 * collection's iterator. The behavior of this operation is undefined if
154 * the specified collection is modified while the operation is in
155 * progress. (This implies that the behavior of this call is undefined if
156 * the specified Collection is this list, and this list is nonempty.)
157 *
158 * @param list the elements to be inserted into this list.
159 * @return <tt>true</tt> if this list changed as a result of the call.
160 * @throws NullPointerException if the specified collection is null.
161 */
162 public void addAll(Collection<T> list) {
163 if (list == null) {
164 return;
165 }
166 for (T t : list) {
167 addToItemList(t);
168 }
169 }
170
171 /**
172 * Appends the specified element to the this list.
173 * <p>
174 * notice: that after added to the list. the current object added to list<br>
175 * will be ordered. <br>
176 * if the ordered list biggest lenght is n, and the current object is bigger or<br>
177 * smaller than any one of the n objects, it will insert into his right order position.<br>
178 * if the thest n objects if bigger ot smaller than current object, it won't be added to the list.<br>
179 * </p>
180 *
181 * @param t element to be appended to this list.
182 * @return <tt>true</tt> (as per the general contract of
183 * <tt>Collection.add</tt>).
184 */
185 @Override
186 public boolean add(T t) {
187 addToItemList(t);
188 return true;
189 }
190
191
192
193 /**
194 * get the object toString method's return result
195 * @param t object
196 * @return toString value
197 */
198 public String getString(T t) {
199 return t.toString();
200 }
201
202
203 /**
204 * Override the toString method.
205 * @return the item info from the list.
206 */
207 @Override
208 public String toString() {
209 ToStringBuilder toStringBuilder = new ToStringBuilder(this);
210
211 ListIterator<T> listIter = listIterator();
212 T tTemp;
213 Integer i = 1;
214 while (listIter.hasNext()) {
215 tTemp = listIter.next();
216 toStringBuilder.append(i.toString(), getString(tTemp));
217 i++;
218 }
219 return toStringBuilder.toString();
220 }
221
222 /**
223 * <p>
224 * compare method.
225 * </p>
226 * <p>
227 * <pre>
228 * t1 is the object you add.
229 * t2 is the object get from list
230 * </pre>
231 * </p>
232 * @param t1 item1
233 * @param t2 item2
234 * @return true or false to compare between t1 and t2
235 */
236 protected Boolean compareTo(T t1, T t2) {
237 boolean bRet;
238 if (t1 == null) {
239 bRet = false;
240 } else {
241 if (t2 == null) {
242 bRet = true;
243 }
244 bRet = t1.compareTo(t2) > 0 ? true : false;
245 }
246 if (isAsc()) {
247 bRet = !bRet;
248 }
249
250 return bRet;
251 }
252
253 /**
254 * @param isUnique The isUnique to set.
255 */
256 public void setUnique(boolean isUnique) {
257 this.isUnique = isUnique;
258 }
259
260 /**
261 * equal the object t1 with t2. true means t1 and t2 are equal.
262 *
263 * @param t1 object
264 * @param t2 object
265 * @return t1 is equal to t2 or not.
266 */
267 protected Boolean equalItem(T t1, T t2) {
268 if (t1 == null) {
269 if (t2 == null) {return true;}
270 } else {
271 if (t2 != null) {
272 return t1.compareTo(t2) == 0 ? true : false;
273 }
274 }
275 return false;
276 }
277
278 public boolean isAsc() {
279 return isAsc;
280 }
281
282 public void setAsc(boolean isAsc) {
283 this.isAsc = isAsc;
284 }
285
286 public static void main(String[] args) {
287
288 //size is 5. element is unique. use ascending order
289 SortedList<String> list = new SortedList<String>(5, true, true);
290
291 list.add("r");
292 list.add("a");
293 list.add("c");
294 list.add("b");
295 list.add("e");
296 list.add("g");
297 list.add("a");
298
299 System.out.println(list);
300 }
301 }
302
