欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java之List和Set

程序员文章站 2023-11-14 09:03:58
List、Set、数据结构、Collections 初次学习,涉及到List集合,Set集合和数据结构方面的一些知识,有错误还请批评指正 数据结构 数据存储的常用结构有:栈、队列、数组、链表和红黑树。 栈 先进后出(FILO). 队列 先进先出(FIFO). 数组 有序的元素序列,以索引访问.查询快 ......

List、Set、数据结构、Collections

初次学习,涉及到List集合,Set集合和数据结构方面的一些知识,有错误还请批评指正

数据结构

数据存储的常用结构有:栈、队列、数组、链表和红黑树。

先进后出(FILO).

队列

先进先出(FIFO).

数组

有序的元素序列,以索引访问.查询快,增删慢.

链表

链式结构,查询慢,增删快.通过地址进行连接.
单向链表:结点包括两个内容,一个是存储元素,一个是下一个元素的地址.
双向链表:结点包括3个部分,前一个元素的存储地址,当前结点存储的元素,后一个元素的存储地址

红黑树

二叉树,查询快.根节点的左边数据小于右边数据.

关于使用java具体实现上面的数据结构以后写,当前只需要了解一下他们的特性就可以.

List集合

java.util.List 接口继承自Collection 接口,是单列集合的一个重要分支,在List集合中允许出现重复的元素,所有的元素是以一种线
性方式进行存储的,在程序中可以通过索引来访问集合中的指定元素。另外,List集合还有一个特点就是元素有序,即元素的存入顺序和
取出顺序一致。(remove(Object obj)只能移除集合中第一个相同的元素)

List集合的特点:

  • 元素存储有序.
  • 可以存储重复元素
  • 有索引,可以通过索引来访问元素

常用的方法有(list的特有方法大都与索引相关):

  • public void add(int index, E element) : 将指定的元素,添加到该集合中的指定位置上。
  • public E get(int index) :返回集合中指定位置的元素。
  • public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素。
  • public E set(int index, E element) :用指定元素替换集合中指定位置的元素,返回值的更新前的元素。

List的子类

  • Vector : 线程安全相关
  • ArrayList : 底层数组实现
  • LinkedList : 链表实现
ArrayList

特有的常用方法:

  • int indexOf(Object o) 返回此列表中指定元素的第一次出现的索引,如果此列表不包含元素,则返回-1。
LinkedList

java.util.LinkedList 集合数据存储的结构是链表结构。方便元素添加、删除的集合。

  • 链表结构,查询慢,增删快
  • 包含大量操作首尾元素的方法

特有的方法:

  • public void addFirst(E e) :将指定元素插入此列表的开头。
  • public void addLast(E e) :将指定元素添加到此列表的结尾。
  • public void push(E e) :将元素推入此列表所表示的堆栈。等效于addFirst

  • public E getFirst() :返回此列表的第一个元素。
  • public E getLast() :返回此列表的最后一个元素。
  • E get(int index) 返回此列表中指定位置的元素。

  • public E removeFirst() :移除并返回此列表的第一个元素。
  • public E removeLast() :移除并返回此列表的最后一个元素。
  • public E pop() :从此列表所表示的堆栈处弹出一个元素。等效于removeFirst

  • int indexOf(Object o) 返回此列表中指定元素的第一次出现的索引,如果此列表不包含元素,则返回-1。
  • public boolean isEmpty() :如果列表不包含元素,则返回true。

Vector

这个在使用上和ArrayList基本没有区别,要注意的是二者的区别:

相同点:

  • 二者的底层实现都是数组结构.
    不同点:
  • Vector是与线程安全相关的,效率低下.ArrayList是线程不安全的,但是高效.

Set接口

java.util.Set接口特点:

  • 不允许存储重复元素
  • 无索引(意味着不能用普通for循环遍历)

HashSet

