当前位置 : 首页 » 文章分类 :  开发  »  Java-集合框架基础

Java-集合框架基础

Java Collections Framework (JCF) Java集合框架笔记

《深入理解Java集合框架》系列文章
http://www.cnblogs.com/CarpenterLee/p/5545987.html


Collections工具类

java.util.Collections

public class Collections
extends Object

此类完全由在 collection 上进行操作或返回 collection 的静态方法组成。它包含在 collection 上操作的多态算法,即“包装器”,包装器返回由指定 collection 支持的新 collection,以及少数其他内容。

如果为此类的方法所提供的 collection 或类对象为 null,则这些方法都将抛出 NullPointerException。

此类中所含多态算法的文档通常包括对实现 的简短描述。应该将这类描述视为实现注意事项,而不是规范 的一部分。实现者应该可以随意使用其他算法替代,只要遵循规范本身即可。(例如,sort 使用的算法不一定是合并排序算法,但它必须是稳定的。)

此类中包含的“破坏性”算法,即可修改其所操作的 collection 的算法,该算法被指定在 collection 不支持适当的可变基元(比如 set 方法)时抛出 UnsupportedOperationException。如果调用不会对 collection 产生任何影响,那么这些算法可能(但不要求)抛出此异常。例如,在已经排序的、不可修改列表上调用 sort 方法可能会(也可能不会)抛出 UnsupportedOperationException。

此类是Java Collections Framework的成员。


unmodifiableMap()

public static <K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m) {
        return new UnmodifiableMap<>(m);
}

该方法返回了一个map的不可修改的视图umap, 为用户提供了一种生成只读容器的方法。如果尝试修改该容器umap, 将会抛出UnsupportedOperationException异常。

Collections.unmodifiableMap 能做什么?
我们在类中经常需要返回一个集合,比如mapA。如果直接返回成员变量mapA本身的话,相当于对外暴露了集合的引用,外部就可以随意修改该对象的集合,该对象可能对修改都一无所知,属性却发生了变化。
一种解决方法,就是将该集合修饰为private, 在返回集合的方法中采用Collections.unmodifiableMap(mapA),返回mapA的一个不可变的副本。且该方法要比我们自己去复制一个副本效率要高。

Collections.unmodifiableMap 构造的map真的不可修改吗?
遗憾的是该结论并不总是成立。对于map<key, value>中的内容value, unmodifiableMap仅仅保证的是它的引用不能被修改,如果value对应的是一个可变对象,那么该unmodifiableMap的内容还是可变的。
比如Map<String, Student>中Student的某个字段的内容,还是可以修改的。

Collections.unmodifiableMap
https://www.cnblogs.com/dreamysmurf/p/6253737.html


emptyList()

public static final <T> List<T> emptyList() {
    return (List<T>) EMPTY_LIST;
}

返回空的列表(不可变的)。此列表是可序列化的。
以下示例演示了获得空列表的类型安全方式:
List<String> s = Collections.emptyList();

实现注意事项:实现此方法不需要为每次调用创建一个单独的 List 对象。使用此方法的开销与使用 like-named 字段相当。(与此方法不同,该字段不提供类型安全。)


sort()

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    list.sort(null);
}

里面也是用了 Arrays 的 sort

default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

reverse()

public static void reverse(List<?> list)
反转指定列表中元素的顺序。
此方法以线性时间运行。

  • 参数:list - 元素要被反转的列表。
  • 抛出: UnsupportedOperationException - 如果指定列表或其列表迭代器不支持 set 操作。

shuffle()乱序

rotate()旋转

package crunchify.com.tutorial;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author Crunchify.com
 * Best way to Shuffle, Reverse, Copy, Rotate and Swap List in Java8
 *
 */

