[数据结构与算法]JAVA day18，19 单列集合Collection：List（ArrayList，LinkedList，Vector）、Queue（Deque）、Set(HashSet，TreeSet)

Collection单列集合

所有超级接口：

Iterable<E>

所有已知子接口：

BeanContext, BeanContextServices, BlockingDeque<E>, BlockingQueue<E>, Deque<E>, List<E>, NavigableSet<E>, Queue<E>, Set<E>, SortedSet<E>

一、List

所有已知实现类：

AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector

1.特点

• 它是?个元素存取有序的集合。例如，存元素的顺序是 11 、 22 、 33 。那么集合中，元素的存储就是按照11 、 22 、 33 的顺序完成的）
• 集合中允许有null值
• 它是?个带有索引的集合，通过索引就可以精确的操作集合中的元素（与数组的索引是?个道

  理）
• 集合中可以有重复的元素，通过元素的 equals ?法，来?较是否为重复的元素。

2.?常用API

?List作为Collection集合的?接?，不但继承了Collection接?中的全部?法，?且还增加了?些根据元素索引来操作集合的特有?法，如下：

3.List接口的实现类

1.ArrayList

java.util.ArrayList 集合数据存储的结构是数组结构。元素增删慢，查找快，由于?常开发中使?最多的功能为查询数据、遍历数据，所以 ArrayList 是最常?的集合。

特点：

1.按照顺序排列，每个元素都带有标号；2.除了有标号是连续的，内存中的物理空间也是连续的。

底层使用的数据结构：顺序结构；

顺序结构底层实现：数组；

优缺点：查询快；增删慢，内存的物理空间是连续的，利用不到碎片空间。

import java.util.ArrayList;
// ArrayList是子接口List的实现类之一
public class ArrayListDemo01 {
    public static void main(String[] args) {
        ArrayList<Object> a = new ArrayList<Object>();
        a.add(2);
        a.add(23);
        System.out.println(a);//[2, 23]

        //1.向集合(this)中末尾添加元素
        a.add(2,55);
        System.out.println(a);//[2, 23, 55]

        //2.向集合index的位置中插入obj元素
        a.add(1,"哈哈");
        System.out.println(a);//[2, 哈哈, 23, 55]

        //3.删除指定位置(index)上的元素，并且返回删除的元素
        //比如删除下标是2的元素
        a.remove(2);
        System.out.println(a);//[2, 哈哈, 55]

        //4.删除第一个指定元素(obj)
        a.remove(0);
        System.out.println(a);//[哈哈, 55]

        //5.替换指定位置上的元素，替换成obj，并且返回被替换的元素
        a.set(1,"嘻嘻");
        System.out.println(a);//[哈哈, 嘻嘻]

        //6.从集合中获得指定位置(index)的元素
        //比如下标是1位置上的元素
        System.out.println(a.get(1));//嘻嘻

        //7.获得集合中的元素个数
        System.out.println(a.size());//2

        //8.判断集合中是否存在指定元素obj
        System.out.println(a.contains("嘻嘻"));//true

        //9.判断集合是否为空：没有有效元素是空
        System.out.println(a.isEmpty());//false

        // 10.打印出在集合中的有效元素
        for (Object obj : a) {
            if (a.isEmpty() == false && obj != null){
                System.out.println(a);
            }
        }

    }
}

2.LinkedList

特点：

1.LinkedList是双向链表
2.链表是内存中固定顺序,但是他的物理空间不连续
3.没有下标
4.所有节点的访问,都必须通过头节点(next)/尾节点(pre)
5.head(头节点): 只存next,不存data；last(尾节点): 只存pre,不存data
6.head.next = null -> 空链表；last.pre = null -> 空链表

底层使用的数据结构：链式结构；

链式结构底层实现：链表：节点（data数据 + next下一个节点的引用）；

优缺点：插入删除效率高，不需要连续的内存物理空间，空间利用率高；查找慢

特有API：(只要带有First/last的方法)

/*
    LinkedList常用API:
         void addFirst(E e)
          void addLast(E e)
           E getFirst()
            E getLast()
             E remove(int index)
             E removeFirst()
              E removeLast()
 */

import java.util.LinkedList;