特点:

  • 不允许存储重复元素(存储相同的元素在Set中只能保存一个,但程序不会出错)
  • 无索引(意味着不能用普通for循环遍历)
  • 存储和读取元素无序(顺序可能不一致,在底层Set有他自己的排序规则)
  • 底层使用哈希表结构

哈希值:

  • int hashCode() 返回对象的哈希码值。

HashSet集合存储数据的结构:

  • jdk8之前是:数组 + 链表
  • jdk8之后是:数组 + 红黑树(二叉树)
  • 数组保存哈希值,存储元素时,哈希值相同的保存在数组的下方.
  • 当有多个元素的哈希值相同时(哈希冲突),这个时候保存的时候就会继续向下排列.具体的看下图.
  • 当有8个及以上的元素的哈希值相同,链式结构就会转化为红黑树结构.

HashSet如何保证元素唯一?与hashCode()方法与equals()方法相关:
Java之List和Set

举个例子:

public class HashSet {

    public static void main(String[] args) {
        Set<String> set = new java.util.HashSet<>();
        set.add(new String("abc"));
        set.add(new String("abc"));
        set.add("abc");
        set.add("重地");
        set.add("通话");

        System.out.println(set); // [重地, 通话, abc]
    }
}

重地和通话两个字符串比较特殊,二者的哈希值相同,从这个例子也可以看出String重写了hashCode()和equals()方法.

LinkedHashSet

特点:

  • 有序
  • 没有索引
  • 不可以存储重复元素
    哈希表(数组 + 链表/红黑树) + 链表(最后的链表是用来存储存入顺序的)

可变参数

定义格式:

修饰符 返回类型 方法名(参数类型...参数名){}

特点:

  • 可变参数底层实现是数组

注意事项:可变参数必须在参数列表的最后一位,一个参数列表只能有一个可变参数.

Collections

工具类特点:

  • 构造方法私有.
  • 所有的方法和属性静态,直接用类名调用.

常用方法:
public static

Comparatable与Comparator

Comparable:强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序,类的compareTo方法
被称为它的自然比较方法。只能在类中实现compareTo()一次,不能经常修改类的代码实现自己想要的排序。实现
此接口的对象列表(和数组)可以通过Collections.sort(和Arrays.sort)进行自动排序,对象可以用作有序映射中
的键或有序集合中的元素,无需指定比较器。
Comparator强行对某个对象进行整体排序。可以将Comparator 传递给sort方法(如Collections.sort或
Arrays.sort),从而允许在排序顺序上实现精确控制。还可以使用Comparator来控制某些数据结构(如有序set或
有序映射)的顺序,或者为那些没有自然顺序的对象collection提供排序。

二者都存在时,优先使用Comparator.

Comparatable的例子:

public class Student implements Comparable<Student>{

    private String name;

    private int age;

    public Student() {
    }

    public Student(String name, int age) {

        this.name = name;
        this.age = age;
    }

    public int getAge() {
        return age;
    }

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

    public String getName() {

        return name;
    }

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

    @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='" + name + '\'' +
                ", age=" + age +
                '}';
    }


    @Override
    public int compareTo(Student o) {
        return this.age - o.age;
    }
}

ArrayList<String> list = new ArrayList<>();

Collections.addAll(list,"迪丽热巴","郑爽","李溪芮");

System.out.println(list);

Collections.sort(list);

System.out.println(list);

Comparator的例子:

// 还是上面的实体类
ArrayList<Student> list = new ArrayList<>();

list.add(new Student("Silme",20));
list.add(new Student("Roke",19));
list.add(new Student("Aoke",19));
list.add(new Student("Robin",18));
System.out.println(list);
Collections.sort(list, new Comparator<Student>() {
    @Override
    public int compare(Student o1, Student o2) {
        // 年龄自然排序
        int flag = o1.getAge() - o2.getAge();
        // 年龄相同,按照姓名排序
        if(flag == 0){
            flag = o1.getName().charAt(0)- o2.getName().charAt(0);
        }
        return flag;
    }
});
System.out.println(list);