Java——容器(单例集合)(上)

一 容器介绍

• 容器，是用来容纳物体、管理物体。生活中,我们会用到各种各样的容器。如锅碗瓢盆、箱子和包等

• 程序中的“容器”也有类似的功能，用来容纳和管理数据。比如，如下新闻网站的新闻列表、教育网站的课程列表就是用“容器”来管理

• 视频课程信息也是使用“容器”来管理

• 计算机当中能够存储数据的位置有两个——>一个是磁盘，一个是内存

  • 磁盘是通过文件的形式存储数据的——>(永久存储，不会受到计算机的关闭而影响数据的)
  • 内存是临时存储——>关闭计算机后内存中是没有数据的
  • 容器存储的数据在内存当中

开发和学习中需要时刻和数据打交道，如何组织这些数据是我们编程中重要的内容。 我们一般通过“容器”来容纳和管理数据。事实上，我们前面所学的数组就是一种容器，可以在其中放置对象或基本类型数据。

数组的优势：是一种简单的线性序列，可以快速地访问数组元素，效率高。如果从查询效率和类型检查的角度讲，数组是最好的。

数组的劣势：不灵活。容量需要事先定义好，不能随着需求的变化而扩容。比如：我们在一个用户管理系统中，要把今天注册的所有用户取出来，那么这样的用户有多少个？我们在写程序时是无法确定的。因此，在这里就不能使用数组。

基于数组并不能满足我们对于“管理和组织数据的需求”，所以我们需要一种更强大、更灵活、容量随时可扩的容器来装载我们的对象。 这就是我们今天要学习的容器，也叫集合(Collection)。

二 容器结构

(三大接口)

1 结构图

​ List和Set都是单例接口，Map是双例接口(k,v)

2 单例集合

​ List——>相当于动态数组，Set——>相当于数学里的集合

3 双例集合

​ Map——>相当于数学里的函数，(mapping——>映射)

(单例集合)

三 (*)Collection接口

(12个方法)

(定义了单例集合的基本行为)

(接口中的方法很重要，注意返回值，和返回值类型)

Collection 表示一组对象，它是集中、收集的意思。Collection接口的两个子接口是List、Set接口。

Collection接口中定义的方法

由于List、Set是Collection的子接口，意味着所有List、Set的实现类都有上面的方法。

JDK8之后，Collection接口新增的方法（将在JDK新特性和函数式编程中介绍）：

四 (*)List接口

(6个方法)

(进一步细化了单例集合的存储特征)

(有序，可重复)

List接口特点

List是有序、可重复的容器。

有序：有序(元素存入集合的顺序和取出的顺序一致)。List中每个元素都有索引标记。可以根据元素的索引标记（在List中的位置）访问元素，从而精确控制这些元素。

可重复：List允许加入重复的元素。更确切地讲，List通常允许满足 e1.equals(e2) 的元素重复加入容器。

List接口中的常用方法

除了Collection接口中的方法，List多了一些跟顺序(索引)有关的方法，参见下表：

五(ArrayList)

1 ArrayList容器的基本操作

(Collection里面的方法——>添加，删除，转数组，长度，判空，清除)

(是List接口的实现类。是List存储特征的具体实现)

(底层是用数组实现的——>查询效率高，增删效率低，线程不安全)

(数组是有索引的查询快，但是插入和删除都要移动后面所有的数据慢)

(建议如果没有用到Arraylist里面的方法，最好用List接口类型定义引用)

实例化

​ 三种定义方式都可以

• 但是ArrayList继承了List接口和Collection接口，可以用包括自己的所有的方法（缺点就是以后换容器时候代码会作废）
• 用List虽然方法少，但是以后换容器的时候不用担心
• 用Collection定义方法太少，一般不会用

建议如果没有用到Arraylist里面的方法，最好用List接口类型定义引用

示例

public class ArrayListTest {
  public static void main(String[] args) {
    //实例化ArrayList容器
    List<String> list = new ArrayList<>();


    //添加元素
    boolean flag1 = list.add("xiaojia");
    boolean flag2 = list.add("xiaoliu");
    boolean flag3 = list.add("jia");
    boolean flag4 = list.add("jia");
    System.out.println(flag1+"\t"+flag2+"\t"+flag3+"\t"+flag4);
    
      
    //将ArrayList转换为数组——>Collextion里面的方法，和数组里面的方法
    Object[] objects = list.toArray();
    System.out.println(Arrays.toString(objects));
      
      
    
    //删除元素——>可以选择删除数据，或者位置
    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));
   }
}

2 ArrayList容器的索引操作

(6个操作)

(指定位置添加元素，获取元素，元素替换，删除指定位置，查找元素在容器(第一次)(最后一次)出现位置)

public class ArrayListTest2 {
  public static void main(String[] args) {
    //实例化容器
    List<String> list = new ArrayList<>();
    //添加元素
    list.add("jia");
    list.add("jiajia");


    //向指定位置添加元素
    list.add(0,"xiao");


    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("jjj");
    System.out.println(value3);


    System.out.println("查找元素最后一次出现的位置");
    list.add("jjj");
    for(String str:list){
      System.out.println(str);
     }
    int value4 = list.lastIndexOf("jjj");
    System.out.println(value4);
    
   }
}

3 ArrayList并集、交集、差集

(Collection里面的3个方法)

(addAll，retainAll，removeAll)

并集

 //并集操作：将另一个容器中的元素添加到当前容器中
    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);
     }

4 ArrayList源码分析

数组的初始化和扩容——>最开始数组长度为10，然后以1.5倍扩容，jdk1.8之后在操作数组时才初始化，节省内存

1

2

3

4

六 (Vector)

1 Vector容器的使用

(方法都加了同步检查——>“线程安全,效率低”)

(方法就增加了synchronized同步标记——>为了多线程的时候线程安全)

(单线程——>串型，多线程——>并型)

(使用容器的时候如果对线程安全有要求，大部分都使用ArrayList)

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);
     }
   }
}

2 Vector源码分析

(和ArrayList底层都是数组，区别就是线程安全和效率)

(数组初始化方式，ArrayList1.8之后是延迟初始化(调用时初始化)，在Vector中是立即初始化，长度也是10)

(ArrayList数组扩容1.5倍，Vector2倍扩容)

成员变量

/**
 * 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)

1 LinkedList容器介绍

(底层用双向链表实现的存储——>查询效率低，增删效率高，线程不安全)

双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前一个节点和后一个节点。 所以，从双向链表中的任意一个节点开始，都可以很方便地找到所有节点。

每个节点都应该有3部分内容：

class Node<E> {
        Node<E> previous;   //前一个节点
        E element;     //本节点保存的数据
        Node<E> next;        //后一个节点
}

List实现类的选用规则

如何选用ArrayList、LinkedList、Vector?

1. 需要线程安全时，用Vector。
2. 不存在线程安全问题时，并且查找较多用ArrayList（一般使用它）
3. 不存在线程安全问题时，增加或删除元素较多用LinkedList

2 LinkedList容器的使用

(LinkedList实现了List接口，所以LinkedList是具备List的存储特征的(有序，元素有重复))

(自己独有的8个方法)

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));
     }
   }
}

非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);
     }
   }
}

3 LinkedList源码分析

1 添加元素

节点类

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++;
}

//创建新节点，头尾指针指向

2 头尾添加元素

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++;
}

3 获取元素——>返回的不是对象是元素

/**
 * 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;
   }
}