复习集合Collection、自定义数组、链表源码分析和实现

一、复习

问1：Collection和数组有什么区别？

相同点：集合和数组都是存储一组数据的。

不同点：

数组是定长的，元素类型一样，索引从[0]开始，元素是连续的，可以存储基本数据类型的元素也可以存储引用数据类型的元素。

集合的长度可变，元素类型也相同，有的集合有序，可以按照索引，有的集合无序，不能按照索引操作，只能存储引用数据类型的元素。

问2：Collection父接口下面有很多个子接口：List、Set、Queue、Deque等，它们有什么区别？

List允许元素重复，有序。

Set不允许元素重复，无序。

Queue是队列，先进先出。

Deque是双端对列，可以从头进或出，也可以从尾进或出。

问3：Set接口的实现类有哪些？它们有什么区别？

HashSet：无规律，散列存储。比喻：广场上的人。

LinkedHashSet：也是散列，有规律，有一个链表记录它们的添加顺序。比喻：在饭店门口等餐位的人，看起来也是分数的，但是它们手上有号，这个号码记录它们来的顺序。

TreeSet：有规律，按照元素的大小顺序排列。依赖于自然比较接口Comparable，或定制比较器接口Comparator。比喻：做操的排队队员。

问4：List接口的实现类有哪些？它们有什么区别？

ArrayList：底层是动态数组，有序的，可重复的，线程不安全。new ArrayList()时，底层数组长度为0，添加时长度才为10。扩容1.5倍。

LinkedList：底层是双向链表，有序的，可重复。

Stack：它是栈，先进后出。Stack是Vector的子类。

Vector：它就旧版的动态数组，线程安全的。new Vector()时，底层数组的长度直接为10。默认扩容2倍，也可以手动指定扩容的增量。

问5：迭代器Iterator和ListIterator有什么关系，有什么区别？

ListIterator继承了Iterator。它们共同的方法：hasNext()、next()、remove()

ListIterator扩展了一些方法。扩展的包括：add（添加）、set（替换）、返回元素的索引 nextIndext和previousIndex、遍历方向多了从后往前遍历（hasPrevious 和 previous）。

Iterator适用于所有Collection集合。ListIterator只能用于List系列的集合。

问6：Iterable接口 与 Iterator接口有什么关系，有什么不同？

Iterable 是形容词，形容 容器 可迭代的。实现它，表示容器可以用foreach遍历，也可以用Iterator迭代器遍历。比喻：列车、飞机上可以查看乘客的情况。

Iterator 是名词，作为迭代容器元素的一个工具，或者说用来遍历集合的元素的。比喻：相当于列车或飞机上的乘务员。

Iterable 是依赖于 Iterator，Iterable接口中包含了一个抽象方法：Iterator iterator()。

问7：Comparable接口与Comparator接口有什么区别？

Comparable接口中一个int compareTo(T t)

Compartor接口中有一个int compare(T t1, T t2)

返回值：正整数、负整数、零，分别代表大于、小于、等于。

比如：要比较两个苹果对象的“大小”

实现Comparable接口，表示 苹果对象本身就可以比较大小， 苹果对象1.compareTo(苹果对象2)，一般都是先选择Comparable接口。

实现Comparator接口，表示 需要第三者来比较两个苹果的大小，售货员.compare(苹果对象1， 苹果对象2)，如果上面的满足不了我的需求，在选择下面的Comparator接口。

问8：泛型，例如：ArrayList等集合都是泛型类，那么在使用集合时，怎么指定泛型？

例如：要存储一组字符串，整数，学生对象…

ArrayList one = new ArrayList<>();

ArrayList two= new ArrayList<>();

ArrayList two= new ArrayList<>();

问9：泛型通配符，有3种形式，以ArrayList为例

ArrayList：表示?对应任意类型

ArrayList：表示?对应的是A或A的子类（或实现类）类型，A称为上限。

ArrayList：表示?对应的是B或B的父类类型，B称为下限。

ArrayList list = new ArrayList();

