[数据结构与算法]on-15 List set接口

1.List接口

List接口继承与collection接口，实现类为ArrayList和LinkedList

List接口特点

1. List集合有下标
2. List集合是有序的
3. List集合可以存重复的元素

List接口常用方法

/**本类用于List接口练习*/
public class TestList {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("大力娃");//向list集合中存入数据
        list.add("千顺娃");
        list.add("头铁娃");
        list.add("喷火娃");
        list.add("喷水娃");
        list.add("隐身娃");
        list.add("小紫娃");
        System.out.println(list.contains("喷火娃"));
        System.out.println(list.equals("喷水娃"));
        System.out.println(list.isEmpty());
        System.out.println(list.remove("小蝴蝶"));
        System.out.println(list.size());
        System.out.println(Arrays.toString(list.toArray()));//集合转数组，并打印

        list.add("小蝴蝶");
        System.out.println(list);
        list.add(1,"蛇精");//指定索引处添加元素
        list.add(3,"小蝴蝶");
        System.out.println(list);

        System.out.println(list.indexOf("小蝴蝶"));
        System.out.println(list.lastIndexOf("小蝴蝶"));

        System.out.println(list.remove(2));//根据索引删除集合中的元素,并将删除的元素返回
        System.out.println(list.get(8));//获取指定下标处的元素
        System.out.println(list);
        System.out.println(list.set(5,"蝎子精"));//修改集合中指定索引处的值
        System.out.println(list);

        List<String> list2 = new ArrayList<>();
        list2.add("1");
        list2.add("2");
        list2.add("3");
        list2.add("4");
        System.out.println(list2);
        System.out.println(list.addAll(list2));//将list2中的所有元素追加到list集合的末尾
        System.out.println(list);
        System.out.println(list.addAll(1,list2));//在list集合的指定索引处，添加list2集合的所有元素
    }
}

List接口的四种迭代方式

/**本类用于进一步测试list接口*/
public class TestList2 {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("喜羊羊");
        list.add("美羊羊");
        list.add("懒羊羊");
        list.add("沸羊羊");
        list.add("小肥羊");
        list.add("肥羊卷");
        System.out.println(list);

        /*集合的迭代方式：
        1.for循环
        2.foreach 高效for循环
        3.iterator
        * */
        /*方式一迭代：因为list集合是有序的，元素是有下标值的*/
        System.out.println("方式一 ：：*************************************");
        for(int i=0; i<list.size(); i++){
            System.out.println(list.get(i));
        }
        /*方式二迭代：
        * 格式： for(本轮遍历得到的元素的类型  元素名： 要遍历的元素) { 循环体 }*/
        System.out.println("方式二 ：：**************************************");
        for(String s : list){
            System.out.println(s);
        }
        /*方式三迭代：iterator*/
        System.out.println("方式三 ：：*************************************** ");
        Iterator<String> it = list.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }
        /*方式四迭代：listIterator 属于list接口特有的迭代器
        * iterator<E> 父接口 hasNext() next()
        * ListIterator<E> 子接口--除了从父接口处继承的功能以外
          还有自己特有的功能，比如逆序遍历 添加元素等等， 但是不常用
          public interface ListIterator<E extends Iterator<E>
          * */
        System.out.println("方式四 ：：*************************************** ");
        //获取迭代器对象
        ListIterator<String> it2 = list.listIterator();
        while(it2.hasNext()){
            System.out.println(it2.nextIndex());
        }
        System.out.println("方式五，逆序迭代 ：：*************************************** ");
        ListIterator<String> it3 = list.listIterator();
        while(it3.hasNext()){//判断后面是否有元素可以迭代
            System.out.println(it3.next());//打印获取到的后面的元素
            if(!it3.hasNext()){//直到迭代器没有下一个元素可以迭代了
                System.out.println("开始逆序遍历");
                while(it3.hasPrevious()){//判断前面是否有元素可以迭代
                    System.out.println(it3.previous());//打印获取到的前面的元素
                }
                break; //终止循环，不然会一直从头到尾，再从头到尾遍历
            }
        }
    }
}

2.List集合的两个常用实现类

2.1 ArrayList

1. List接口的实现类
2. 底层的数据结构是数组，内存空间是连续的
3. 元素有下标，有序，允许存放重复的操作
4. 通常可以根据下标进行操作
5. 增删操作比较慢，查询操作比较快【数据量大时】
6. 内部数组默认的初始容量是10,如果不够会以1.5倍的容量增长

/**本类用于测试ArrayList实现类*/
public class TestArrayList {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(100);
        list.add(200);
        list.add(300);
        list.add(400);
        list.add(400);
        list.add(300);
        System.out.println(list);

//        list.clear();
        System.out.println(list.contains("100"));//false，因为这个100是字符串
        System.out.println(list.get(1));//200,打印下标为1的元素
        System.out.println(list.indexOf(400));//3,指定元素第一次出现的下标
        System.out.println(list.lastIndexOf(400));//4，指定元素最后一次出现的下标
        System.out.println(list.remove(0));//根据下标删除元素
        /*集合中传入的数据是引用类型，不是基本类型
        * 所以如果想根据元素删除数据，需要把int类型参数300转为集合中元素的类型Integer*/
        System.out.println(list.remove(Integer.valueOf(300)));//删除int类型的300
        System.out.println(list);
        System.out.println(list.contains(200));
    }
}

