14.集合、常见的数据结构

集合

概念

Java中的集合就是一个容器，用来存放Java对象。

集合在存放对象的时候，不同的容器，存放的方法实现是不一样的，

Java中将这些不同实现的容器，往上抽取就形成了Java的集合体系。

Java集合中的根接口：Collection 和 Map

Collection是一个单值集合，每次添加只能存放一个值进去

Map是一个双值集合，每次添加可以添加一对数据到Map

Collection介绍

1.由来

Java是一个面向对象语言，将来肯定会处理对象。

为了方便操作多个对象，就需要把这些对象存储起来，存储多个对象，就需要一个容器

Java之前提供了数组、StringBuffer这两个容器，但是他们用来存放对象不是很方便

所以，Java就提供了Collection集合。

2.数组和集合的区别

长度区别：

数组的长度是固定的

集合的长度可变的

内容不同：

数组存储的是同一种数据类型

集合可以存储不同类型的元素

元素的数据类型不同：

数组可以存放基本类型、引用类型

集合只能存放引用类型，如果存放int类型，默认会被提升为Integer

3.Collection的发展

集合可以存放多个元素，但是在存放的时候也会有不同的需求，

比如：多个元素不能重复、多个元素按照规则排序...

根据不同的需求，Java中提供了很多的集合类

每个集合根据需求，使用不同的数据结构，不管什么数据结构，他们都有一些共同的功能，

比如可以添加、删除、判断...

所以Collection其实就是把不同集合类的共同内容不断往上抽取，

最终，形成了集合的继承体系。

Collection中子接口、子类比较多，只需要掌握常用的一些集合类

Collection

--Set

--HashSet

--TreeSet

--LinkedHashSet

--List

--ArrayList

--LinkedList

4.Collection的功能

（1）添加

boolean add(E e)

确保此集合包含指定的元素（可选操作）。

boolean addAll(Collection<? extends E> c)

将指定集合中的所有元素添加到此集合（可选操作）。

（2）获取

Iterator<E> iterator()

返回此集合中的元素的迭代器。

（3）判断

boolean contains(Object o)

如果此集合包含指定的元素，则返回 true 。

boolean containsAll(Collection<?> c)

如果此集合包含指定集合中的所有元素，则返回true。

boolean isEmpty()

如果此集合不包含元素，则返回 true 。

（4）大小

int size()

返回此集合中的元素数。

（5）移除

void clear()

从此集合中删除所有元素（可选操作）。

boolean remove(Object o)

从该集合中删除指定元素的单个实例（如果存在）（可选操作）。

boolean removeAll(Collection<?> c)

删除指定集合中包含的所有此集合的元素（可选操作）。

default boolean removeIf(Predicate<? super E> filter)

删除满足给定谓词的此集合的所有元素。

package com.day14.collet;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

public class CollectionDemo01 {
    public static void main(String[] args) {
        //多态的方式创建Collection对象
        Collection c = new ArrayList();

        //调用方法

        //添加
        c.add(123);
        c.add("hello");
        c.add(new Person("jack"));
        c.add(2.58);
        c.add(null);
        c.add("hello");
        System.out.println(c);

        //判断包含
        boolean b1 = c.contains("hello");
        System.out.println(b1);
        //判断是否为空
        boolean b2 = c.isEmpty();
        System.out.println(b2);

        //大小
        System.out.println(c.size());

        //        //移除
        //        c.remove("hello");//移除指定内容
        //        System.out.println(c);
        //
        //        c.clear();
        //        System.out.println(c);//清除全部

        System.out.println("---------------------");
        //遍历 获取
        ArrayList arrayList =(ArrayList) c;
        for (int i = 0; i < arrayList.size(); i++) {
            System.out.println(arrayList.get(i));
        }
        System.out.println("---------------------");
        //增强for
        for (Object o : c){
            System.out.println(o);
        }
        System.out.println("---------------------");
        //iterator
        Iterator iterator = c.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }

        //创建一个指定存储类型的集合
        //指定之后，这个集合中只能存放String
        Collection<String> c1 = new ArrayList();

        c1.add("hello");
        //c1.add(123);
        c1.add("world");
        c1.add("world");
        c1.add("java");

