Java回顾数据结构

时间：2021-07-13作者：klpeng分类：Java技术浏览：110评论：0

数据结构

1.栈

2.队列

3.数组

4.链表

红黑树

List接口

java.util.List<E>接口 extends Collection<E>接口
    List接口的特点:
        1.是一个有序的集合:存储元素和取出元素的顺序是一致的  存储:123  取出:123
        2.允许存储重复的元素  add(10)  add(10)
        3.含有一些带索引的方法
    List接口中特有的含有索引的方法:
        void add(int index, E element)  :把元素插入到集合指定的索引处
        E get(int index)  获取指定索引处的元素
        E remove(int index)  移除并返回指定索引处的元素,返回的是被移除的元素
        E set(int index, E element)  替换并返回指定索引处的元素,返回被替换的元素
    注意:
        使用带索引的方法,必须防止索引越界异常(不要超出集合索引的使用范围:0---->长度-1)

List接口中的常用方法

public class Demo01List {
    public static void main(String[] args) {
        //创建List集合对象,并赋值
        List<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");
        list.add("aaa");
        list.add("ddd");         //  0    1    2    3    4
        System.out.println(list);//[aaa, bbb, ccc, aaa, ddd]

        /*
            void add(int index, E element)  :把元素插入到集合指定的索引处
         */
        //在索引2处添加一个元素"haha"
        list.add(2,"haha");     //           1   正确
        System.out.println(list);//[aaa, bbb,haha, ccc, aaa, ddd]

        //E get(int index)  获取指定索引处的元素
        String s1 = list.get(0);
        System.out.println("s1:"+s1);//aaa
        String s2 = list.get(3);
        System.out.println("s2:"+s2);//ccc
        //list.get(10);//IndexOutOfBoundsException: Index: 10, Size: 6

        /*
            E remove(int index)  移除并返回指定索引处的元素,返回的是被移除的元素
         */
        //删除集合中存储的第二个aaa  [aaa, bbb,haha, ccc, aaa, ddd]
        String s3 = list.remove(4);
        System.out.println("s3:"+s3);//s3:aaa
        System.out.println(list);//[aaa, bbb, haha, ccc, ddd]

        //E set(int index, E element)  替换并返回指定索引处的元素,返回被替换的元素
        //把2索引处的haha替换为呵呵
        String s4 = list.set(2, "呵呵");
        System.out.println("s4:"+s4);//s4:haha
        System.out.println(list);//[aaa, bbb, 呵呵, ccc, ddd]
        System.out.println("-------------------------------");
        //使用普通for循环遍历List集合
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
        //使用增强for循环遍历List集合
        System.out.println("-------------------------------");
        for (String s : list) {
            System.out.println(s);
        }
        System.out.println("-------------------------------");
        //使用迭代器遍历List集合
        Iterator<String> it = list.iterator();
        while (it.hasNext()){
            String s = it.next();
            System.out.println(s);
        }
    }
}

ArrayList集合

java.util.ArrayList<E>集合 implements List<E>接口
List 接口的大小可变数组的实现。
ArrayList集合底层采用的就是数组结构:查询快,增删慢
ArrayList集合底层源码:
定义的数组:用于存储元素
transient Object[] elementData = {};
add方法:
	public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 把原来数组长度+1
        elementData[size++] = e;
        return true;
    }
注意:
	什么使用使用ArrayList集合:频繁使用查询的时候

LinkedList集合(双向链表)

特有的方法