public class CrunchifyJava8ShuffleList {
    public static void main(String[] args) {

        List<String> CrunchifyList = new ArrayList<String>();

        CrunchifyList.add("Google");
        CrunchifyList.add("Facebook");
        CrunchifyList.add("Twitter");
        CrunchifyList.add("Snap Inc");
        CrunchifyList.add("Crunchify LLC");
        CrunchifyList.add("TechCrunch");
        CrunchifyList.add("Verizon");

        List<String> newList = new ArrayList<String>(CrunchifyList);

        // Print list before any operation.
        System.out.println("Printing result before any Operation: \t" + CrunchifyList);

        // Randomly permutes the specified list using a default source of randomness.
        Collections.shuffle(CrunchifyList);
        System.out.println("Printing result after shuffle(): \t" + CrunchifyList);

        // Reverses the order of the elements in the specified list.
        Collections.reverse(CrunchifyList);
        System.out.println("Printing result after reverse(): \t" + CrunchifyList);

        // Copies all of the elements from one list into another.
        Collections.copy(newList, CrunchifyList);
        System.out.println("Printing result after copy(): \t\t" + newList);

        // Rotates the elements in the specified list by the specified distance.
        Collections.rotate(newList, 2);
        System.out.println("Printing result after rotate(): \t" + newList);

        // Returns the number of elements in this list.
        System.out.println("Printing total count using size(): \t" + newList.size());

        // Swaps the elements at the specified positions in the specified list.
        Collections.swap(newList, 2, 4);
        System.out.println("Printing result after swap(): \t\t" + newList);
    }

}

max() 最大值

public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)

min() 最小值

public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)


Arrays工具类

java.util.Arrays

public class Arrays
extends Object

此类包含用来操作数组(比如排序和搜索)的各种方法。此类还包含一个允许将数组作为列表来查看的静态工厂。

除非特别注明,否则如果指定数组引用为 null,则此类中的方法都会抛出 NullPointerException。

此类中所含方法的文档都包括对实现 的简短描述。应该将这些描述视为实现注意事项,而不应将它们视为规范 的一部分。实现者应该可以随意替代其他算法,只要遵循规范本身即可。(例如,sort(Object[]) 使用的算法不必是一个合并排序算法,但它必须是稳定的。)

此类是Java Collections Framework的成员。


asList() 数组转集合

public static <T> List<T> asList(T... a)
返回一个受指定数组支持的固定大小的列表。(对返回列表的更改会“直接写”到数组。)此方法同 Collection.toArray() 一起,充当了基于数组的 API 与基于 collection 的 API 之间的桥梁。返回的列表是可序列化的,并且实现了 RandomAccess。
此方法还提供了一个创建固定长度的列表的便捷方法,该列表被初始化为包含多个元素:
List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
参数:a - 支持列表的数组。
返回:指定数组的列表视图。

List<Integer>转int[]数组

// List<Integer> 转 int[]
@Test
public void testIntegerListToIntArray() {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    int[] intArray = list.stream().mapToInt(Integer::intValue).toArray();
    System.out.println(Arrays.toString(intArray));
}

int[]数组转List<Integer>集合

注意:没有从 int[] 转换为 List<Integer> 的快捷方式,因为 Arrays.asList 无法自动装箱拆箱,所以
Arrays.asList(new int[] {1,2,3}); 只会创建一个 List<int[]> ,而不是期望的 List<Integer>

// int[] 数组转 List<Integer>
@Test
public void testIntArrayToIntegerList() {
    int[] nums = {1, 2, 3, 4, 5};
//        List<Integer> integerList = Arrays.asList(nums); // 编译错误,因为 Arrays.asList 无法自动装箱
    List list = Arrays.asList(nums); // 错误,结果是 List<int[]>
    List list2 = Arrays.asList(new int[] {1, 2, 3}); // 错误,结果是 List<int[]>
    List<Integer> list3 = Arrays.stream(nums).boxed().collect(Collectors.toList()); // 正确
    System.out.println(list);
    System.out.println(list2);
    System.out.println(list3);
}

结果