ArrayList list = new ArrayList();

ArrayList list = new ArrayList();

ArrayList list = new ArrayList();（错误）

ArrayList list = new ArrayList();（错误）

ArrayList list = new ArrayList();（可以）

ArrayList list = new ArrayList();（错误）

ArrayList list = new ArrayList();（可以）

ArrayList list = new ArrayList();（错误）

二、Map集合的使用

2.1 Map集合的特点

Map系列的集合用来存储键值对(key,value)，键值对有称为映射关系。映射(map)，比如，地图上的某个位置，对应实际生活中的某个地点。

Map系列的集合还有一个共同特点：它们的key不能重复。它们的value可能重复。

Map的实现类有很多，最常用的一个是HashMap。

2.2 java.util.Map的API

Map集合的根接口是java.util.Map，它的API方法：

1、添加

• public V put(K key, V value)：添加一对键值对。如果是首次添加这个key的映射关系，那么返回值是null。如果这个key的映射关系已存在，返回被覆盖/替换的value值。
• public void putAll(Map m)：添加一组键值对。如果m集合中有key与当前map的key重复，会覆盖当前集合中的(key,value)。

2、删除

• public void clear()：清空当前map。
• public V remove(Object key)：根据key删除一对键值对。如果该key的映射关系存在，那么会移除一对映射关系，并且返回value值。如果该key的映射关系不存在，返回null。
• public default boolean remove(Object key,Object value)：删除匹配的(key,value)键值对。该方法是JDK8引入的。

3、修改

• map中的键值对的key是不能修改的，能修改的只有value。
• 如果你是key不变，修改value，可以再次put一下新的(key,value)。早期只能用新的value覆盖旧的value。
• public default V replace(K key, V value)：找到目标key，替换value。
• public default boolean replace(K key,V oldValue,V newValue)：找到目标(key,value)，替换value。
• public default void replaceAll(BiFunction function)：实现BiFunction接口并重写R apply(T t, U u)方法（此时为public String apply(Integer key, String oldValue)形式）。在replaceAll方法中会遍历当前map，并将每一个(key,value)作为实参传给apply方法，然后将apply方法的返回值作为newValue覆盖当前oldValue。

4、查询

• public V get(Object key)：根据key返回value。
• public default V getOrDefault(Object key,V defaultValue)：如果根据key可以get到一个非null的value值，则返回value值，否则返回defaultValue。
• public boolean containsKey(Object key)：判断key是否存在。
• public boolean containsValue(Object value)：判断value是否存在。
• public boolean isEmpty()：判断map是否为空。
• public int size()：获取键值对的数量。

5、遍历

Map接口没有继承Iterable接口，说明Map系列的集合本身不支持foreach，也不支持直接适用面Iterator迭代器遍历。

如果要遍历Map必须转换一下：

（1）分开遍历：

• public Set keySet()：返回当前map中的所有key构成的Set集合，然后可以遍历所有的key。
• public Collection values()：返回当前map中的所有value构成的Collection集合，然后遍历所有value。

（2）成对遍历：

• public Set> entrySet()：返回当前map中所有键值对Entry对象构成的Set集合，然后遍历所有键值对的Entry对象。
• 遍历的是映射关系Map.Entry类型的对象，Map.Entry是Map接口的内部接口。每一种Map内部有自己的Map.Entry的实现类。在Map中存储数据，实际上是将Key---->value的数据存储在Map.Entry接口的实例中，再在Map集合中插入Map.Entry的实例化对象，

6、代码演示

public class API {
    @Test
    public void test() throws Exception{
        HashMap<String, String> map = new HashMap<>();
        //public V put(K key, V value)：添加一对键值对。
        // 如果是首次添加这个key的映射关系，那么返回值是null。如果这个key的映射关系已存在，返回被覆盖/替换的value值。
        map.put("哈哈","嘻嘻");
        map.put("嘿嘿","咻咻");
        map.put("biubiu","diudiu");
        System.out.println(map);
        //{biubiu=diudiu, 哈哈=嘻嘻, 嘿嘿=咻咻}
    }