public class LinkedApiDemo {
    public static void main(String[] args) {
       LinkedList<Object> linked =  new LinkedList<>();

       linked.add(23);
       linked.add(15.6);
       linked.add(0,false);
       System.out.println(linked);//[false, 23, 15.6]
       linked.addFirst(true);
       System.out.println(linked);//[true, false, 23, 15.6]
       linked.addLast(888);
       System.out.println(linked);//[true, false, 23, 15.6, 888]
       linked.removeFirst();
       System.out.println(linked);//[false, 23, 15.6, 888]
       Object o =  linked.getLast();
        System.out.println(o);//888


    }
}

3.Vector

Vector 类可以实现可增长的对象数组。与数组一样，它包含可以使用整数索引进行访问的组件。但是，Vector 的大小可以根据需要增大或缩小，以适应创建 Vector 后进行添加或移除项的操作。

特点：

特点跟ArrayList 一样，特别的是，Vector上带有线程同步锁(synchronized)，所以是线程安全的，效率低。

tips：ArrayList 和 Vector的区别
? ? ? ?? ?a.线程安全区别
? ? ? ?? ? ?ArrayList不带锁,线程不安全,效率高
? ? ? ?? ? ?Vector带锁,线程安全,效率低
? ? ? ?? ?b.扩容问题区别
? ? ? ?? ? ?ArrayList扩容为原容量的1.5倍
? ? ? ?? ? ?Vector扩容为原容量的2倍

二、Queue

Queue也是Collection接口的子接口，在处理元素前用于保存元素的 collection。除了基本的 Collection 操作外，队列还提供其他的插入、提取和检查操作。每个方法都存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）。插入操作的后一种形式是用于专门为有容量限制的 Queue 实现设计的；在大多数实现中，插入操作不会失败。

1.特点

1.先进先出；后进后出。2.队列也是线性结构,有顺序的,但是本身没有标号。

底层使用的数据结构：顺序（数组）或者链式（链表）；

2.API

offer() - 向队列尾部追加元素
poll() - 向队列头部取出元素(出队列)
peek() - 向队列头部获取元素(队列不变)

import java.util.LinkedList;
import java.util.Queue;

//队列 offer peek poll
public class QueueDemo {
    public static void main(String[] args) {
        //创建对象Queue底层实现是链表
        Queue<Object> qu =  new LinkedList<>();

        //添加offer

        qu.offer(12);
        qu.offer("哈哈哈");
        qu.offer(true);
        System.out.println(qu);//[12, 哈哈哈, true]

        //查看peek（出列）
        Object pe = qu.peek();
        System.out.println(pe);//12
        System.out.println(qu);//[12, 哈哈哈, true]

        //poll(出列)
        Object po =qu.poll();
        System.out.println(po);//12
        System.out.println(qu);//[哈哈哈, true]



    }


}

3.子接口（Deque）

Deque 是 Queue接口的子接口，一个线性 collection，支持在两端插入和移除元素。名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。

特点：

1.作为双端队列 - 先进先出
? ?? ??? ? ?作为栈 - 先进后出
2.只能通过方法区分是队列/栈

底层使用的数据结构：顺序（数组）或者链式（链表）；

常用API：

作为双端队列:
? ?? ??? ? ? 带有First()/Last()
作为栈:
? ?? ??? ??? ?push() - 压栈
? ?? ??? ??? ?pop() - 弹栈

双端队列代码

import java.util.Deque;
import java.util.LinkedList;

//双端队列
public class DequeDemo {
    public static void main(String[] args) {
        Deque<Object> de = new LinkedList<>();

        de.offer("55");
        de.offerFirst(false);//头添加
        de.offer(666);
        System.out.println(de);//[false, 55, 66]
        de.offerLast(889);//尾添加
        System.out.println(de);//[false, 55, 666, 889]

        Object pe = de.peek();
        System.out.println(pe);//false
        Object pe1 = de.peekFirst();
        System.out.println(pe1);//false
        Object pe2 = de.peekLast();
        System.out.println(pe2);//889
        System.out.println(de);//[false, 55, 666, 889]

        Object po = de.poll();
        System.out.println(po);//false
        System.out.println(de);//[55, 666, 889]
        Object po1 = de.pollFirst();
        System.out.println(po1);//55
        System.out.println(de);//[666, 889]
        Object po2 = de.pollLast();
        System.out.println(po2);//889
        System.out.println(de);//[666]

    }
}