[[I@2d2ffcb7]
[[I@762ef0ea]
[1, 2, 3, 4, 5]

sort(int[])

public static void sort(int[] a)

public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

对指定的 int 型数组按数字升序进行排序。
参数:a - 要排序的数组

实现

  • JSE1.6及之前,该排序算法是一个经过调优的快速排序法,改编自 Jon L. Bentley 和 M. Douglas McIlroy 合著的 Engineering a Sort Function, Software-Practice and Experience Vol. 23(11) P. 1249-1265 (November 1993)。此算法在许多数据集上提供 O(n log(n)) 性能,这导致其他快速排序会降低二次型性能。
  • JSE1.7及之后,默认是一个由 Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch 实现的 Dual-Pivot快速排序。此算法在许多数据集上提供 O(n log(n)) 性能,这导致其他快速排序会降低二次型性能。并且比传统的单pivot快速排序要快。

toString()数组转字符串

// String[]
String[] array = new String[] {"John", "Mary", "Bob"};
System.out.println(Arrays.toString(array));

// int[]
int[] intArray = { 7, 9, 5, 1, 3 };
System.out.println(Arrays.toString(intArray));

Java打印二维数组

比如有二维数组,直接打印出的是数组地址

int[][] test = {{0, 1, 2}, {2, 1}, {1}};
System.out.println(Arrays.toString(test));

正确的打印方式是

// 打印int二位数组
public static void printInt2DArray(int[][] input) {
    for (int[] row : input) {
        System.out.println(Arrays.toString(row));
    }
}

fill()填充数组

public static void fill(int[] a, int val)
数组所有元素填充为 val
public static void fill(int[] a, int fromIndex, int toIndex, int val)
数组从下标 fromIndex(包括) 到 toIndex(不包括)填充为 val

@Test
public void testFill() {
    int[] intArray = new int[10];
    char[] charArray = new char[13];
    Arrays.fill(intArray, 33);
    Arrays.fill(charArray, 'z');
    System.out.println(Arrays.toString(intArray));
    System.out.println(Arrays.toString(charArray));
}

结果:

[33, 33, 33, 33, 33, 33, 33, 33, 33, 33]
[z, z, z, z, z, z, z, z, z, z, z, z, z]

Map

Java8遍历Map的几种方式

map.forEach()推荐

map.forEach((k, v) -> System.out.println("key:value = " + k + ":" + v));

map.keySet().forEach()

map.keySet().forEach(key -> System.out.println("map.get(" + key + ") = " + map.get(key)));

map.entrySet().forEach()

// java8之前
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
    System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}

// java8
map.entrySet().forEach(entry -> System.out.println("key:value = " + entry.getKey() + ":" + entry.getValue()));

map.values().forEach()

map.values().forEach(System.out::println);

示例

public class LambdaMap {

    private Map<String, Object> map = new HashMap<>();

    @Before
    public void initData() {
        map.put("key1", "value1");
        map.put("key2", "value2");
        map.put("key3", "value3");
        map.put("key4", 4);
        map.put("key5", 5);
        map.put("key5", 'h');
    }


    /**
     * 遍历Map的方式一
     * 通过Map.keySet遍历key和value
     */
    @Test
    public void testErgodicWayOne() {
        System.out.println("---------------------Before JAVA8 ------------------------------");
        for (String key : map.keySet()) {
            System.out.println("map.get(" + key + ") = " + map.get(key));
        }
        System.out.println("---------------------JAVA8 ------------------------------");
        map.keySet().forEach(key -> System.out.println("map.get(" + key + ") = " + map.get(key)));
    }

    /**
     * 遍历Map第二种
     * 通过Map.entrySet使用Iterator遍历key和value
     */
    @Test
    public void testErgodicWayTwo() {
        System.out.println("---------------------Before JAVA8 ------------------------------");
        Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, Object> entry = iterator.next();
            System.out.println("key:value = " + entry.getKey() + ":" + entry.getValue());
        }
        System.out.println("---------------------JAVA8 ------------------------------");
        map.entrySet().iterator().forEachRemaining(item -> System.out.println("key:value=" + item.getKey() + ":" + item.getValue()));
    }

    /**
     * 遍历Map第三种
     * 通过Map.entrySet遍历key和value,在大容量时推荐使用
     */
    @Test
    public void testErgodicWayThree() {
        System.out.println("---------------------Before JAVA8 ------------------------------");
        for (Map.Entry<String, Object> entry : map.entrySet()) {
            System.out.println("key:value = " + entry.getKey() + ":" + entry.getValue());
        }
        System.out.println("---------------------JAVA8 ------------------------------");
        map.entrySet().forEach(entry -> System.out.println("key:value = " + entry.getKey() + ":" + entry.getValue()));
    }

    /**
     * 遍历Map第四种
     * 通过Map.values()遍历所有的value,但不能遍历key
     */
    @Test
    public void testErgodicWayFour() {
        System.out.println("---------------------Before JAVA8 ------------------------------");
        for (Object value : map.values()) {
            System.out.println("map.value = " + value);
        }
        System.out.println("---------------------JAVA8 ------------------------------");
        map.values().forEach(System.out::println); // 等价于map.values().forEach(value -> System.out.println(value));
    }

    /**
     * 遍历Map第五种
     * 通过k,v遍历,Java8独有的
     */
    @Test
    public void testErgodicWayFive() {
        System.out.println("---------------------Only JAVA8 ------------------------------");
        map.forEach((k, v) -> System.out.println("key:value = " + k + ":" + v));
    }
}