    @Test
    public void test1() throws Exception{
        //public void putAll(Map m)
        //添加一组键值对。如果m集合中有key与当前map的key重复，会覆盖当前集合中的(key,value)。
        HashMap<String, String> map1 = new HashMap<>();
        map1.put("哈哈","嘻嘻");
        map1.put("嘿嘿","咻咻");
        map1.put("biubiu","diudiu");
        HashMap<String, String> map2 = new HashMap<>();
        map2.put("GGB","小菲菲");
        map2.put("喜羊羊","灰太狼");
        map2.put("biubiu","沸羊羊");
        map1.putAll(map2);
        System.out.println(map1);
        //{GGB=小菲菲, biubiu=沸羊羊, 哈哈=嘻嘻, 嘿嘿=咻咻, 喜羊羊=灰太狼}
    }
    @Test
    public void test2() throws Exception{
        //public void clear()：清空当前map。
        HashMap<String, String> map1 = new HashMap<>();
        map1.put("哈哈","嘻嘻");
        map1.put("嘿嘿","咻咻");
        map1.put("biubiu","diudiu");
        map1.clear();
        System.out.println(map1);
        //{}
    }

    @Test
    public void test3() throws Exception{
        //public V remove(Object key)：根据key删除一对键值对。
        //如果该key的映射关系存在，那么会移除一对映射关系，并且返回value值。如果该key的映射关系不存在，返回null。
        HashMap<String, String> map1 = new HashMap<>();
        map1.put("哈哈","嘻嘻");
        map1.put("嘿嘿","咻咻");
        map1.put("biubiu","diudiu");
        System.out.println("map1.remove(\"哈哈\") = " + map1.remove("哈哈"));
        System.out.println(map1);
        System.out.println("-------------");
        System.out.println("map1.remove(\"java\") = " + map1.remove("java"));
        System.out.println(map1);
        //map1.remove("哈哈") = 嘻嘻
        //{biubiu=diudiu, 嘿嘿=咻咻}
        //-------------
        //map1.remove("java") = null
        //{biubiu=diudiu, 嘿嘿=咻咻}
    }

    @Test
    public void test4() throws Exception{
        //public default boolean remove(Object key,Object value)
        // 删除匹配的(key,value)键值对。该方法是JDK8引入的。
        HashMap<String, String> map1 = new HashMap<>();
        map1.put("哈哈","嘻嘻");
        map1.put("嘿嘿","咻咻");
        map1.put("biubiu","diudiu");
        map1.remove("哈哈","嘻嘻");
        System.out.println(map1);
        System.out.println("------------");
        map1.remove("java",null);
        System.out.println(map1);
        //{biubiu=diudiu, 嘿嘿=咻咻}
        //------------
        //{biubiu=diudiu, 嘿嘿=咻咻}
    }
    @Test
    public void test5() throws Exception{
        //public default V replace(K key, V value)：找到目标key，替换value。
        HashMap<String, String> map1 = new HashMap<>();
        map1.put("哈哈","嘻嘻");
        map1.put("嘿嘿","咻咻");
        map1.put("biubiu","diudiu");
        map1.replace("biubiu","java");
        System.out.println(map1);
        System.out.println("-------------");
        map1.replace("haha","java");
        System.out.println(map1);
        //{biubiu=java, 哈哈=嘻嘻, 嘿嘿=咻咻}
        //-------------
        //{biubiu=java, 哈哈=嘻嘻, 嘿嘿=咻咻}
        //如果找不到匹配的 , 就不动
    }

    @Test
    public void test6() throws Exception{
        // default boolean replace(K key,V oldValue,V newValue)：找到目标(key,value)，替换value。
        HashMap<String, String> map1 = new HashMap<>();
        map1.put("哈哈","嘻嘻");
        map1.put("嘿嘿","咻咻");
        map1.put("biubiu","diudiu");
        map1.replace("哈哈","嘻嘻","world");
        System.out.println(map1);
        //{biubiu=diudiu, 哈哈=world, 嘿嘿=咻咻}
        //注意:只能修改key对应的value , 不能修改key
    }