栈代码：

import java.util.Deque;
import java.util.LinkedList;


public class DequeStackDemo {
    public static void main(String[] args) {
        Deque<Object> des = new LinkedList<>();
        //存入 实现栈 先进后出
        des.push(222);
        des.push(999);
        System.out.println(des);
        //[999, 222]
        des.pop();
        System.out.println(des);
        //[222]


    }
}

三、Set

所有已知子接口：

NavigableSet<E>, SortedSet<E>

所有已知实现类：

AbstractSet, ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSet, JobStateReasons, LinkedHashSet, TreeSet

1.特点

• API跟Collection里的完全一致。
• Set集合截取Map(映射表)。
• Set集合的物理空间是不连续的，添加没有顺序(不是随机，是不按添加的顺序输出)
• Set集合不允许有重复值，值是唯一的。使用equals()判断元素是否重复。
• Set集合允许null值。

2.Set接口的实现类

1.HashSet

HashSet 是根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能。保证元素唯?性的?式依赖于： hashCode 与 equals ?法。

特点：

a.调用自身的hashCode()计算存储位置
b.如果该位置上没有元素,则直接存入
c.如果该位置上有元素,则调用equals()和该位置上所有元素进行比较
d.如果相同,则覆盖原来的数据
e.如果不相同,则存入该链表的末尾

HashSet所使用的数据结构：哈希表（Hash表）

在 JDK1.8 之前，哈希表底层采?数组 + 链表实现，即使?链表处理冲突，同? hash 值的链表都存 储在?个链表?。但是当位于?个桶中的元素较多，即hash 值相等的元素较多时，通过 key 值依次查找的效率较低。?JDK1.8 中，哈希表存储采?数组 + 链表 + 红?树实现，当链表?度超过阈（8 ）时，将链表转换为红?树，这样??减少了查找时间。

简单的来说，哈希表是由数组 +链表+ 红?树（ JDK1.8 增加了红?树部分）实现的，如下图所示。

?

代码举例：?

import java.util.HashSet;
import java.util.Set;

public class HashSetDemo {
    public static void main(String[] args) {
        Set<Object> set = new HashSet<>();
        set.add(222);
        set.add("困死了");
        set.add(2.13);
        set.add(null);//允许空值

        System.out.println(set);//[null, 2.13, 困死了, 222] ---> 输出无序
        set.add(2.13);
        System.out.println(set);//[null, 2.13, 困死了, 222]  ---> 且不允许有重复值 因为判断了两值相等，所以覆盖了

        //原因
        //HashSet --- > Set 底层实现其实是数组加链表实现的 在数组的每个位置上 都存在一个链表的结构
        //存数据时，先计算数据的hashcode的值用来判断存放位置。
        //然后判断该位置上是否存在元素，如果没有，存入链表；如果有，需要equals判断
        //两个值是否相等，不相等则存入链表末端，相等则覆盖之前的值。

        set.remove(null);
        System.out.println(set);//[2.13, 困死了, 222]

    }
}

?HashSet存储?定义类型元素

import java.util.Objects;

//实体类
public class Student {
    private String name;
    private int age;
    public Student() {
    }

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (o == null || getClass() != o.getClass())
            return false;
        Student student = (Student) o;
        return age == student.age &&
                Objects.equals(name, student.name);
    }
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public String toString() {
        return "Student{"+ name + ","+ age+"}";
    }
}

import java.util.HashSet;

//测试存放数据的原因 hashcode equals
public class HashSetTest {
    public static void main(String[] args) {
        Student stu1 = new Student("lucy",15);
        Student stu2 = new Student("tony",15);
        Student stu3 = new Student("jack",13);
        HashSet<Student> set = new HashSet<Student>();
        set.add(stu1);
        set.add(stu2);
        set.add(stu3);
        System.out.println(set);//重写了toString方法
        //[Student{lucy,15}, Student{tony,15}, Student{jack,13}]

        set.remove(stu1);
        System.out.println(set);

    }
}