        System.out.println("---------------------");
        //遍历
        for (String s : c1) {
            System.out.println(s);
        }
        System.out.println("---------------------");
        //迭代器遍历
        Iterator<String> iterator1 = c1.iterator();
        while (iterator1.hasNext()){
            System.out.println(iterator1.next());
        }
    }
}

Collection中迭代器原理 iterator()

1，iterator() 方法，继承自Iterable接口，这个接口主要用来规定对于迭代获取的规则接口

2， Iterator<T> iterator(); 这个方法的返回值是一个 Iterator对象

Iterator也是一个接口，提供了两个抽象方法，分别是hasNext() 和 Next()方法

3，当我们使用多态创建Collection对象，

Collection<String> c1 = new ArrayList();

然后使用c1调用iterator()方法做迭代的时候，实际上调用的是ArrayList()中重写的iterator()方法

ArrayList的iterator()方法，重写之后，返回了 new Itr(); 也就Itr是一个类，并且这个类一定是Iterator接口的实现类

往下看，发现，在ArrayList内部声明了一个内部类，Itr 并且实现了Iterator接口，重写了 hasNext() 和 Next()方法

hasNext()方法是在判断，cursor是否移动最后了

next()方法，是在以数组下标的方式取出元素，并返回，同时给cursor做增加(往后移动)

常见的数据结构

将来，不同的集合

栈结构：先进后出，入口和出口在同一侧

队列结构：先进先出，入口和出口不在同一侧

数组结构：存放元素通过下标来存放，获取元素通过下标获取

查询快：数组中的元素存放是连续的，通过数组的下标快速找到指定的元素

增删慢：数组的长度是固定的，增删的时候，其实是在做数组复制

数组做增删操作：

1.先创建一个新数组，然后将老数组的内容复制到新数组中

2.再往新数组中添加内容

3.删除则是往新数组中复制指定的内容

链表结构：链表中的每个元素，称为一个节点，就是一个类 Node类

一个节点中，包含一个数据区，还有两个指针区，就是类的属性

特点：

查询慢：查询元素需要一个个往下遍历获取，需要遍历的次数比较多

增删快：增删元素的时候，只需要修改节点中的引用地址就行了

单向链表：节点中，只有一个地址，指向下个地址

双向链表：节点中，有两个地址，一个指向上一个节点，一个指向下一个节点，

LinkedList使用了双向链表

package com.day14.jiegou;

public class Node {
    Node pri;
    Object data;
    Node next;

    public Node(Object data, Node addr) {
        this.data = data;
        this.next = addr;
    }

    public Node(Node pri, Object data, Node next) {
        this.pri = pri;
        this.data = data;
        this.next = next;
    }

    public void add(Object o){
        //第一次添加
        Node node = new Node(null,"hello",null );
        //第二次添加
        Node node1 = new Node(node,"java", null);
        node.next = node1;
        //第二次添加
        Node node2 = new Node(node1,"oracle", null);
        node1.next = node2;
    }

}

树结构：有多个节点组成，具有层次关系的一种结构。

特点：

因为组成的结构，看起来像一棵倒挂的树，也就是根朝上，叶子朝下，称为树结构。

每个节点都有零个或多个子节点，没有父节点的节点成为根节点，每个非根节点，有且仅有一个父节点，除了根节点之外，每个子结点都可以分为多个不相交的子树。将来应用中，主要使用的是二叉树。

二叉树特点：添加、删除元素都很快，查找也有很多算法优化，所以二叉树既有集合的好处，也有数组的好处，是两者的优化方案，处理大批量的动态数据应用很多。

二叉树扩展：平衡二叉树、红黑树、B+树..

B+树是MySQL底层索引结构

红黑树是HashMap的底层结构

红黑树特点：查询很快，查询叶子节点的最大次数和最小次数不超过2倍。节点是红色或者黑色，根节点是黑色，叶子节点是黑色，每个红色节点的子节点都是黑色，任何节点到每个叶子节点路径上的黑色节点数相同。

List接口

List集合的特点：有序（存取有序），可以重复的，可以有null，用户可以通过索引（类似于数组下标）精确地访问或者操作List中的元素

