List接口介绍
List接口特点
List是有序、可重复的容器。
有序：有序(元素存入集合的顺序和取出的顺序一致)。List中每个元 素都有索引标记。可以根据元素的索引标记（在List中的位置）访问 元素，从而精确控制这些元素。
可重复：List允许加入重复的元素。更确切地讲，List通常允许满足 e1.equals(e2) 的元素重复加入容器。
List接口中的常用方法
除了Collection接口中的方法，List多了一些跟顺序(索引)有关的方 法，参见下表：
ArrayList容器的基本使用
ArrayList是List接口的实现类。是List存储特征的具体实现。 ArrayList底层是用数组实现的存储。 特点：查询效率高，增删效率 低，线程不安全。
public class ArrayListTest { public static void main(String[] args) { //实例化ArrayList容器 List<String> list = new ArrayList<>(); //添加元素 boolean flag1 = list.add("oldlu"); boolean flag2 = list.add("itbz"); boolean flag3 = list.add("sxt"); boolean flag4 = list.add("sxt"); System.out.println(flag1+"\t"+flag2+"\t"+flag3+"\t"+flag4); //删除元素 boolean flag4 = list.remove("oldlu"); System.out.println(flag4); //获取容器中元素的个数 int size = list.size(); System.out.println(size); //判断容器是否为空 boolean empty = list.isEmpty(); System.out.println(empty); //容器中是否包含指定的元素 boolean value = list.contains("itbz"); System.out.println(value); //清空容器 list.clear(); Object[] objects1 = list.toArray(); System.out.println(Arrays.toString(objects1)); } }
ArrayList容器的索引操作
public class ArrayListTest2 { public static void main(String[] args) { //实例化容器 List<String> list = new ArrayList<>(); //添加元素 list.add("oldlu"); list.add("itbz"); //向指定位置添加元素 list.add(0,"sxt"); System.out.println("获取元素"); String value1 = list.get(0); System.out.println(value1); System.out.println("获取所有元素方式一"); //使用普通for循环 for(int i=0;i<list.size();i++){ System.out.println(list.get(i)); } System.out.println("获取所有元素方式二"); //使用Foreach循环 for(String str:list){ System.out.println(str); } System.out.println("元素替换"); list.set(1,"kevin"); for(String str:list){ System.out.println(str); } System.out.println("根据索引位置删除元素); String value2 = list.remove(1); System.out.println(value2); System.out.println("----------------"); for(String str:list){ System.out.println(str); } System.out.println("查找元素第一次出现的位置"); int value3 = list.indexOf("sxt"); System.out.println(value3); System.out.println("查找元素最后一次出现的位置"); list.add("sxt"); for(String str:list){ System.out.println(str); } int value4 = list.lastIndexOf("sxt"); System.out.println(value4); } }
ArrayList的并集、交集、差集
并集
//并集操作：将另一个容器中的元素添加到当前容器中 List<String> a = new ArrayList<>(); a.add("a"); a.add("b"); a.add("c"); List<String> b = new ArrayList<>(); b.add("a"); b.add("b"); b.add("c"); //a并集b a.addAll(b); for(String str :a){ System.out.println(str); }
交集
//交集操作：保留相同的，删除不同的 List<String> a1 = new ArrayList<>(); a1.add("a"); a1.add("b"); a1.add("c"); List<String> b1 = new ArrayList<>(); b1.add("a"); b1.add("d"); b1.add("e"); //交集操作 a1.retainAll(b1); for(String str :a1){ System.out.println(str); }
差集
//差集操作：保留不同的，删除相同的 List<String> a2 = new ArrayList<>(); a2.add("a"); a2.add("b"); a2.add("c"); List<String> b2= new ArrayList<>(); b2.add("b"); b2.add("c"); b2.add("d"); a2.removeAll(b2); for(String str :a2){ System.out.println(str); }
ArrayList源码分析
ArrayList底层是用数组实现的存储。
成员变量
/** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10; /** * The array buffer into which the elements of the ArrayList are stored. /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */ transient Object[] elementData; // nonprivate to simplify nested class access /** * The size of the ArrayList (the number of elements it contains). * * @serial */ private int size;
数组初始大小
/** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10;
添加元素
/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { ensureCapacityInternal(size + 1); //Increments modCount!! elementData[size++] = e; return true; }
判断数组是否扩容
//容量检查 private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } //容量确认 private void ensureExplicitCapacity(int minCapacity) { modCount++; //判断是否需要扩容，数组中的元素个数-数组长度，如果大于0表明需要扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); }
数组扩容
/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //扩容1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData,newCapacity); }
Vector容器的基本使用
Vector底层是用数组实现的，相关的方法都加了同步检查，因此“线 程安全,效率低”。 比如，indexOf方法就增加了synchronized同步 标记。
Vector的使用
Vector的使用与ArrayList是相同的，因为他们都实现了List接口， 对List接口中的抽象方法做了具体实现。
public class VectorTest { public static void main(String[] args) { //实例化Vector List<String> v = new Vector<>(); v.add("a"); v.add("b"); v.add("a"); for(int i=0;i<v.size();i++){ System.out.println(v.get(i)); } System.out.println("----------------------"); for(String str:v){ System.out.println(str); } } }
Vector源码分析
成员变量
/** * The array buffer into which the components of the vector are * stored. The capacity of the vector is the length of this array buffer, * and is at least large enough to contain all the vector's elements. * * <p>Any array elements following the last element in the Vector are null. * * @serial */ protected Object[] elementData; /** * The number of valid components in this {@code Vector} object. * Components {@code elementData[0]} through * {@code elementData[elementCount-1]} are the actual items. * * @serial */ protected int elementCount; /** * The amount by which the capacity of the vector is automatically * incremented when its size becomes greater than its capacity. If * the capacity increment is less than or equal to zero, the capacity * of the vector is doubled each time it needs to grow. * * @serial */ protected int capacityIncrement;
构造方法
public Vector() { this(10); }
添加元素
/** * Appends the specified element to the end of this Vector. * * @param e element to be appended to this Vector * @return {@code true} (as specified by {@link Collection#add}) * @since 1.2 */ public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; }
数组扩容
/** * This implements the unsynchronized semantics of ensureCapacity. * Synchronized methods in this class can internally call this * method for ensuring capacity without incurring the cost of an * extra synchronization. * * @see #ensureCapacity(int) */ private void ensureCapacityHelper(int minCapacity) { // overflow-conscious code //判断是否需要扩容，数组中的元素个数-数组长度，如果大于0表明需要扩容 if (minCapacity - elementData.length >0) grow(minCapacity); }
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //扩容2倍 int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }
LinkedList容器介绍
LinkedList底层用双向链表实现的存储。特点：查询效率低，增删 效率高，线程不安全。 双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两 个指针，分别指向前一个节点和后一个节点。 所以，从双向链表中 的任意一个节点开始，都可以很方便地找到所有节点。
LinkedList的存储结构图
每个节点都应该有3部分内容：
class Node<E> { Node<E> previous; //前一个节点 E element; //本节点保存的数据 Node<E> next; //后一个节点 }
List实现类的选用规则
如何选用ArrayList、LinkedList、Vector?
1 需要线程安全时，用Vector。
2 不存在线程安全问题时，并且查找较多用ArrayList（一般使用它）
3 不存在线程安全问题时，增加或删除元素较多用LinkedList
LinkedList容器的使用（List标准）
LinkedList实现了List接口，所以LinkedList是具备List的存储特征的 (有序，元素有重复)。
public class LinkedListTest { public static void main(String[] args) { //实例化LinkedList容器 List<String> list = new LinkedList<>(); //添加元素 boolean a = list.add("a"); boolean b = list.add("b"); boolean c = list.add("c"); list.add(3,"a"); System.out.println(a+"\t"+b+"\t"+c); for(int i=0;i<list.size();i++){ System.out.println(list.get(i)); } } }
LinkedList容器的使用（非List标准）
public class LinkedListTest2 { public static void main(String[] args) { System.out.println("-------LinkedList-------------"); //将指定元素插入到链表开头 LinkedList<String> linkedList1 = new LinkedList<>(); linkedList1.addFirst("a"); linkedList1.addFirst("b"); linkedList1.addFirst("c"); for (String str:linkedList1){ System.out.println(str); } System.out.println("----------------------"); //将指定元素插入到链表结尾 LinkedList<String> linkedList = new LinkedList<>(); linkedList.addLast("a"); linkedList.addLast("b"); linkedList.addLast("c"); for (String str:linkedList){ System.out.println(str); } System.out.println("---------------------------"); //返回此链表的第一个元素 System.out.println(linkedList.getFirst()); //返回此链表的最后一个元素 System.out.println(linkedList.getLast()); System.out.println("-----------------------"); //移除此链表中的第一个元素，并返回这个元素 linkedList.removeFirst(); //移除此链表中的最后一个元素，并返回这个元素 linkedList.removeLast(); for (String str:linkedList){ System.out.println(str); } System.out.println("-----------------------"); linkedList.addLast("c"); //从此链表所表示的堆栈处弹出一个元素,等效于removeFirst linkedList.pop(); for (String str:linkedList){ System.out.println(str); } System.out.println("-------------------"); //将元素推入此链表所表示的堆栈 这个等效于addFisrt(E e) linkedList.push("h"); for (String str:linkedList){ System.out.println(str); } } }
LinkedList的源码分析
添加元素
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
成员变量
transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last;
添加元素
/** * Appends the specified element to the end of this list. * * <p>This method is equivalent to {@link #addLast}. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link Collection#add}) */ public boolean add(E e) { linkLast(e); return true; } /** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
头尾添加元素
addFirst
/** * Inserts the specified element at the beginning of this list. * * @param e the element to add */ public void addFirst(E e) { linkFirst(e); } /** * Links e as first element. */ private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }
addLast
/** * Appends the specified element to the end of this list. * * <p>This method is equivalent to {@link #add}. * * @param e the element to add */ public void addLast(E e) { linkLast(e); } /** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
获取元素
/** * Returns the element at the specified position in this list. * * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { checkElementIndex(index); return node(index).item; }
private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
/** * Tells if the argument is the index of an existing element. */ private boolean isElementIndex(int index) { return index >= 0 && index < size; }
/** * Returns the (non-null) Node at the specified element index. */ Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
Set接口介绍
Set接口继承自Collection接口，Set接口中没有新增方法，它和 Collection接口保持完全一致。我们在前面学习List接口的使用方 式，在Set中仍然适用。因此，学习Set的使用将没有任何难度。
Set接口特点
Set特点：无序、不可重复。无序指Set中的元素没有索引，我们只 能遍历查找；不可重复指不允许加入重复的元素。更确切地讲，新 元素如果和Set中某个元素通过equals()方法对比为true，则只能保 留一个。
Set常用的实现类有：HashSet、TreeSet等，我们一般使用 HashSet。
HashSet容器的使用
HashSet是Set接口的实现类。是Set存储特征的具体实现。
public class HashSetTest { public static void main(String[] args) { //实例化HashSet Set<String> set = new HashSet<>(); //添加元素 set.add("a"); set.add("b1"); set.add("c2"); set.add("d"); set.add("a"); //获取元素,在Set容器中没有索引，所以没有对应的get(int index)方法 for(String str: set){ System.out.println(str); } System.out.println("--------------------"); //删除元素 boolean flag = set.remove("c2"); System.out.println(flag); for(String str: set){ System.out.println(str); } System.out.println("------------------------"); int size = set.size(); System.out.println(size); } }
HashSet存储特征分析
HashSet 是一个不保证元素的顺序且没有重复元素的集合，是线程 不安全的。HashSet允许有null 元素。
无序：
在HashSet中底层是使用HashMap存储元素的。HashMap底层使 用的是数组与链表实现元素的存储。元素在数组中存放时，并不是 有序存放的也不是随机存放的，而是对元素的哈希值进行运算决定 元素在数组中的位置。
不重复：
当两个元素的哈希值进行运算后得到相同的在数组中的位置时，会 调用元素的equals()方法判断两个元素是否相同。如果元素相同则 不会添加该元素，如果不相同则会使用单向链表保存该元素。