2.TreeSet

在说这个实现类之前，先学习一下树，跟比较器。

树

树：树是n个结点的有限集合，有且仅有一个根结点，其余结点可分为m个根结点的子树。

?叉树?：?binary tree?，是每个结点不超过?2?的有序?树（?tree?）?。?叉树是每个节点最多有两个?树的树结构。顶上的叫根结点，两边被称作?“?左?树?”?和?“?右?树?”?。

满二叉树：高度为h，由2^h-1个节点构成的二叉树称为满二叉树。

完全二叉树：完全二叉树是由满二叉树而引出来的，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

平衡二叉树：当且仅当两个子树的高度差不超过1时，这个树是平衡二叉树。（同时是排序二叉树）平衡二叉树，又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。

?二叉树的遍历

前序遍历（前根遍历）：根——>左——>右

中序遍历（中根遍历）：左——>根——>右

后序遍历（后根遍历）：左——>右——>根

?较器

基于 TreeMap 的 NavigableSet 实现。使用元素的自然顺序对元素进行排序，或者根据创建 set 时提供的 Comparator 进行排序，具体取决于使用的构造方法。

代码：

import java.util.TreeSet;

public class TreeSet01 {
    public static void main(String[] args) {
        //默认排序方法是中序排序
        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(555);
        treeSet.add(2);
        treeSet.add(5);
        System.out.println(treeSet);//[2, 5, 555]


        /*
            泛型是String:
                1.默认按照字典顺序排序
                2.如果相同字母,但是长度不同,短在前,长在后
                3.全小写或者是全大写,按字典顺序排序,首字母相同查看第二位
         */
        TreeSet<String> tree1  = new TreeSet<>();
        tree1.add("marry");
        tree1.add("marry");//一样的值就进行覆盖
        tree1.add("lucy");
        tree1.add("tom");
        tree1.add("jack");
        tree1.add("rose");
        System.out.println(tree1);
        //[jack, lucy, marry, rose, tom]

        /*
            1.大写字母在前,小写字母在后
              因为ASCII码值对应的 A = 65  a = 97
        */
        TreeSet<Character> tree2 = new TreeSet<>();
        tree2.add('a');
        tree2.add('b');
        tree2.add('B');
        tree2.add('A');
        System.out.println(tree2);
        //[A, B, a, b]

    }
}

自定义tree

import java.util.Comparator;

/*
    自定义实现二叉树
 */
public class Tree<T> {

    //内部类
    private class Node<T>{
        private T data;
        private Node left;
        private Node right;

        Node(T data){
            this.data = data;
        }
    }

    //根节点:
    private Node<T> root;

    //定义一个内部的方法 - 递归方式实现
    private void addNode(Node node,T t){
        if(((Comparable)t).compareTo(node.data) > 0){
            if (node.right == null){
                node.right = new Node<T>(t);
                return;
            }
            addNode(node.right,t);
        }else if(((Comparable)t).compareTo(node.data) < 0){
            if (node.left == null){
                node.left = new Node<T>(t);
                return;
            }
            addNode(node.left,t);
        }
    }

    //add()
    public void add(T t){
        if (root == null){
            root = new Node<>(t);
            return;
        }
        addNode(root,t);
    }
    //在内部看来: 对每一个节点进行遍历 - 递归
    private void travelNode(Node node){
        if(node.left != null){
            travelNode(node.left);
        }
        System.out.println(node.data);
        if(node.right != null){
            travelNode(node.right);
        }
    }

    //对插入的数据进行遍历 - 按照从小到大的顺序进行排序
    public void travel(){
        //对数据进行排序
        travelNode(root);
    }

    /*public void add(T t){
        //判断是否存在根节点
        if(root == null){
            root = new Node<T>(t);
            return;
        }
        Node node = root;
        Node parentNode;
        while (true){
            parentNode = node;
            //((Comparable)t).compareTo()
            if(((Comparable)t).compareTo(node.data) > 0){
                //存在根节点的右边
                node = node.right;
                if(node == null){
                    parentNode = new Node(t);
                    return;
                }
            }else if(((Comparable)t).compareTo(node.data) < 0){
                //存在根节点的左边
                node = node.left;
                if(node == null){
                    parentNode = new Node(t);
                    return;
                }
            }
        }
    }*/
}