Java8中Map的遍历方式总结
https://www.cnblogs.com/homeword/p/7396414.html


interface Map<K,V>

java.util.Map<K,V>
public interface Map<K,V>

将键映射到值的对象。一个映射不能包含重复的键;每个键最多只能映射到一个值。
Map 接口提供三种collection 视图,允许以键集、值集或键-值映射关系集的形式查看某个映射的内容。

嵌套类Map.Entry<K,V>

public static interface Map.Entry<K,V>
映射项(键-值对)。Map.entrySet 方法返回映射的 collection 视图,其中的元素属于此类。获得映射项引用的唯一 方法是通过此 collection 视图的迭代器来实现。

put()

V put(K key, V value)
将指定的值与此映射中的指定键关联(可选操作)。
如果此映射以前包含一个该键的映射关系,则用指定值替换旧值(当且仅当 m.containsKey(k) 返回 true 时,才能说映射 m 包含键 k 的映射关系)。
返回:以前与 key 关联的值,如果没有针对 key 的映射关系,则返回 null。(如果该实现支持 null 值,则返回 null 也可能表示此映射以前将 null 与 key 关联)。

get()

V get(Object key)
返回指定键所映射的值;如果此映射不包含该键的映射关系,则返回 null。
更确切地讲,如果此映射包含满足 (key==null ? k==null : key.equals(k)) 的键 k 到值 v 的映射关系,则此方法返回 v;否则返回 null。(最多只能有一个这样的映射关系)。
如果此映射允许 null 值,则返回 null 值并不一定 表示该映射不包含该键的映射关系;也可能该映射将该键显示地映射到 null。使用 containsKey 操作可区分这两种情况。

keySet()

Set<K> keySet()
返回此映射中包含的键的 Set 视图。该 set 受映射支持,所以对映射的更改可在此 set 中反映出来,反之亦然。如果对该 set 进行迭代的同时修改了映射(通过迭代器自己的 remove 操作除外),则迭代结果是不确定的。set 支持元素移除,通过 Iterator.remove、Set.remove、removeAll、retainAll 和 clear 操作可从映射中移除相应的映射关系。它不支持 add 或 addAll 操作。
例:

public void doSomethingWithMap(Map<String,Object> map) {
  for (String key : map.keySet()) {
    Object value = map.get(key);
    // ...
  }
}

entrySet()

Set<Map.Entry<K,V>> entrySet()
返回此映射中包含的映射关系的 Set 视图。该 set 受映射支持,所以对映射的更改可在此 set 中反映出来,反之亦然。如果对该 set 进行迭代的同时修改了映射(通过迭代器自己的 remove 操作,或者通过对迭代器返回的映射项执行 setValue 操作除外),则迭代结果是不确定的。set 支持元素移除,通过 Iterator.remove、Set.remove、removeAll、retainAll 和 clear 操作可从映射中移除相应的映射关系。它不支持 add 或 addAll 操作。
例:

public void doSomethingWithMap(Map<String,Object> map) {
  for (Map.Entry<String,Object> entry : map.entrySet()) {
    String key = entry.getKey();
    Object value = entry.getValue();
    // ...
  }
}

putIfAbsent

default V putIfAbsent(K key, V value)
Since: 1.8
如果 map 中不存在 key,则放入 put(k,v) 并返回 null, 如果 map 中已存在 key, 则直接返回其 value
返回:如果 map 中存在 key,返回之前的 value, 如果 map 中不存在 key, 返回 null

