8.4 List和Set

1、List

ArrayList，它长于随机访问元素，但是在List的中间插入和移除元素时较慢。 LinkedList，它通过代价较低的在List中间进行的插入和删除操作，提供了优化的顺序访问。LinkedList在随机访问方面相对比较慢。

（1）ArrayList 方法有：

构造示例： List l3 = new ArrayList(); List<Integer> l1 = new ArrayList<Integer>(); List<MyClass> l2 = new ArrayList<MyClass>(); // 方法应用例子：------------------------------------------------- List<String> ls = new ArrayList<String>(); //增加元素 ls.add("s1");ls.add("s2"); 。。。 ls.add(3, new String("s8")); // 将新元素放在下标为3处 ls.addAll(2, ls2); 将表ls2添加到ls中下标为2的开始位置 ls.addAll(ls2); 直接加到末尾 // 删除元素 ls.remove(s6); copy.remove(2); // Remove by index ls.removeAll(ls2); 将ls2中的所有从ls中移去 // 清空表 ls.clear(); // 修改元素 ls.set(1, new String("s9")); 修改下标为1的元素 // 获取某位置元素 String s3 = ls.get(2); //下标为2的元素 // 求某元素的下标，如果不在线性表中返回-1 ls.indexOf(s3) // 求子线性表 List<String> sub = ls.subList(1, 4); 下标从1到3的子表 // 是否为空 ls.isEmpty() // 是否包含某对象 String s6 = new String("s6"); System.out.println(ls.contains(s6)); System.out.println(ls.containsAll(sub)); 判断sub是否是ls的子表，此处不考虑顺序只考虑是否包含元素 // 将表赋值给另外一个表 List<String> copy = new ArrayList<String>(ls); // 数组转化为List ls = Arrays.asList("as", "ad"); 或int[] a_int = { 1, 2, 3, 4 }; List a_int_List = Arrays.asList(a_int); // List转化为数组 Object[] o = ls.toArray(); String[] str = ls.toArray(new String[0]); // 表仅保留交集的元素 ls1.retainAll(ls2); ls1仅保留ls1与ls2的交集元素 // 表的排序 Collections.sort(ls); // 表里元素之间顺序随机化，即打乱 Collections.shuffle(ls); 或 Random rand = new Random(47); Collections.shuffle(sub, rand);

（2）LinkedList LinkedList也实现了基本的List接口，但是在某些方面它要比ArrayList要高效一些，如插入和移除操作，但是在随机访问方面要逊色一些。 LinkedList还有一个重要的作用是用来实现栈、队列以及双端队列等数据结构中的一些基本结构

方法： 因为LinkedList也实现了List接口，当然上面ArrayList中的方法也都包含，除此之外它还包含如下方法

List l = new LinkedList(); List<String> ls = new LinkedList<String>(); 其他代码略

栈和队列

Stack在新版本的Java中是不推荐使用，有了LinkedList，我们完全可以自己很快的写一个，因为说到底栈无非就是操作受限的链表。

import java.util.LinkedList; public class Stack<T> { private LinkedList<T> storage = new LinkedList<T>(); public void push(T v) { storage.addFirst(v); } public T peek() { return storage.getFirst(); } public T pop() { return storage.removeFirst(); } public boolean empty() { return storage.isEmpty(); } public String toString() { return storage.toString(); } }

队列：

在java5中新增加了java.util.Queue接口 LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用

import java.util.LinkedList; import java.util.Queue; public class QueueTest { public static void main(String[] args) { Queue<String> queue = new LinkedList<String>(); //添加元素 queue.offer("a"); queue.offer("b"); // 遍历队列 for(String q : queue){ System.out.println(q); } //队列中删除并返回第一个元素 System.out.println("poll="+queue.poll()); // 下面两个方法均是访问第一个元素 System.out.println("element="+queue.element()+queue.peek()); } }

2、Set

Set不保存重复元素。 Set实现：HashSet和TreeSet，而在HashSet的基础上还实现了一个LinkedHashSet。

HashSet：拥有最快的查询速度，存入HashSet的元素必须定义hashCode()方法TreeSet：保持元素处于排序状态，底层为树结构。使用它可以从Set中提取有序的序列。元素必须实现Comparable接口LinkedHashSet：以插入顺序保持元素，用迭代器进行遍历时会按照插入时的顺序显示，但也必须定义hashCode()方法

Set具有与Collection完全一样的接口，因此没有任何额外的功能， 而ArrayList和LinkedList具有额外的功能。

import java.util.*; // 下面的SetType，HashType，TreeType都是自己定义的类 class SetType { int i; public SetType(int n) { i = n; } public boolean equals(Object o) { return o instanceof SetType && (i == ((SetType) o).i); } public String toString() { return Integer.toString(i); } } class HashType extends SetType { public HashType(int n) { super(n); } public int hashCode() { return i; } } class TreeType extends SetType implements Comparable<TreeType> { public TreeType(int n) { super(n); } public int compareTo(TreeType arg) { return (arg.i < i ? -1 : (arg.i == i ? 0 : 1)); } } // 测试代码 public class TypesForSets { static <T> Set<T> fill(Set<T> set, Class<T> type) { try { for (int i = 0; i < 10; i++) set.add(type.getConstructor(int.class).newInstance(i)); } catch (Exception e) { throw new RuntimeException(e); } return set; } static <T> void test(Set<T> set, Class<T> type) { fill(set, type); fill(set, type); // Try to add duplicates fill(set, type); System.out.println(set); } public static void main(String[] args) { // 系统的容器有HashSet，LinkedHashSet，TreeSet三种，要想容器起到作用，需要：HashSet及LinkedHashSet容器里放的类有hashCode()方法，TreeSet里放的类实现Comparable接口。而自己定义的三个类中，HashType类有hashCode()方法，TreeType类实现Comparable接口。 test(new HashSet<HashType>(), HashType.class); test(new LinkedHashSet<HashType>(), HashType.class); test(new TreeSet<TreeType>(), TreeType.class); // 下面的几个测试失败因为容器里没有放对应的类 test(new HashSet<SetType>(), SetType.class); test(new HashSet<TreeType>(), TreeType.class); test(new LinkedHashSet<TreeType>(), TreeType.class); try { test(new TreeSet<SetType>(), SetType.class); } catch (Exception e) { System.out.println(e.getMessage()); } } } /* [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] [8, 9, 2, 1, 6, 7, 1, 5, 8, 7, 8, 0, 5, 5, 2, 0, 1, 6, 4, 7, 3, 2, 9, 0, 6, 9, 4, 4, 3, 3] [0, 9, 4, 0, 8, 5, 6, 7, 7, 9, 8, 6, 1, 4, 1, 3, 3, 7, 6, 2, 0, 4, 3, 5, 9, 2, 8, 5, 1, 2] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9] java.lang.ClassCastException: SetType cannot be cast to java.lang.Comparable *///:~

参考：http://www.cnblogs.com/xltcjylove/p/3790064.html