public class TreeSetTest {
    public static void main(String[] args) {
        Tree tree = new Tree();
        tree.add(55);
        tree.add(222);
        tree.add(888);
        tree.travel();
        /*
        * 55
          222
          888
        * */
        
        
    }
}

比较器：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

/*
* java的排序
* 1.自然排序（默认排序）
* 2.自定义排序
*
* 数组Arrays
* Arrays.sort---->默认排序
*
* 集合
* List
* Collections.sort ---->默认排序
*
* Queue Stark 队列跟栈 就不能进行排序 因为位置都是固定的
*
* Set
* TreeSet set = new TreeSet(); ----> 无参就是默认排序
*
* Map
* TreeMap() map = new TreeMap();----> 无参就是默认排序
* */
public class ComparatorDemo01 {
    public static void main(String[] args) {
        //对数组排序 默认排序
        Integer[] arr = {2,66,9,33};
        System.out.println("排序前"+Arrays.toString(arr));//排序前[2, 66, 9, 33]
        Arrays.sort(arr);
        System.out.println("排序后"+Arrays.toString(arr));//排序后[2, 9, 33, 66] 默认从小到大

        //自定义排序
        Arrays.sort(arr , new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return 0;
            }

        });

        //对List集合进行排序 默认
       ArrayList<Integer> list =  new ArrayList<>();
       list.add(5);
       list.add(5);
       list.add(4);
       list.add(598);
       System.out.println("排序前"+list);//排序前[5, 5, 4, 598]
        Collections.sort(list);
        System.out.println("排序后"+list);//排序后[4, 5, 5, 598]

        //自定义list排序 就要用到比较器了
        //对List集合进行排序 - 指定比较器
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                /*return 0; 不进行排序*/
                //return o1 - o2;//正序
                return o2 - o1;//倒序
            }
        });
        System.out.println(list);


    }
}

tree比较器：

import java.util.Objects;

/*
    自定义实现类
    解决办法:
      1.在自定义的类中实现Comparable接口
      2.重写Comparable中的compareTo()
 */
public class User implements Comparable<User>{
    private String name;
    private int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public User() {
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "User{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        return age == user.age && Objects.equals(name, user.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    /*
        return 0: 会认为传进来的所有对象都是同一个
        二叉树: 中序遍历
            左 < 根  < 右
        compareTo():
            this 和 u对比规则:
                this 比 u 小, 则返回负数
                this 和 u 相同,则返回0 -> 不存入
                this 比 u 大, 则返回正数

            this - u  --> 正序
            u -> this --> 倒序

     */
    @Override//重写的比较方法
    public int compareTo(User u) {
        //this(User) 和 u(User)
        //强制类型转换
        //return 0;
        //默认方式:从小到大进行排序 - 正序
        //return this.getAge() - u.getAge();
        if(u.getAge() != this.getAge()){
            return u.getAge() - this.getAge();//倒序
        }
        // 从大到小进行排序 - 倒序
        return u.getName().compareTo(this.getName());

    }
}



import java.util.Comparator;
import java.util.TreeSet;

/*
    对自定义的类进行排序
        自然排序 Comparable
        自定义排序(指定排序) Comparator
 */
public class TreeSetDemo {
    public static void main(String[] args) {
        TreeSet<User> tree = new TreeSet<>();
        User u1 = new User("张三", 18);
        User u2 = new User("李四", 18);
        User u3 = new User("小黄", 16);
        User u4 = new User("小红", 21);
        tree.add(u1);
        tree.add(u2);
        tree.add(u3);
        tree.add(u4);
        /* 如果自定义的类没有实现Comparable接口
            则会:ClassCastException - 类型转换异常
            解决办法:
                1.在自定义的类中实现Comparable接口
                2.重写Comparable中的compareTo()
         */
        System.out.println(tree);

        TreeSet<User> tree2 = new TreeSet<>(new Comparator<User>() {
            @Override
            public int compare(User o1, User o2) {
                return o1.getName().compareTo(o2.getName());
                /*o1.getAge() - o2.getAge()*/
            }
        });

    }
}