# (53) 剖析Collections - 算法 / 计算机程序的思维逻辑

1. 对容器接口对象进行操作
2. 返回一个容器接口对象

• 查找和替换
• 排序和调整顺序
• 添加和修改

• 适配器：将其他类型的数据转换为容器接口对象
• 装饰器：修饰一个给定容器接口对象，增加某种性质

```public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
```

```public static <T> Comparator<T> reverseOrder()
public static <T> Comparator<T> reverseOrder(Comparator<T> cmp)```

```List<Integer> list = new ArrayList<>(Arrays.asList(new Integer[]{
35, 24, 13, 12, 8, 7, 1
}));
System.out.println(Collections.binarySearch(list, 7, Collections.reverseOrder()));
```

```5
```

List的二分查找的基本思路与Arrays中的是一样的，但，数组可以根据索引直接定位任意元素，实现效率很高，但List就不一定了，我们来看它的实现代码：

```public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
```

indexedBinarySearch的代码为：

```private static <T>
int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key)
{
int low = 0;
int high = list.size()-1;

while (low <= high) {
int mid = (low + high) >>> 1;
Comparable<? super T> midVal = list.get(mid);
int cmp = midVal.compareTo(key);

if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
}
```

iteratorBinarySearch的代码为：

```private static <T>
int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
{
int low = 0;
int high = list.size()-1;
ListIterator<? extends Comparable<? super T>> i = list.listIterator();

while (low <= high) {
int mid = (low + high) >>> 1;
Comparable<? super T> midVal = get(i, mid);
int cmp = midVal.compareTo(key);

if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
}
```

```private static <T> T get(ListIterator<? extends T> i, int index) {
T obj = null;
int pos = i.nextIndex();
if (pos <= index) {
do {
obj = i.next();
} while (pos++ < index);
} else {
do {
obj = i.previous();
} while (--pos > index);
}
return obj;
}
```

Collections提供了如下查找最大最小值的方法：

```public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp)
public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)
```

```public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) {
Iterator<? extends T> i = coll.iterator();
T candidate = i.next();

while (i.hasNext()) {
T next = i.next();
if (next.compareTo(candidate) > 0)
candidate = next;
}
return candidate;
}
```

```public static int frequency(Collection<?> c, Object o)
```

```public int indexOf(String str)
public int lastIndexOf(String str)
```

```public static int indexOfSubList(List<?> source, List<?> target)
public static int lastIndexOfSubList(List<?> source, List<?> target)
```

indexOfSubList从开头找，lastIndexOfSubList从结尾找，没找到返回-1，找到返回第一个匹配元素的索引位置，比如：

```List<Integer> source = Arrays.asList(new Integer[]{
35, 24, 13, 12, 8, 24, 13, 7, 1
});
System.out.println(Collections.indexOfSubList(source, Arrays.asList(new Integer[]{24, 13})));
System.out.println(Collections.lastIndexOfSubList(source, Arrays.asList(new Integer[]{24, 13})));
```

```1
5
```

```public static boolean disjoint(Collection<?> c1, Collection<?> c2)
```

```public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal)
```

Arrays类有针对数组对象的排序方法，Collections提供了针对List接口的排序方法，如下所示：

```public static <T extends Comparable<? super T>> void sort(List<T> list)
public static <T> void sort(List<T> list, Comparator<? super T> c)
```

```public static <T extends Comparable<? super T>> void sort(List<T> list) {
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator<T> i = list.listIterator();
for (int j=0; j<a.length; j++) {
i.next();
i.set((T)a[j]);
}
}
```

```public static void swap(List<?> list, int i, int j)
```

```public static void swap(List<?> list, int i, int j) {
final List l = list;
l.set(i, l.set(j, l.get(i)));
}
```

```public static void reverse(List<?> list)
```

```public static void reverse(List<?> list) {
int size = list.size();
if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
swap(list, i, j);
} else {
ListIterator fwd = list.listIterator();
ListIterator rev = list.listIterator(size);
for (int i=0, mid=list.size()>>1; i<mid; i++) {
Object tmp = fwd.next();
fwd.set(rev.previous());
rev.set(tmp);
}
}
}```

```public static void shuffle(List<?> list)
public static void shuffle(List<?> list, Random rnd)
```

```public static void shuffle(List<?> list, Random rnd) {
int size = list.size();
if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
for (int i=size; i>1; i--)
swap(list, i-1, rnd.nextInt(i));
} else {
Object arr[] = list.toArray();

// Shuffle array
for (int i=size; i>1; i--)
swap(arr, i-1, rnd.nextInt(i));

// Dump array back into list
ListIterator it = list.listIterator();
for (int i=0; i<arr.length; i++) {
it.next();
it.set(arr[i]);
}
}
}
```

`[8, 5, 3, 6, 2]`

```[6, 2, 8, 5, 3]
```

`[3, 6, 2, 8, 5]`

```public static void rotate(List<?> list, int distance)
```

distance表示循环移位个数，一般正数表示向右移，负数表示向左移，比如：

```List<Integer> list1 = Arrays.asList(new Integer[]{
8, 5, 3, 6, 2
});
Collections.rotate(list1, 2);
System.out.println(list1);

List<Integer> list2 = Arrays.asList(new Integer[]{
8, 5, 3, 6, 2
});
Collections.rotate(list2, -2);
System.out.println(list2);
```

```[6, 2, 8, 5, 3]
[3, 6, 2, 8, 5]
```

```Collections.rotate(list.subList(j, k+1), -1);
```

```List<Integer> list = Arrays.asList(new Integer[]{
8, 5, 3, 6, 2, 19, 21
});
Collections.rotate(list.subList(1, 5), 2);
System.out.println(list);
```

```[8, 6, 2, 5, 3, 19, 21]
```

`[8, 5, 3, 6, 2] -> [3, 6, 2, 8, 5] `

[8, 5, 3, 6, 2] -> [6, 2, 8, 5, 3]

1. 翻转子列表A

2. 翻转子列表B

3. 翻转整个列表

```private static void rotate2(List<?> list, int distance) {
int size = list.size();
if (size == 0)
return;
int mid =  -distance % size;
if (mid < 0)
mid += size;
if (mid == 0)
return;

reverse(list.subList(0, mid));
reverse(list.subList(mid, size));
reverse(list);
}
```

mid为两个子列表的分割点，调用了三次reverse以实现子列表顺序交换。

Collections也提供了几个批量添加和修改的方法，逻辑都比较简单，我们看下。

public static <T> boolean addAll(Collection<? super T> c, T... elements)

elements为可变参数，将所有元素添加到容器c中。这个方法很方便，比如，可以这样：

```List<String> list = new ArrayList<String>();
String[] arr = new String[]{"深入", "浅出"};
System.out.println(list);
```

```[hello, world, 老马, 编程, 深入, 浅出]
```

`public static <T> void fill(List<? super T> list, T obj)`

`public static <T> void copy(List<? super T> dest, List<? extends T> src)`

97 篇文章36 人订阅

0 条评论

792

22010

4203

1034

1878

1361

22110

2247

2058

1003