/*
    java.util.LinkedList<E>集合 implements List<E>接口
    List 接口的链接列表实现。
    LinkedList集合底层是一个双向链表:查询慢,增删快
    双向:是一个有序的集合
    LinkedList集合中有一些操作首尾元素的方法:(特有)
        public void addFirst(E e) :将指定元素插入此列表的开头。
        public void push(E e) :将元素推入此列表所表示的堆栈。
        public void addLast(E e) :将指定元素添加到此列表的结尾。

        public E getFirst() :返回此列表的第一个元素。
        public E getLast() :返回此列表的最后一个元素。
        public boolean isEmpty() ：如果列表不包含元素，则返回true。

        public E removeFirst() :移除并返回此列表的第一个元素。
        public E pop() :从此列表所表示的堆栈处弹出一个元素。
        public E removeLast() :移除并返回此列表的最后一个元素。
   注意:
        使用LinkedList集合特有的方法,不能使用多态创建对象
            List<String> list = new LinkedList<>(); 弊端:不能使用子类特有的功能
 */
public class Demo02LinkedList {
    public static void main(String[] args) {
        show04();
    }

    /*
        public E removeFirst() :移除并返回此列表的第一个元素。
        public E pop() :从此列表所表示的堆栈处弹出一个元素。此方法等效于 removeFirst()。
        public E removeLast() :移除并返回此列表的最后一个元素。
     */
    private static void show04() {
        LinkedList<String> linked = new LinkedList<>();
        linked.add("aaa");
        linked.add("bbb");
        linked.add("ccc");
        linked.add("ddd");
        System.out.println(linked);//[aaa, bbb, ccc, ddd]

        //String first = linked.removeFirst();
        String first = linked.pop();
        System.out.println("first:"+first);//first:aaa

        String last = linked.removeLast();
        System.out.println("last:"+last);//last:ddd
        System.out.println(linked);//[bbb, ccc]

    }

    /*
        public E getFirst() :返回此列表的第一个元素。
        public E getLast() :返回此列表的最后一个元素。
        public boolean isEmpty() ：如果列表不包含元素，则返回true。
     */
    private static void show03() {
        LinkedList<String> linked = new LinkedList<>();
        linked.add("aaa");
        linked.add("bbb");
        linked.add("ccc");
        linked.add("ddd");

        //linked.clear();//清空集合

        //为了防止NoSuchElementException:没有元素异常,增加一个判断,集合不是空在获取
        if(!linked.isEmpty()){//return size() == 0;
            String first = linked.getFirst();
            System.out.println("first:"+first);//first:aaa

            String last = linked.getLast();
            System.out.println("last:"+last);//last:ddd
        }

        if(linked.size()!=0){//return size() == 0;
            String first = linked.getFirst();
            System.out.println("first:"+first);//first:aaa

            String last = linked.getLast();
            System.out.println("last:"+last);//last:ddd
        }
    }

    private static void show02() {
        LinkedList<String> linked = new LinkedList<>();
        linked.addFirst("1");
        linked.addFirst("2");
        linked.addFirst("3");
        linked.addLast("a");
        linked.addLast("b");
        linked.addLast("c");
        System.out.println(linked);//[3, 2, 1, a, b, c]
    }

    /*
        public void addFirst(E e) :将指定元素插入此列表的开头。
        public void push(E e) :将元素推入此列表所表示的堆栈。此方法等效于 addFirst(E)。
        public void addLast(E e) :将指定元素添加到此列表的结尾。等效于 add()
     */
    private static void show01() {
        LinkedList<String> linked = new LinkedList<>();
        linked.add("aaa");
        linked.add("bbb");
        linked.add("ccc");
        linked.add("ddd");
        System.out.println(linked);//[aaa, bbb, ccc, ddd]

        //public void addFirst(E e) :将指定元素插入此列表的开头。
        //linked.addFirst("www");
        linked.push("www");
        System.out.println(linked);//[www, aaa, bbb, ccc, ddd]

        //public void addLast(E e) :将指定元素添加到此列表的结尾。等效于 add()
        linked.addLast("com");
        System.out.println(linked);//[www, aaa, bbb, ccc, ddd, com]
    }
}

Vector

注意：vector可以保证多线程的安全操作，但是效率低下