    @Test
    public void test7() throws Exception{
        //public default void replaceAll(BiFunction function)
        //实现BiFunction接口并重写R apply(T t, U u)方法

        // 在replaceAll方法中会遍历当前map，并将每一个(key,value)作为实参传给apply方法，
        // 然后将apply方法的返回值作为newValue覆盖当前oldValue。

        //public void replaceAll(BiFunction function)
        //replaceAll方法的形参类型BiFunction，
        //BiFunction是一个泛型接口，它有3个泛型，
        //? super K： ?的类型必须是 >= K，key的类型
        //? super V： ?的类型必须是 >= V，Value的类型
        //? extends V：?的类型必须是 <= V，Value的类型
        //前面两个泛型是指map现在的HashMap两个泛型的类型要求
        //第三个泛型是你新的value的类型，要么和现在的value类型一样，要么比现在的value类型要小
        HashMap<String, String> map1 = new HashMap<>();
        map1.put("哈哈","嘻嘻");
        map1.put("嘿嘿","咻咻");
        map1.put("biubiu","diudiu");
        map1.put("haha","diudiu");
        map1.replaceAll(new BiFunction<String, String, String>() {
            @Override
            public String apply(String key, String oldValue) {
                if(oldValue.equals("diudiu")){
                    return "java";
                }
                return oldValue;
            }
        });
        System.out.println(map1);
    }
    //{haha=java, biubiu=java, 哈哈=嘻嘻, 嘿嘿=咻咻}

    @Test
    public void test8() throws Exception{
        //public V get(Object key)：根据key返回value。
        HashMap<String, String> map1 = new HashMap<>();
        map1.put("哈哈","嘻嘻");
        map1.put("嘿嘿","咻咻");
        map1.put("biubiu","diudiu");
        map1.put("didi",null);
        System.out.println(map1.get("哈哈"));     //嘻嘻
        System.out.println(map1.get("haha"));       //null
        //注意: get方法无法区分查找的K的V是null , 还是没有K显示的null
    }

    @Test
    public void test9() throws Exception{
        //public boolean containsKey(Object key)：判断key是否存在。
        HashMap<String, String> map1 = new HashMap<>();
        map1.put("哈哈","嘻嘻");
        map1.put("嘿嘿","咻咻");
        map1.put("biubiu","diudiu");
        map1.put("didi",null);
        System.out.println(map1.containsKey("didi"));   //true

        String key = "张三";
        String value = map1.get(key);
        if(value==null){
            if(map1.containsKey(key)){
                System.out.println("有这个"+key+"但是它没有值");
            }else{
                System.out.println("没有这个"+key);
            }
        }
        //true
        //没有这个张三
    }