default V putIfAbsent(K key, V value) {
    V v = get(key);
    if (v == null) {
        v = put(key, value);
    }
    return v;
}

getOrDefault(k, defaultValue)

default V getOrDefault(Object key, V defaultValue)
Since: 1.8
返回 key 对应的 value, 如果 map 中没有 key, 则返回 defaultValue

default V getOrDefault(Object key, V defaultValue) {
    V v;
    return (((v = get(key)) != null) || containsKey(key))
        ? v
        : defaultValue;
}

比如算法题中常见的用 map 统计数组元素出现次数:

// 统计数组中各个元素的出现次数  数值 -> 次数
int[] nums = {1,1,2,2,3,3,4};
Map<Integer, Integer> map = new HashMap<>();
for (int n : nums) {
    map.put(n, map.getOrDefault(n, 0) + 1);
}

class HashMap<K,V>

java.util.HashMap<K,V>
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键
HashMap不是线程同步的。

HashMap 的实例有两个参数影响其性能:初始容量 和加载因子。容量 是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。

构造方法
public HashMap()
构造一个具有*默认初始容量 (16) 和默认加载因子 (0.75) *的空 HashMap。


class LinkedHashMap<K,V>

java.util.LinkedHashMap<K,V>
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

顾名思义LinkedHashMap是比HashMap多了一个链表的结构,与HashMap相比LinkedHashMap维护的是一个具有双重链表的HashMap。
LinkedHashMap支持两种排序:一种是插入排序,一种是使用排序,最近使用的会移至尾部例如 M1 M2 M3 M4,使用M3后为 M1 M2 M4 M3了,LinkedHashMap输出时其元素是有顺序的,而HashMap输出时是随机的。
如果Map映射比较复杂而又要求高效率的话,最好使用LinkedHashMap。
LinkedHashMap不是线程同步的,多线程访问的话可能会造成不同步,所以要用Collections.synchronizedMap来包装一下,从而实现同步。

如果需要输出的顺序和输入时的相同,那么就选用LinkedHashMap。


Collection 接口

java.util.Collection

public interface Collection<E>
extends Iterable<E> {
}

toArray() 集合转数组

<T> T[] toArray(T[] a);

【强制】使用集合转数组的方法,必须使用集合的 toArray(T[] array),传入的是类型完全一样的数组,大小就是list.size()
使用toArray带参方法,入参分配的数组空间不够大时,toArray方法内部将重新分配内存空间,并返回新数组地址;
如果数组元素个数大于实际所需,下标为[ list.size() ]的数组元素将被置为null,其它数组元素保持原值
因此最好将方法入参数组大小定义与集合元素个数一致。
正例:

List<String> list = new ArrayList<String>(2);
list.add("guan");
list.add("bao");
String[] array = new String[list.size()];
array = list.toArray(array);

反例:
直接使用toArray无参方法存在问题,此方法返回值只能是 Object[] 类,若强转其它类型数组将出现ClassCastException错误。


List

list转逗号分隔字符串

String s = list.stream().map(Object::toString).collect(Collectors.joining(","));
String citiesCommaSeparated = cities.stream().map(String::toUpperCase).collect(Collectors.joining(","));
String citiesCommaSeparated = String.join(",", Arrays.asList("Milan", "London", "New York", "San Francisco"));

遍历时remove防止fail-fast

使用Iterator的remove方法移除当前对象,如果使用List的remove方法,则同样会出现ConcurrentModificationException

/**
 * 使用Iterator的方式也可以顺利删除和遍历
 */
public void iteratorRemove() {
    List<Student> students = this.getStudents();
    System.out.println(students);
    Iterator<Student> stuIter = students.iterator();
    while (stuIter.hasNext()) {
        Student student = stuIter.next();
        if (student.getId() % 2 == 0)
            stuIter.remove();//这里要使用Iterator的remove方法移除当前对象,如果使用List的remove方法,则同样会出现ConcurrentModificationException
    }
    System.out.println(students);
}

如何正确遍历删除List中的元素,你会吗?
http://elim.iteye.com/blog/1523785