java.util.Vector<E> implements List<E>
Vector是JDK1.0时期就存在的单列集合,Collection下边的集合(ArrayList,LinkedList)是JDK1.2之后出现的
Vector 类可以实现可增长的对象数组。底层和ArrayList是一样的也是一个数组结构的集合
特点:查询快,增删慢
Vector集合在1.0时期特有的方法:
	void addElement(E obj) 将指定的组件添加到此向量的末尾，将其大小增加 1。
    Enumeration<E> elements() 返回此向量的组件的枚举。 
    Enumeration:就是1.0时期的迭代器==>向量枚举
    Enumeration<E>:接口
    	boolean hasMoreElements()  判断集合中是否还有元素==>hasNext
    	E nextElement() 取出集合中的元素==>next
与新 collection 实现不同，Vector 是同步的。 
同步技术:可以保证多线程的安全
同步:效率低下

Collections类

常用功能

/*
    java.util.Collections:操作集合的工具类,里边的方法都是静态的
        通过类名.方法名(参数)可以直接使用
    常用方法:
        static void shuffle(List<?> list) :随机打乱集合中元素的顺序
        static void sort(List<T> list) 根据元素的自然顺序对指定列表按升序进行排序。(升序:小->大,降序反之)
        static <T> void sort(List<T> list, Comparator<? super T> c) 根据指定比较器产生的顺序对指定列表进行排序。
    注意:
          以上3个方法的参数都必须传递List接口下的集合;不能使用Set接口下的集合
 */
public class Demo01Collections {
    public static void main(String[] args) {
        //创建ArrayList集合
        ArrayList<Integer> list01 = new ArrayList<>();
        list01.add(1);
        list01.add(3);
        list01.add(2);
        list01.add(4);
        System.out.println(list01);//[1, 3, 2, 4]

        /*
            static void sort(List<T> list) 根据元素的自然顺序对指定列表按升序进行排序。(升序:小->大,降序反之)
         */
        Collections.sort(list01);
        System.out.println(list01);//[1, 2, 3, 4]

        /*
            static void shuffle(List<?> list) :随机打乱集合中元素的顺序
         */
        Collections.shuffle(list01);
        System.out.println(list01);//[1, 4, 2, 3]  [3, 2, 4, 1]

        ArrayList<String> list02 = new ArrayList<>();
        list02.add("ab");
        list02.add("aa");
        list02.add("12");
        list02.add("AB");
        list02.add("CC");
        System.out.println(list02);//[ab, aa, 12, AB, CC]

        /*
            static void sort(List<T> list) 根据元素的自然顺序对指定列表按升序进行排序。(升序:小->大,降序反之)
            自然顺序: 编码表表的顺序ASCII   0:48   A:65   a:97
         */
        Collections.sort(list02);
        System.out.println(list02);//[12, AB, CC, aa, ab]
    }
}

Comparator比较器

/*
    static <T> void sort(List<T> list, Comparator<? super T> c) 根据指定比较器产生的顺序对指定列表进行排序。
    参数:
        List<T> list:要排序的List集合
        java.uti.Comparator<T>接口:对集合中元素进行排序的比较器
            强行对某个对象 collection 进行整体排序 的比较函数。
        Comparator接口中的抽象方法:
            int compare(T o1, T o2) 比较用来排序的两个参数。
            参数:
                 T o1, T o2:依次比较的集合中的元素[1,3,2,4]
            比较的规则:
                升序:o1-o2
                降序:o2-o1
                两个元素相等:o1==o2
 */
public class Demo02Collections {
    public static void main(String[] args) {
        //创建ArrayList集合
        ArrayList<Integer> list01 = new ArrayList<>();
        list01.add(1);
        list01.add(3);
        list01.add(2);
        list01.add(4);
        System.out.println(list01);//[1, 3, 2, 4]

        //使用Collections集合工具类中的方法sort对集合中的元素,根据比较器产生的规则降序排序
        Collections.sort(list01, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //降序: o2-o1
                return o2-o1;
            }
        });
        System.out.println(list01);//[4, 3, 2, 1]

        //使用Collections集合工具类中的方法sort对集合中的元素,根据比较器产生的规则升序排序
        Collections.sort(list01, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //升序: o1-o2
                return o1-o2;
            }
        });
        System.out.println(list01);//[1, 2, 3, 4]
    }
}