    @Test
    public void test10() throws Exception{
        //public default V getOrDefault(Object key,V defaultValue)
        //如果根据key可以get到一个非null的value值，则返回value值，否则返回defaultValue。
        HashMap<String, String> map1 = new HashMap<>();
        map1.put("哈哈","嘻嘻");
        map1.put("嘿嘿","咻咻");
        map1.put("biubiu","diudiu");
        map1.put("didi",null);

        String value = map1.get("张三");
        System.out.println("value = " + value);     //null
        System.out.println(map1);   //{didi=null, biubiu=diudiu, 哈哈=嘻嘻, 嘿嘿=咻咻}

        String value2 = map1.getOrDefault("张三", "花花");
        System.out.println(value2);  //花花

        String value3 = map1.getOrDefault("didi", "huahua");
        System.out.println("value3 = " + value3);   //value3 = null
        System.out.println(map1);
        //{didi=null, biubiu=diudiu, 哈哈=嘻嘻, 嘿嘿=咻咻}
        //如果有这个键值对,但是为null,也不为它设置默认值
        //如果没有这个键值对,则可以为他设置默认值
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204

public class bianLi {
    @Test
    public void test() throws Exception{
        //（1）分开遍历：
        //public Set keySet()：返回当前map中的所有key构成的Set集合，然后可以遍历所有的key。
        //public Collection values()：返回当前map中的所有value构成的Collection集合，然后遍历所有value。
        HashMap<String, String> map1 = new HashMap<>();
        map1.put("哈哈","嘻嘻");
        map1.put("嘿嘿","咻咻");
        map1.put("biubiu","diudiu");

        //遍历所有的key
        Set<String> keys = map1.keySet();//由key组成,因为map的key不可能重复,Set集合的特征也不可重复
        for (String key : keys) {
            System.out.println(key);
        }
        //biubiu
        //哈哈
        //嘿嘿
    }
    @Test
    public void test1() throws Exception{
        //public Collection values()：返回当前map中的所有value构成的Collection集合，然后遍历所有value。
        HashMap<String, String> map1 = new HashMap<>();
        map1.put("哈哈","嘻嘻");
        map1.put("嘿嘿","咻咻");
        map1.put("biubiu","diudiu");

        //遍历所有的value
        Collection<String> values = map1.values();//由value组成的集合,因为map的value可能重复,所以肯定不是Set
        for (String value : values) {
            System.out.println(value);
        }
        //diudiu
        //嘻嘻
        //咻咻
    }

    @Test
    public void test2() throws Exception{
        //public Set> entrySet()
        //返回当前map中所有键值对Entry对象构成的Set集合，然后遍历所有键值对的Entry对象。
        /*
        最外层是Set，因为map的key不可能重复，那么(key,value)就不可能重复，所以它们构成一个Set
        Map.Entry：这些键值对(key,value)的组合都是Entry类型的对象
        表示key的类型和value的类型
        Map.Entry表示Entry类型是Map的内部类（内部接口），这里是内部接口
        */
        HashMap<String, String> map1 = new HashMap<>();
        map1.put("哈哈","嘻嘻");
        map1.put("嘿嘿","咻咻");
        map1.put("biubiu","diudiu");

        Set<Map.Entry<String, String>> entries = map1.entrySet();
        for (Map.Entry<String, String> entry : entries) {
            System.out.println(entry); //直接输出
//            System.out.println("key:"+entry.getKey()+",value"+entry.getValue());
        }
        //biubiu=diudiu
        //哈哈=嘻嘻
        //嘿嘿=咻咻
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

三、源码分析

3.1 自定义动态数组

代表：ArrayList和Vector

以ArrayList为例。

为了让大家印象更深刻一些，我们模仿ArrayList写一写一小部分源码，来理解它底层的原理。

public class MyArrayList<E> implements Iterable<E>{
    private Object[] arr = new Object[4];//实际存储对象的数组，初始长度为4
    private int size;//代表实际元素的个数，size <= elementData.length

    //编写add
    public void add(E e) {
        //判断是否需要扩容
        if (size >= arr.length) {
            arr = Arrays.copyOf(arr, arr.length * 2);
        }
        arr[size] = e;
        size++;
    }

    //编写add(int index,E e)
    public void add(int index, E e) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("输入有误,数组下标越界异常");
        }
        if (size > arr.length) {
            arr = Arrays.copyOf(arr, arr.length * 2);
        }
        System.arraycopy(arr, index, arr, index + 1, size - index);
        arr[index] = e;
        size++;
    }

    //编写get(int index)查询obj在当前动态数组中的索引值，如果存在多个obj对象，那么返回第一次找到的索引值
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("输入有误,数组下标越界异常");
        }
        return (E) arr[index];
    }