2.2 LinkedList实现类

1. List接口的实现类
2. 底层的数据结构是链表，内存空间是不连续的
3. 元素有下标，有序，允许存放重复的数据
4. 但是通常首尾节点的操作比较多
5. 增删操作比较快，查询操作比较慢【数据量大时】
6. LinkedList查询,首尾操作还是比较快的

/**本类用于测试LinkedList方法的使用*/
public class TestLinkedList {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("孙悟空");
        list.add("猪八戒");
        list.add("沙师弟");
        list.add("唐三藏");
        list.add("白龙马");
        System.out.println(list);
        list.addFirst("蜘蛛精");
        list.addLast("玉兔精");
        System.out.println(list);
        System.out.println(list.getFirst()); //获取首元素
        System.out.println(list.getLast()); //获取尾元素

        System.out.println(list.removeFirst());//删除首节点
        System.out.println(list.removeLast());//删除尾结点
        System.out.println(list);

        LinkedList<String> list2 = new LinkedList<>();
        list2.add("西游记");
        list2.add("红楼梦");
        list2.add("水许传");
        list2.add("三国演义");
        System.out.println(list2);
        System.out.println(list2.element());//获取集合中的首元素

        /*别名：查询系列*/
        System.out.println(list2.peek());//获取集合中的首元素
        System.out.println(list2.peekFirst());//获取集合中的首元素
        System.out.println(list2.peekLast());//获取集合中的尾元素

        /*别名：新增系列*/
        System.out.println(list2.offer("斗罗大陆"));//添加尾元素
        System.out.println(list2.offerFirst("盗墓笔记"));//添加首元素
        System.out.println(list2.offerLast("钢铁是怎样练成的"));//添加尾元素
        System.out.println(list2);

        /*别名：移除系列*/
        System.out.println(list2.poll());//移除首元素
        System.out.println(list2.pollFirst());//移除首元素
        System.out.println(list2.pollLast());//移除尾元素
        System.out.println(list2);

        /*以上都是对首位节点做操作*/
    }
}

3.Map接口

1. map集合的结构是：键值对、KEY与VALUE、Map.Entry<K,V>的映射关系
2. map中key值不允许重复，如果重复，对应的value会被覆盖
3. map中的映射关系是无序的
4. map没有自己的迭代器，所以迭代时通常需要转成set集合来迭代

/**本类用于测试map接口*/
public class TestMap {
    public static void main(String[] args) {
        Map<Integer,String> map = new HashMap<>();
//        Map<String,Integer> map2 = new HashMap<>();
//        map2.put("白骨精",1);
        map.put(9527,"白骨精");
        map.put(9528,"黑熊精");
        map.put(9529,"鲤鱼精");
        map.put(9530,"黄毛怪");
        map.put(9531,"黑熊精");
        map.put(9527,"女儿国国王");
        System.out.println(map);
        /*1.map中存放的都是无序的数据
        * 2.map中的value可以重复，比如放入了两个“黑熊精 ”
        * 3.map中的key不可以重复，如果重复，新的value会把旧的value重复掉*/

//        map.clear();
//        System.out.println(map);
        System.out.println(map.hashCode());//获取集合对象的哈希值
        System.out.println(map.equals("黄毛怪"));//集合对象与集合中的元素对比
        System.out.println(map.isEmpty());//false,判断集合是否为空
        System.out.println(map.size());//5,集合的长度

        System.out.println(map.containsKey(9527));//判断集合中是否包含指定的Key(键)
        System.out.println(map.containsValue("黑熊精"));//判断集合中是否包含指定的value(值)
        System.out.println(map);
        System.out.println(map.get(9527));//根据key获取集合中对应的value
        System.out.println(map.remove(9529));//删除指定的键值对
        System.out.println(map.containsValue("鲤鱼精"));//false
        System.out.println(map.containsKey(9529));//false
        /*将map集合中的所有value去除，存入到一个Collection集合中*/
        Collection<String> values = map.values();
        System.out.println(values);
        /*将map集合中的所有key去除，存入到一个Collection集合中*/
//        Collection<Integer> keys = map.keySet();
//        System.out.println(keys);

        //map集合的迭代方式一
        /*方式一：
        想要迭代map中的数据，但是map本身没有迭代器，所以需要先转换成set集合
        Set<KEY>：把map中所有的KEY值存入到Set集合中，用到的方法：keySet()
        */
        Set<Integer> key = map.keySet();
        System.out.println(key);
        Iterator<Integer> it = key.iterator();
        while(it.hasNext()){
            Integer next = it.next();
            String value = map.get(next);
            System.out.println("{"+next+"="+value+"}");
        }
        //map集合的迭代方式二
        /*想要迭代map集合，需要把map集合先转换成set集合
        * 这次是把map中的每一对键值对都看作是一个Entry<K,V>
        一对Key&value就是一对Entry<K,V>*/
        System.out.println("第二种方法*************************");
        Set<Map.Entry<Integer, String>> set = map.entrySet();
        Iterator<Map.Entry<Integer, String>> it2 = set.iterator();
        while(it2.hasNext()){
            Map.Entry<Integer, String> entry = it2.next();
            Integer key1 = entry.getKey();
            String val = entry.getValue();
            System.out.println("{"+key1+"="+val+"}");
        }
    }
}