太空旅行  0:29:20
/*
    static <T> void sort(List<T> list, Comparator<? super T> c) 根据指定比较器产生的顺序对指定列表进行排序。
 */
public class Demo03Collections {
    public static void main(String[] args) {
        //创建ArrayList集合,泛型使用Person
        ArrayList<Person> list01 = new ArrayList<>();
        list01.add(new Person("zhangsan",18));
        list01.add(new Person("bwangwu",22));
        list01.add(new Person("lisi",19));
        list01.add(new Person("atianqi",22));
        list01.add(new Person("zhaoliu",20));

        //使用Collections集合工具类中的方法sort,根据比较器产生的规则,对List集合进行排序(年龄升序排序)
        Collections.sort(list01, new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                //年龄升序排序
                return o1.getAge()-o2.getAge();
            }
        });
        System.out.println(list01);//[Person{name='zhangsan', age=18}, Person{name='lisi', age=19}, Person{name='zhaoliu', age=20}, Person{name='wangwu', age=22}]

        //按照两个人的年龄升序排序,如果两个人的年龄相同,按照姓名的首字母降序排序
        Collections.sort(list01, new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                //按照两个人的年龄升序排序
                int a = o1.getAge()-o2.getAge();
                if(a==0){//两个人的年龄相同
                    //按照姓名的首字母降序排序
                    a = o2.getName().charAt(0)-o1.getName().charAt(0);
                }
                return a;
            }
        });
        System.out.println(list01);
    }
}

//实体类
public class Person {
    private String name;
    private int age;

    public Person() {
    }

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

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", 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;
    }
}

可变参数

note：可以接收任意个同种数据类型的参数

/*
    可变参数
        是JDK1.5之后出现的新特性
    作用:
        当我们定义一个方法的时候,方法的参数的类型已经明确了;但是参数的个数不确定,就可以使用可变参数
    格式:
        修饰符 返回值类型  方法名(数据类型...变量名){
            方法体
        }
    数据类型...变量名==>可变参数:代表形式参数可以接收任意个参数
        调用参数是可变参数的方法,参数的个数可以传递任意个(不传递,1,2,3,4,5,...,n)==>反射
    原理:
        可变参数底层就是一个数组,传递不同个数的参数,那么就会创建不同长的数组,来接收这些参数
 */
public class Demo04VarArgs {
    public static void main(String[] args) {
        //getSum();
        //getSum(10);
        //getSum(10,20);
        int sum = getSum(10, 20, 30, 40, 50, 60, 70, 80, 90, 100);
        System.out.println(sum);

        method("a","b",1.1,1,2,3);
    }

    /*
        可变参数的注意事项
        1.一个参数列表中只能写一个可变参数
     */
    //public static void method(int...a,String...b){}
    //2.方法的参数列表如果有多个参数,可变参数必须写在末尾 Vararg parameter must be the last in the list
    //public static void method(String b,String c,double d,int...a){}
    //可变参数的终极写法
    //public static void method(Object...obj){}
    public static <T> T[] method(T...t){
        return t;
    }