Java遍历HashMap,Set, List, ArraryList 删除(remove)或者修改
http://justcode.ikeepstudying.com/2017/06/java%E9%81%8D%E5%8E%86hashmapset-list-arrarylist-%E5%B9%B6%E4%BF%AE%E6%94%B9remove%E6%88%96%E8%80%85%E4%BF%AE%E6%94%B9/


interface List<E>

java.util.List
public interface List<E> extends Collection<E>

有序的 collection(也称为序列)。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引(在列表中的位置)访问元素,并搜索列表中的元素。

size()

int size()
返回列表中的元素数。如果列表包含多于 Integer.MAX_VALUE 个元素,则返回 Integer.MAX_VALUE

isEmpty()

boolean isEmpty()
如果列表不包含元素,则返回 true

contains()

boolean contains(Object o)
如果列表包含指定的元素,则返回 true。更确切地讲,当且仅当列表包含满足 (o==null ? e==null : o.equals(e)) 的元素 e 时才返回 true。

addAll()

boolean addAll(Collection<? extends E> c)
添加指定 collection 中的所有元素到此列表的结尾,顺序是指定 collection 的迭代器返回这些元素的顺序(可选操作)。

  • 抛出:
    • UnsupportedOperationException - 如果列表不支持 addAll 操作
    • ClassCastException - 如果指定 collection 的元素的类不允许它添加到此列表
    • NullPointerException - 如果指定的 collection 包含一个或多个 null 元素,并且该列表不允许 null 元素,或者指定的 collection 为 null
    • IllegalArgumentException - 如果指定 collection 的元素的某些属性不允许它添加此列表

retainAll()

boolean retainAll(Collection<?> c)
仅保留此集合中也包含在集合c中的元素(可选操作),即从当前集合中删除不在集合c中的元素,即当前集合和参数c集合取交集。

https://docs.oracle.com/javase/9/docs/api/java/util/List.html#retainAll-java.util.Collection-


class ArrayList<E>

java.util.ArrayList
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable

List 接口的大小可变数组的实现。
每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素,其容量也自动增长。并未指定增长策略的细节,因为这不只是添加元素会带来分摊固定时间开销那样简单。

注意,此实现不是同步的。如果多个线程同时访问一个 ArrayList 实例,而其中至少一个线程从结构上修改了列表,那么它必须 保持外部同步。(结构上的修改是指任何添加或删除一个或多个元素的操作,或者显式调整底层数组的大小;仅仅设置元素的值不是结构上的修改。)


class LinkedList<E>

java.util.LinkedList
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable

List 接口的链接列表实现。
除了实现 List 接口外,LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
此类实现 Deque 接口,为 add、poll 提供先进先出队列操作,以及其他堆栈和双端队列操作。
注意,此实现不是同步的。


比较与排序

Comparable

Comparable 是排序接口。

若一个类实现了 Comparable 接口,就意味着“该类支持排序”。
即然实现 Comparable 接口的类支持排序,假设现在存在“实现 Comparable 接口的类的对象的 List 列表(或数组)”,则该 List 列表(或数组)可以通过 Collections.sort(或 Arrays.sort)进行排序。

此外,“实现 Comparable 接口的类的对象”可以用作“有序映射(如 TreeMap )”中的键或“有序集合( TreeSet )”中的元素,而不需要指定比较器。

Comparable 接口仅仅只包括一个函数,它的定义如下:

package java.lang;

public interface Comparable<T> {
    public int compareTo(T o);
}

假设我们通过 x.compareTo(y) 来“比较x和y的大小”。 若返回“负数”,意味着“x比y小”;返回“零”,意味着“x等于y”;返回“正数”,意味着“x大于y”。
总之就是,x-y<0 则 x<y

Comparator

Comparator 是比较器接口。

我们若需要控制某个类的次序,而该类本身不支持排序(即没有实现 Comparable 接口);那么,我们可以建立一个“该类的比较器”来进行排序。这个“比较器”只需要实现 Comparator 接口即可。

也就是说,我们可以通过“实现 Comparator 类来新建一个比较器”,然后通过该比较器对类进行排序。

package java.util;

@FunctionalInterface
public interface Comparator<T> {

    int compare(T o1, T o2);

    boolean equals(Object obj);

    default Comparator<T> reversed() {
        return Collections.reverseOrder(this);
    }
    ... ...
}