    //查询obj在当前动态数组中的索引值，如果存在多个obj对象，那么返回第一次找到的索引值
    //分情况,看target的情况
    public int indexOf(Object target) {
        if (target == null) {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < arr.length; i++) {
                if (target.equals(arr[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    public int lastIndexOf(Object target) {      //倒着遍历
        if (target == null) {
            for (int i = size - 1; i >= 0; i--) {
                if (arr[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = size - 1; i >= 0; i--) {
                if (target.equals(arr[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    public boolean contains(Object target) {
        int index = lastIndexOf(target);
        if (index >= 0) {
            return true;
        } else {
            return false;
        }
    }

    public void remove(int index) {//删除[index]索引位置的元素
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException("索引错误");
        }
        System.arraycopy(arr, index + 1, arr, index, size - index - 1);
        arr[size - 1] = null;
        size--;
    }

    //如果只删除第一次找到的目标
    public void remove(Object obj) {
        int index = indexOf(obj);
        if (index >= 0) {
            remove(index);
        }
    }

    public String toString() {
        String str = "";
        for (int i = 0; i < size; i++) {
            if (i == 0) {
                str += "[" + arr[i]+",";
            } else if (i == size - 1) {
                str += arr[i] + "]";
            } else {
                str += arr[i] + ",";
            }
        }
        return str;
    }


    //重写Iterable接口的抽象方法，需要提供一个迭代器对象
    @Override
    public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator{
        int index;
        @Override
        public boolean hasNext() {
            return index >= 0 && index < size;
        }

        @Override
        public E next() {
            return (E) arr[index++];
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

public class ArrayListTest<E> {
    @Test
    public void test() throws Exception{
        MyArrayList<String> list = new MyArrayList<>();
        list.add("hello");
        list.add("world");
        list.add("java");
        list.add("xixi");
        list.add(null);
        list.add("haha");
        list.add(1,"biu");
        System.out.println(list);
    }

    @Test
    public void test1() throws Exception{
        MyArrayList<String> list = new MyArrayList<>();
        list.add("hello");
        list.add("world");
        list.add("java");
        list.add("xixi");
        list.add(null);
        list.add("haha");
        list.add(1,"biu");
        System.out.println(list.get(1));
    }

    @Test
    public void test2() throws Exception{
        MyArrayList<String> list = new MyArrayList<>();
        list.add("hello");
        list.add("world");
        list.add("java");
        list.add("xixi");
        list.add(null);
        list.add("haha");
        System.out.println(list.indexOf("hello"));
    }

    @Test
    public void test3() throws Exception{
        MyArrayList<String> list = new MyArrayList<>();
        list.add("hello");
        list.add("world");
        list.add("java");
        list.add("xixi");
        list.add(null);
        list.add("haha");
        System.out.println(list.lastIndexOf("haha"));
    }

    @Test
    public void test4() throws Exception{
        MyArrayList<String> list = new MyArrayList<>();
        list.add("hello");
        list.add("world");
        list.add("java");
        list.add("xixi");
        list.add(null);
        list.add("haha");
        System.out.println(list.contains("hello"));
        System.out.println(list.contains("bbbbb"));
    }

    @Test
    public void test5() throws Exception{
        MyArrayList<String> list = new MyArrayList<>();
        list.add("hello");
        list.add("world");
        list.add("java");
        list.add("xixi");
        list.add(null);
        list.add("haha");
        list.remove(4);
        System.out.println(list);
    }

    @Test
    public void test6() throws Exception{
        MyArrayList<String> list = new MyArrayList<>();
        list.add("hello");
        list.add("world");
        list.add("java");
        list.add("xixi");
        list.add(null);
        list.add("haha");
        list.add("world");
        list.remove("world");
        System.out.println(list);
    }

    @Test
    public void test7() throws Exception{
        MyArrayList<String> list = new MyArrayList<>();
        list.add("hello");
        list.add("world");
        list.add("java");
        list.add("xixi");
        list.add(null);
        list.add("haha");
        list.add("world");
        System.out.println(list.toString());
    }

    @Test
    public void test8() throws Exception{
        MyArrayList<String> list = new MyArrayList<>();
        list.add("hello");
        list.add("world");
        list.add("java");
        list.add("xixi");
        list.add(null);
        list.add("haha");
        list.add("world");
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()){
            String str = iterator.next();
            System.out.println(str);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

3.2 自定义双向链表

/**
 * MyLinkedList模仿LinkedList（双向链表）。
 * add(E e)：添加一个元素
 * remove(Object target)：删除一个元素
 * 遍历
 */
public class MyLinkedList<E> implements Iterable {
    private Node<E> first;  //代表头节点
    private Node<E> last;   //代表尾节点
    private int size;   //代表节点个数


    //因为没有Node类型,所以我们在这里建一个内部类Node
    private static class Node<E> {
        //节点是由data和link组成,所以需要声明
        Node<E> previous;
        E data;
        Node<E> next;

        //声明一个构造器,因为此时为内部类且被private修饰,所以可以把public去掉
        Node(Node<E> previous, E data, Node<E> next) {
            this.previous = previous;
            this.data = data;
            this.next = next;
        }
    }

    //此时我们来定义add()方法
    public void add(E e) {
        //此处的e传的是结点中的data,想要加入链表,就需要将data包装起来
        Node<E> node = new Node<>(last, e, null);

        //添加的时候要考虑如下情况:①此时链表中没有元素②此时链表中有元素
        //①当链表中没有元素时,体现为 first = null   last = null
        if (first == null) {
            first = node;
        } else {
            //②当链表中有元素时,我们在new node的时候就已经将previous指向了last,但是last.next没有指向我们
            //所以此时就需要last.next指向我们
            last.next = node;
        }
        last = node;
        size++;
    }

    //此时我们来定义remove方法   根据指定的obj查找删除
    //首先我们需要先去查找有没有obj,如果没有,则不删除,如果有,则仍需进行分情况判断, 如①obj在first②obj在last③obj在中间
    public Node<E> findNode(Object target) {
        //首先从第一个元素开始寻找
        Node<E> node = first;
        if (target != null) {
            while (node != null) {
                if (target.equals(node.data)) {
                    break;
                }
                node = node.next;
            }
        } else {
            while (node != null) {
                if (node.data == null) {
                    break;
                }
                node = node.next;
            }
        }
        return node;
    }


    public void remove(Object obj) {
        Node<E> node = findNode(obj);
//        Node before = node.previous;
//        Node after = node.next;
        if (node == null) {
            return;
        }
        //当obj为头节点时
        if (node.previous == null) {
            first = node.next;
        } else {
            node.previous.next = node.next;
        }

        if (node.next == null) {
            last = node.previous;
        } else {
            node.next.previous = node.previous;
        }
        node.previous = null;
        node.data = null;
        node.next = null;
        size--;
    }

    //编写一个内部类实现Iterator
    @Override
    public Iterator iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E> {
        MyLinkedList.Node node = first;

        @Override
        public boolean hasNext() {
            return node != null;
        }

        @Override
        public E next() {
            node = node.next;
            return (E) node.data;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

public class LinkedListTest {
    @Test
    public void test() throws Exception{
        LinkedList<String> list = new LinkedList<>();
        list.add("hello");
        list.add("world");
        list.add(0,"haha");
        list.add(1,"xixi");
        System.out.println(list);
    }

    @Test
    public void test1() throws Exception{
        LinkedList<String> list = new LinkedList<>();
        list.add("hello");
        list.add("world");
        list.add(0,"haha");
        list.add(1,"xixi");
        list.remove("hello");
        System.out.println(list);
        list.remove("didi");
        System.out.println(list);
    }

    @Test
    public void test2() throws Exception{
        LinkedList<String> list = new LinkedList<>();
        list.add("hello");
        list.add("world");
        list.add(0,"haha");
        list.add(1,"xixi");
        list.remove(null);
        System.out.println(list);
    }

    @Test
    public void test3() throws Exception{
        LinkedList<String> list = new LinkedList<>();
        list.add("hello");
        list.add("world");
        list.add(0,"haha");
        list.add(1,"xixi");
        for (String s : list) {
            System.out.println(s);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47