    /*
        定义一个计算n个(不知道要传递多少个整数0,1,2,3,4,...100...)int类型整数和的方法
        已知:
            参数的数据类型:int 类型
        未知:
            不知道计算多少个整数的和
        所以我们就可以使用可变参数,作方法的参数,可以接收任意个同种数据类型的变量
            getSum(); 传递0个参数,那么可变参数就会创建一个长度为0的数组,用来接收参数 new int[]{};
            getSum(10); 传递1个参数,那么可变参数就会创建一个长度为1的数组,用来接收参数 new int[]{10};
            getSum(10,20); 传递2个参数,那么可变参数就会创建一个长度为2的数组,用来接收参数 new int[]{10,20};
            getSum(10,20,30,40,50,60,70,80,90,100); 传递10个参数,那么可变参数就会创建一个长度为10的数组,
                用来接收参数 new int[]{10,20,30,40,50,60,70,80,90,100};
     */
    public static int getSum(int...arr){
        //System.out.println(arr);//数组的地址值  [I@4554617c
        //System.out.println(arr.length);//数组的长度 0
        //对数组中的元素进行求和
        //定义一个变量,初始值为0,记录累加求和
        int sum = 0;
        //遍历数组(可变参数),获取数组中每一个元素
        for (int i : arr) {
            //累加求和
            sum += i;
        }
        //把和返回
        return sum;
    }

    /*
        定义一个计算四个int类型整数和的方法
     */
    /*public static int getSum(int a,int b,int c,int d){
        return a+b+c+d;
    }*/

    /*
        定义一个计算三个int类型整数和的方法
     */
    /*public static int getSum(int a,int b,int c){
        return a+b+c;
    }*/

    /*
        定义一个计算两个int类型整数和的方法
     */
    /*public static int getSum(int a,int b){
        return a+b;
    }*/
}

Collections集合工具类中的方法addAll

/*
    java.util.Collections:集合工具类
        static <T> boolean addAll(Collection<? super T> c, T... elements) 将所有指定元素添加到指定 collection 中。
            给指定的集合一次添加多个元素
 */
public class Demo05AddAll {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        //st.add(1);
        //st.add(2);
        //st.add(3);
        //st.add(4);

        Collections.addAll(list,1,2,3,4);

        System.out.println(list);//[1, 2, 3, 4]

        ArrayList<String> list02 = new ArrayList<>();
        //Collections.addAll(list02,"a","b","c","d","e");

        //可变参数的底层就是一个数组,传递可参数也可以传递数组
        String[] arr = {"a","b","c","d","e"};
        Collections.addAll(list02,arr);

        System.out.println(list02);

    }
}

Set接口

java.util.Set<E> extends Collection<E>
Set接口的特点：
	1.不允许存储重复的元素
	2.不包含带索引的方法，里边的方法和Collection一样

HashSet集合的介绍和基本使用（重点）

/*
    java.uti.HashSet<E>集合 implements Set<E>接口
        此类实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。
        它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。
    HashSet集合的特点:
        1.不允许存储重复的元素
        2.不包含带索引的方法(不能使用普通的for循环遍历Set集合)
        3.是一个无序的集合(存储元素和取出元素的顺序有可能不一致)
        4.底层是一个哈希表
            JDK1.8之前:数组+单向链表
            JDK1.8之后:数组_单向链表|数组+红黑树(可以提高查询的效率)
 */
public class Demo01HashSet {
    public static void main(String[] args) {
        show02();
    }

    private static void show02() {
        HashSet<String> set = new HashSet<>();
        set.add("aaa");
        set.add("bbb");
        set.add("ccc");
        set.add("aaa");
        set.add("ddd");
        //使用增强for循环遍历Set集合
        for (String s : set) {
            System.out.println(s);
        }
    }


    private static void show01() {
        HashSet<Integer> set = new HashSet<>();
        //往集合中添加元素
        set.add(1);
        set.add(3);
        set.add(2);
        set.add(1);
        set.add(4);
        //使用迭代器遍历Set集合
        Iterator<Integer> it = set.iterator();
        while (it.hasNext()){
            Integer i = it.next();
            System.out.println(i);
        }
    }
}

哈希值（了解）