常用子类

ArrayList：底层数据结构是数组，线程不安全。

LinkedList：底层数据结构是双向链表，线程不安全

Vector：底层数据结构是数组，线程安全

ArrayList

构造方法

ArrayList()

构造一个初始容量为十的空列表。

ArrayList(Collection<? extends E> c)

构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。

ArrayList(int initialCapacity)

构造具有指定初始容量的空列表。

普通方法

boolean add(E e)

将指定的元素追加到此列表的末尾。

void add(int index, E element)

在此列表中的指定位置插入指定的元素。

E get(int index)

返回此列表中指定位置的元素。

int indexOf(Object o)

返回此列表中指定元素的第一次出现的索引，如果此列表不包含元素，则返回-1。

Iterator<E> iterator()

以正确的顺序返回该列表中的元素的迭代器。

ListIterator<E> listIterator()

返回列表中的列表迭代器（按适当的顺序）。

E remove(int index)

删除该列表中指定位置的元素。

boolean remove(Object o)

从列表中删除指定元素的第一个出现（如果存在）。

int size()

返回此列表中的元素数。

E set(int index, E element)

用指定的元素替换此列表中指定位置的元素。


package com.day14.list;

import com.day14.collet.Person;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;

public class ArrayListDemo {
    public static void main(String[] args) {
        //创建ArrayList对象
        ArrayList arrayList = new ArrayList();

        //调用方法
        //int size()
        //返回集合中的实际有几个元素。
        System.out.println(arrayList.size());

        //add()
        arrayList.add(123);
        arrayList.add("java");
        arrayList.add("hello");
        //arrayList.add(5,"oracle");//不能跳着添加
        arrayList.add(3,"oracle");
        arrayList.add(null);
        arrayList.add("java");
        System.out.println(arrayList);

        //get()
        System.out.println(arrayList.get(3));

        //set()
        arrayList.set(3,"spring");
        System.out.println(arrayList);

        //remove()
        arrayList.remove(2);
        System.out.println(arrayList);

        //通过iterator()方法遍历
        Iterator iterator = arrayList.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
        System.out.println("-------------------");
        //从前向后遍历
        ListIterator listIterator = arrayList.listIterator();
        while (listIterator.hasNext()){
            System.out.println(listIterator.next());
        }
        System.out.println("-------------------");
        //从后向前遍历
        while (listIterator.hasPrevious()){
            System.out.println(listIterator.previous());
        }


        //从中ArrayList存入对象
        ArrayList<Person> list = new ArrayList<>();

        Person p1 = new Person("jack");
        Person p2 = new Person("Tom");
        Person p3 = new Person("Lucy");

        list.add(p1);
        list.add(p2);
        list.add(p3);
        System.out.println(list);

    }
}

ArrayList源码分析

属性

默认初始容量

private static final int DEFAULT_CAPACITY = 10;

空实例对象共享的一个空数组

private static final Object[] EMPTY_ELEMENTDATA = {};

默认大小的空示例共享的一个共数组

用来区分传入具体的空间参数值的，这样可以知道将来存放第一个元素

之后，需要创建多大的空间

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

表示当前的arrayList对象

transient Object[] elementData;

当前arrayList中的真实空间大小

private int size;

1，new ArrayList 新创建的ArrayList对象就是空数组，容量为0

2，添加元素

public boolean add(E e) {

ensureCapacityInternal(size + 1); // Increments modCount!!

elementData[size++] = e;

return true;

}

add方法中，

第一步先调用 ensureCapacityInternal(size + 1);

第二步将传递进来的元素赋值到数组中的索引上

第三步返回结果true

private void ensureCapacityInternal(int minCapacity) {

ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

}

ensureCapacityInternal方法将传递过来的 size+1 在传入

calculateCapacity(elementData, minCapacity) 计算空间，计算完传入

ensureExplicitCapacity();

private static int calculateCapacity(Object[] elementData, int minCapacity) {

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

return Math.max(DEFAULT_CAPACITY, minCapacity);

}

return minCapacity;

}

calculateCapacity方法的判断是，将当前size+1之后，和默认的空间做比较

返回一个大的值，带入到ensureExplicitCapacity()方法中做计算

