Java回顾 数据结构

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

数据结构

1.栈

2.队列

Java回顾 数据结构

3.数组

Java回顾 数据结构

4.链表

Java回顾 数据结构

红黑树

Java回顾 数据结构

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集合:频繁使用查询的时候

Java回顾 数据结构

LinkedList集合(双向链表)

特有的方法
Java回顾 数据结构

/*
    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) 将指定的组件添加到此向量的末尾,将其大小增加 1Enumeration<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

    }
}

Java回顾 数据结构

HashSet集合存储数据的结构

Java回顾 数据结构

使用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]
    }
}
打赏
文章版权声明:除非注明,否则均为彭超的博客原创文章,转载或复制请以超链接形式并注明出处。
相关推荐

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

猜你喜欢