/*
    哈希值:
        是一个十进制的整数,由操作系统随机给出,我们打印的对象的地址值,使用的就是哈希值
    Object类中有获取对象哈希值的方法:
        int hashCode() 返回该对象的哈希码值。
        hashCode方法的底层源码:
            public native int hashCode();
            native:调用的是操作系统底层的方法
 */
public class Demo02HashCode {
    public static void main(String[] args) {
        //Person类默认继承了Object类,所以可以使用Object类中的hashCode方法
        Person p1 = new Person();
        int h1 = p1.hashCode();
        System.out.println(h1);//1163157884==>1

        /*
            Object类的toString
                String toString() 返回该对象的字符串表示。
            toString方法的底层源码:
                public String toString() {
                    return getClass().getName() + "@" + Integer.toHexString(hashCode());
                    getClass().getName():使用反射技术,获取类的全类名(包名+类名) com.aaa.demo04Set.Person
                    "@":字符串
                    Integer.toHexString(hashCode()):把十进制的整数转换为十六进制
                }
         */
        System.out.println(p1.toString());//com.aaa.demo04Set.Person@4554617c ==> xxx@1
    }
}

public class Person extends Object {
    //重写Obeject类的hashCode方法
    @Override
    public int hashCode() {
        return 1;
    }
}

String类的哈希值

/*
    String类哈希值
        String类重写了Object类的hashCode方法
        规则:
            相同的字符串,返回的哈希值是一样的
 */
public class Demo03StringHashCode {
    public static void main(String[] args) {
        String s1 = new String("abc");
        String s2 = new String("abc");
        System.out.println(s1.hashCode());//96354
        System.out.println(s2.hashCode());//96354
        System.out.println(s1==s2);//引用数据类型==比较的是对象的地址值 false

        System.out.println("重地".hashCode());//1179395
        System.out.println('重'+0);//37325 编码表对应的数字==>GBK
        System.out.println('地'+0);//22320
        System.out.println("通话".hashCode());//1179395

    }
}

HashSet集合存储数据的结构

使用HashSet集合存储String不重复的原理

/*
    使用HashSet集合存储String不重复的原理
        String类重写了Object类hashCode方法和equals方法,用来判断元素是否重复
        Integer,Double,Character...类重写了Object类hashCode方法和equals方法
 */
public class Demo04HashSetSaveString {
    public static void main(String[] args) {
        //创建HashSet集合,泛型使用String
        HashSet<String> set = new HashSet<>();
        String s1 = new String("abc");
        String s2 = new String("abc");
        set.add(s1);
        set.add(s2);
        set.add("重地");
        set.add("通话");
        set.add("abc");
        System.out.println(set);//打印的结果 [重地, 通话, abc]
    }
}

打赏

上一篇：用Python写一个记忆翻牌小游戏呀！下一篇：php数组的差集与并集

Java回顾数据结构

数据结构

1.栈

2.队列

3.数组

4.链表

红黑树

List接口

List接口中的常用方法

ArrayList集合

LinkedList集合(双向链表)

Vector

Collections类

可变参数

Collections集合工具类中的方法addAll

Set接口

HashSet集合的介绍和基本使用（重点）

哈希值（了解）

String类的哈希值

HashSet集合存储数据的结构

使用HashSet集合存储String不重复的原理

相关推荐

猜你喜欢

热门文章

热评文章

网站分类

标签列表

最新留言

Java回顾 数据结构

数据结构

1.栈

2.队列

3.数组

4.链表

红黑树

List接口

List接口中的常用方法

ArrayList集合

LinkedList集合(双向链表)

Vector

Collections类

可变参数

Collections集合工具类中的方法addAll

Set接口

HashSet集合的介绍和基本使用（重点）

哈希值（了解）

String类的哈希值

HashSet集合存储数据的结构

使用HashSet集合存储String不重复的原理

相关推荐

猜你喜欢

热门文章

热评文章

网站分类

标签列表

最新留言

Java回顾数据结构