1、 若一个类要实现 Comparator 接口:它一定要实现 compare(T o1, T o2) 函数,但可以不实现 equals(Object obj) 函数。
为什么可以不实现 equals(Object obj) 函数呢? 因为任何类,默认都是已经实现了equals(Object obj)的。 Java 中的一切类都是继承于 java.lang.Object,在 Object.java 中实现了 equals(Object obj) 函数;所以,其它所有的类也相当于都实现了该函数。

2、 int compare(T o1, T o2) 是“比较o1和o2的大小”。返回“负数”,意味着“o1比o2小”;返回“零”,意味着“o1等于o2”;返回“正数”,意味着“o1大于o2”。


compareTo方法要满足哪些性质

compareTo 需要满足以下性质:
自反性:x,y 的比较结果和 y,x 的比较结果相反。
传递性:x>y,y>z,则 x>z。
对称性:x=y,则 x,z 比较结果和 y,z 比较结果相同。


整数List倒序排序

可用 lambda 表达式代替 Comparator 接口,例如
倒序排序:
Collections.sort(list, (a, b) -> b - a);
等价于
Colletions.reverse(list);

@Test
public void testReverseCompare() {
    List<Integer> integerList = Lists.newArrayList(123, 12345, 5, 556, 12);
    Collections.sort(integerList);
    System.out.println(integerList);
    Collections.sort(integerList, (str1, str2) -> str2.compareTo(str1));
//        Collections.reverse(integerList);
    System.out.println(integerList);
}

字符串数组按长度倒序

@Test
public void testStringArrayReverse() {
    List<String> list = Arrays.asList("dbb", "sdddfd", "a", "bb", "ddd", "ssssssss");
    // 按字符串长度倒序排序
    Collections.sort(list, (str1, str2) -> str2.length() - str1.length());
    System.out.println(list);

    String[] stringArray = new String[] {"dbb", "sdddfd", "a", "bb", "ddd", "ssssssss"};
    // 按字符串长度倒序排序
    Arrays.sort(stringArray, (str1, str2) -> str2.length() - str1.length());
    System.out.println(Arrays.toString(stringArray));
}

结果

[ssssssss, sdddfd, dbb, ddd, bb, a]
[ssssssss, sdddfd, dbb, ddd, bb, a]

List<List>按内部List串接后的字典序排序

@Test
public void testListCompare() {
    // 将 List<List> 按内部 List 串接后的字符串排序
    ArrayList<ArrayList<Integer>> listList = Lists.newArrayList();
    listList.add(Lists.newArrayList(789));
    listList.add(Lists.newArrayList(456, 123));
    listList.add(Lists.newArrayList(456));
    listList.add(Lists.newArrayList(789, 123));
    listList.add(Lists.newArrayList(789, 456));
    listList.add(Lists.newArrayList(123));
    listList.add(Lists.newArrayList(789, 456, 123));
    Collections.sort(listList, (list1, list2) -> {
        String str1 = list1.stream().map(String::valueOf).collect(Collectors.joining(""));
        String str2 = list2.stream().map(String::valueOf).collect(Collectors.joining(""));
        return str2.compareTo(str1);
    });
    listList.forEach(System.out::println);
}

结果

[789, 456, 123]
[789, 456]
[789, 123]
[789]
[456, 123]
[456]
[123]

按二维数组中每个一维数组的第一个元素升序排序

按二维数组中每个一维数组的第一个元素升序排序

// 按二维数组中每个一维数组的第一个元素升序排序
@Test
public void test2DArraySort() {
    int[][] arrays = {{8,10,2}, {15,18,2,1}, {1,3}, {3,2,6}};
    Arrays.sort(arrays, (array1, array2) -> array1[0] - array2[0]);
//        Arrays.sort(arrays, Comparator.comparingInt(array -> array[0]));
    for (int[] array: arrays) {
        System.out.print(Arrays.toString(array) + " ");
    }
}

结果:

[1, 3] [3, 2, 6] [8, 10, 2] [15, 18, 2, 1]

上一篇 Java-日期

下一篇 Java-正则表达式

阅读
评论
6,277
阅读预计27分钟
创建日期 2015-08-08
修改日期 2020-04-25
类别
标签

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论