private void ensureExplicitCapacity(int minCapacity) {

modCount++;

// overflow-conscious code

if (minCapacity - elementData.length > 0)

grow(minCapacity);

}

ensureExplicitCapacity这个方法会将传递过来的空间值和当前数组的长度做比较

如果传递过来的空间值，比当前数组的长度大，就开始扩容

ArrayList的扩容方式：

如果默认创建无参构造ArrayList，开始是空数组，没有内容，空间为0，

当调用add方法加入第一个元素，通过计算空间方法，开始扩容，扩容到10，

当10个元素放满了，放入第11个元素，继续下次扩容，扩容为原来的1.5倍，

扩容的时候，其实是在使用数组复制功能。

ArrayList总结

ArrayList底层是一个可以动态扩容的数组，可以存放任意类型的元素，可以存放null元素，存取有序，元素可以重复，线程是不安全的。

创建无参构造ArrayList，默认初始空间为0，放入第一个元素，扩容为10，后续元素放满后，放入下一个元素会继续扩容，扩容1.5倍。

如果知道集合中存放的内容是多少，可以在初始化的时候，指定它的初始空间，可以提升效率。

效率上，非首尾元素增删慢，查询快，可以根据索引快速找到元素

ArrayList和Vector区别

Vector是一个比较老的集合类，jdk1.2

Vector底层也是数组，和ArrayList的最大区别就是，方法前面有Synchronized，

也就是方法是同步的，线程安全

相对来说，效率比ArrayList低

扩容上来说，Vector每次扩容2倍

LinkedList

说明：

1.底层是双向链表，可以存放任意类型元素

2.可以存放null元素，存取有序，元素可以重复，线程不安全

3.效率上，查询慢，增删快

4.结构上，它实现了Deque接口，因此LinkedList中还具有类似于操作队列和栈一样的方法

既然是链表，LinkedList中必然含有Node节点对象

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;

}

构造方法

LinkedList()

构造一个空列表。

普通方法

boolean add(E e)

将指定的元素追加到此列表的末尾。

void add(int index, E element)

在此列表中的指定位置插入指定的元素。

void addFirst(E e)

在该列表开头插入指定的元素。

void addLast(E e)

将指定的元素追加到此列表的末尾。

E get(int index)

返回此列表中指定位置的元素。

E getFirst()

返回此列表中的第一个元素。

E getLast()

返回此列表中的最后一个元素。

boolean offer(E e)

将指定的元素添加为此列表的尾部（最后一个元素）。

boolean offerFirst(E e)

在此列表的前面插入指定的元素。

boolean offerLast(E e)

在该列表的末尾插入指定的元素。

E pop()

从此列表表示的堆栈中弹出一个元素。

void push(E e)

将元素推送到由此列表表示的堆栈上。

package com.day14.list;

import java.util.LinkedList;
import java.util.ListIterator;

public class LinkedListDemo {
    public static void main(String[] args) {
        //创建一个LinkedList对象，存放String类型的元素
        LinkedList<String> linkedList = new LinkedList<>();

        //调用方法
        //add
        linkedList.add("hello");
        linkedList.add("world");
        linkedList.add("java");
        System.out.println(linkedList);

        linkedList.addFirst("spring");
        linkedList.addLast("mysql");
        System.out.println(linkedList);

        //push方法相当于addFirst
        linkedList.push("abc");
        linkedList.push("oracle");//往里加
        System.out.println(linkedList);

        //pop方法，弹栈，会将第一个元素取出
        linkedList.pop();//取出
        System.out.println(linkedList);

        //普通的get方法，并不会取出元素，只是获取了元素内容
        System.out.println(linkedList.get(1));
        System.out.println(linkedList);
        //getFirst获取第一个元素，不会将元素弹出
        System.out.println(linkedList.getFirst());
        System.out.println(linkedList);

        //遍历
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(1));
        }
        System.out.println("---------------------");
        for (String s : linkedList){
            System.out.println(s);
        }
        System.out.println("-----------------------");
        ListIterator<String> listIterator = linkedList.listIterator();
        while (listIterator.hasNext()){
            System.out.println(listIterator.next());
        }


    }
}