动手实现基础的ArrayList和LinkedList

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

动手实现基础的ArrayList和LinkedList

基础

  1. ArrayList:顺序列表,它是 Array 的增强版,也称动态数组,提供了动态的增加和减少数组,如果你阅读过它的源码,你会发现它内部就是采用数组来存储数据,并且动态扩容数组的长度,在日常开发中被广泛使用。

  2. LinkedList:线性列表,但是和 ArrayList 不同的是,它采用了双向链表的数据结构,既然是链表的结构,那么就不需要考虑它的容量问题。

  3. 各自的优缺点:

    • ArrayList采用数组的结构,在添加和删除操作上的效率低,需要大量移动数组中的元素,但是在查找的效率高;

    • LinkedList采用了链表的结构,在查找的方面效率极低,添加和删除的方面效率高;

    • LinkedList占用内存比ArrayList更高,因为它的结点不仅村粗了数据,并且存储了前一节点和后一节点的引用。

制定手写方案:

  1. 两种列表都需要有:添加、删除、查找、清空、判空、循环遍历和获取大小的共有的方法;

  2. LinkedList 添加元素的方法需要区分类型:头部添加,尾部添加,指定下标添加;ArrayList 也需要有添加整个数组的方法;

  3. LinkedList 在本次的方案中采用的是单向链表而不是双向链表的结构。

手写ArrayList:

  1import java.util.Arrays;
2import java.util.function.Consumer;
3
4class ArrayList<E{
5
6
7    // 用于保存空列表的引用
8    private static final Object[] EMPTY_ELEMENTDATA = {};
9
10    private Object[] _data;
11    private int _size;
12    private int _realLength;
13
14    // 列表默认的长度
15    private static final int LEN = 20;
16
17    public ArrayList(int initLen) {
18        if (initLen == 0) {
19            this._data = EMPTY_ELEMENTDATA;
20        } else if (initLen > 0) {
21            this._data = new Object[initLen];
22        } else {
23            throw new IllegalArgumentException("init length is error");
24        }
25        this._size = initLen;
26        this._realLength = 0;
27    }
28
29    public ArrayList() {
30        this(LEN);
31    }
32
33    /**
34     * 追加一个元素
35     *
36     * @param element 元素
37     */

38    public void add(E element) {
39        checkLen();
40        _data[_realLength++] = element;
41    }
42
43    /**
44     * 指定下标插入
45     *
46     * @param index   下标
47     * @param element 元素
48     */

49    public void add(int index, E element) {
50        checkIndex(index);
51        checkLen();
52        System.arraycopy(_data, index, _data, index + 1, _realLength - index);
53        _data[index] = element;
54        _realLength++;
55    }
56
57    /**
58     * 添加一个数组
59     *
60     * @param elements 数组元素
61     */

62    public void addAll(E[] elements) {
63        for (E e : elements) {
64            checkLen();
65            _data[_realLength++] = e;
66        }
67    }
68
69    /**
70     * 获取指定下标的元素
71     *
72     * @param index 下标
73     * @return 下标对应的元素
74     */

75    @SuppressWarnings("unchecked")
76    public E get(int index) {
77        checkIndex(index);
78        return (E) _data[index];
79    }
80
81    /**
82     * 删除指定下标的元素
83     *
84     * @param index 下标
85     * @return 删除的元素
86     */

87    @SuppressWarnings("unchecked")
88    public E remove(int index) {
89        checkIndex(index);
90        Object delete = _data[index];
91        System.arraycopy(_data, index + 1, _data, index, _realLength - index - 1);
92        _data[--_realLength] = null;
93        return (E) delete;
94    }
95
96    /**
97     * 判断是否包含某个元素
98     *
99     * @param element 元素
100     * @return 包含返回true
101     */

102    public boolean contain(E element) {
103        if (isEmpty()) return false;
104        else {
105            for (Object e : _data) {
106                if (e == element) {
107                    return true;
108                }
109            }
110            return false;
111        }
112    }
113
114    /**
115     * 循环遍历列表
116     *
117     * @param consumer Consumer对象
118     */

119    public void forEach(Consumer<E> consumer) {
120        if (isEmpty()) {
121            return;
122        }
123        for (Object object : _data) {
124            if (object != null)
125                consumer.accept((E) object);
126        }
127    }
128
129    /**
130     * 清空列表元素
131     */

132    public void clear() {
133        for (int i = 0; i < _realLength; i++) {
134            _data[i] = null;
135        }
136        _realLength = 0;
137    }
138
139    /**
140     * 检查下标是否越界
141     *
142     * @param index 下标
143     */

144    private void checkIndex(int index) {
145        if (index < 0 || index > _realLength) {
146            throw new IndexOutOfBoundsException();
147        }
148    }
149
150    public boolean isEmpty() {
151        return _realLength == 0;
152    }
153
154    public int size() {
155        return _realLength;
156    }
157
158    /**
159     * 检查是否要扩容数组
160     *
161     * @return true 表示需要扩容
162     */

163    private void checkLen() {
164        if (_realLength >= _size) {
165            grow();
166        }
167
168
169    /**
170     * 数组的扩容,扩容大小为原先的2倍
171     */

172    private void grow() {
173        // 扩容后size也要变化
174        _size = _size * 2;
175        _data = Arrays.copyOf(_data, _size);
176    }
177
178    public static void main(String[] args) {
179        ArrayList<Integer> arrayList = new ArrayList<>();
180        arrayList.add(1);
181        arrayList.add(12);
182        arrayList.add(3);
183        arrayList.add(14);
184        System.out.print("原始数据:");
185        arrayList.forEach(element -> System.out.print(element + " "));
186        System.out.println();
187        arrayList.remove(1);
188        System.out.print("移除index=1的元素:");
189        arrayList.forEach(element -> System.out.print(element + " "));
190        System.out.println();
191        System.out.println("list has {1}: " + arrayList.contain(1));
192        System.out.println("list has {10}: " + arrayList.contain(10));
193    }
194}
195
196// 原始数据:1 4 2 3 
197// 移除index=1的元素:1 2 3 
198// list has {1}: true
199// list has {10}: false

如上所述,在组织一个 ArrayList 的过程中,我们特别注意以下几点:

  1. 既然采用数组,那么就要注意它的容量问题,做好扩容的工作;

  2. 使用数组的过程中,千万别忘记处理数组越界问题;

  3. 在删除固定的元素后,别忘记了手动置空下。

实现一个简单的 ArrayList 还是挺简单的,自己动手写一遍会对 ArrayList 有另一番见解,快去动手敲一敲吧。

手写LinkedList:

  1import java.util.function.Consumer;
2
3class LinkedList<E{
4
5    // 列表的长度
6    private int _size;
7    // 头结点
8    private Node<E> _first;
9    // 尾结点
10    private Node<E> _last;
11
12    public LinkedList() {
13        _size = 0;
14    }
15
16    /**
17     * 在尾巴插入一个结点
18     *
19     * @param element 插入的数据
20     */

21    public void addLast(E element) {
22        final Node<E> l = _last;
23        final Node<E> newNode = new Node<>(element, null);
24        _last = newNode;
25        if (l == null) {
26            // 如果之前的尾部元素为空,那说明列表为空,插入元素后,首尾应该都是newNode
27            _first = newNode;
28        } else {
29            l.next = newNode;
30        }
31        _size++;
32    }
33
34    /**
35     * 在头部插入元素
36     *
37     * @param element 插入的数据
38     */

39    public void addFirst(E element) {
40        final Node<E> f = _first;
41        final Node<E> newNode = new Node<>(element, _first);
42        _first = newNode;
43        if (f == null) {
44            // 如果之前的头部元素为空,那说明列表为空,插入元素后,首尾应该都是newNode
45            _last = newNode;
46        } else {
47            newNode.next = f;
48        }
49        _size++;
50    }
51
52    /**
53     * 添加一个元素,默认在尾巴添加
54     *
55     * @param element 元素值
56     */

57    public void add(E element) {
58        addLast(element);
59    }
60
61    /**
62     * 指定下标插入元素
63     *
64     * @param index   下标
65     * @param element 元素值
66     */

67    public void add(int index, E element) {
68         // 特殊处理头尾
69        if (index == 0) {
70            addFirst(element);
71            return;
72        }
73        if (index == size() - 1) {
74            addLast(element);
75            return;
76        }
77        Node<E> newNode = new Node<>(element, null);
78        Node<E> pre = _first;
79        Node<E> next = _first.next;
80        for (int i = 1; i < size() - 1; i++) {
81            if (i == index) {
82                newNode.next = next;
83                pre.next = newNode;
84                _size++;
85            }
86            pre = next;
87            next = next.next;
88        }
89    }
90
91    /**
92     * 获取指定下标的元素值
93     *
94     * @param index 下标
95     * @return 值
96     */

97    public E get(int index) {
98        checkIndex(index);
99        Node<E> f = _first;
100        for (int i = 0; i < size(); i++) {
101            if (i == index) {
102                return f.data;
103            } else {
104                f = f.next;
105            }
106        }
107        return null;
108    }
109
110    /**
111     * 移除指定下标的元素
112     *
113     * @param index 下标
114     * @return 返回移除的元素
115     */

116    public E remove(int index) {
117        checkIndex(index);
118        Node<E> f = _first;
119        Node<E> l = _first;
120        // 需特殊处理头结点
121        if (index == 0) {
122            E element = f.data;
123            f = f.next;
124            _first = f;
125            _size--;
126            return element;
127        }
128        for (int i = 0; i < size(); i++) {
129            if (i == index) {
130                E element = f.data;
131                l.next = f.next;
132                _size--;
133                f.next = null;
134                f.data = null;
135                return element;
136            } else {
137                l = f;
138                f = f.next;
139            }
140        }
141        return null;
142    }
143
144    /**
145     * 检测是否包含某个元素
146     *
147     * @param element 包含的对象
148     * @return 包含返回true
149     */

150    public boolean contain(E element) {
151        if (!isEmpty()) {
152            Node<E> f = _first;
153            for (int i = 0; i < size(); i++) {
154                if (f.data == element) return true;
155                f = f.next;
156            }
157            return false;
158        } else {
159            return false;
160        }
161    }
162
163    /**
164     * 遍历整个列表
165     *
166     * @param consumer Consumer对象
167     */

168    public void forEach(Consumer<E> consumer) {
169        if (isEmpty()) {
170            return;
171        }
172        Node<E> f = _first;
173        while (f != null) {
174            E e = f.data;
175            consumer.accept(e);
176            f = f.next;
177        }
178    }
179
180    /**
181     * 清空
182     */

183    public void clear() {
184        for (Node<E> x = _first; x != null; ) {
185            Node<E> next = x.next;
186            x.data = null;
187            x.next = null;
188            x = next;
189        }
190        _first = _last = null;
191        _size = 0;
192    }
193
194    /**
195     * 列表的长度
196     *
197     * @return 长度值
198     */

199    public int size() {
200        return _size;
201    }
202
203    /**
204     * 判断列表是否为空
205     *
206     * @return 为空返回true
207     */

208    public boolean isEmpty() {
209        return _size == 0;
210    }
211
212    /**
213     * 检查下标是否越界
214     *
215     * @param index 下标
216     */

217    private void checkIndex(int index) {
218        if (index < 0 || index > _size) {
219            throw new IndexOutOfBoundsException();
220        }
221    }
222
223    /**
224     * 链表节点
225     *
226     * @param <E> 数据类型
227     */

228    static class Node<E{
229        E data;
230        Node<E> next;
231
232        Node(E data, Node<E> next) {
233            this.data = data;
234            this.next = next;
235        }
236    }
237
238    public static void main(String[] args) {
239        LinkedList<Integer> linkedList = new LinkedList<>();
240        linkedList.add(1);
241        linkedList.addFirst(0);
242        linkedList.add(2);
243        linkedList.add(3);
244        System.out.print("原始数据: ");
245        linkedList.forEach(integer -> System.out.print(integer + " "));
246        System.out.println();
247        int remove = linkedList.remove(0);
248        System.out.println("remove data is: " + remove);
249        System.out.print("删除index为0的数据: ");
250        linkedList.forEach(integer -> System.out.print(integer + " "));
251        System.out.println();
252        linkedList.add(110);
253        System.out.print("在index=1的地方添加数据10: ");
254        linkedList.forEach(integer -> System.out.print(integer + " "));
255        System.out.println();
256        System.out.println("list has {1}: " + linkedList.contain(1));
257        System.out.println("list has {100}: " + linkedList.contain(100));
258    }
259}
260// 原始数据: 0 1 2 3 
261// remove data is: 0
262// 删除index为0的数据: 1 2 3 
263// 在index=1的地方添加数据10: 1 10 2 3 
264// list has {1}: true
265// list has {10}: true

LinkedList 的实现过程中,比 ArrayList 要多出了几个操作,毕竟是链表的结构,插入元素可以分别在头部和尾部插入数据,对于熟悉链表结构的大佬来说一点,这点一点不成问题,不熟悉的小佬可以借此机会熟悉一下链表的操作。下面说一下几点注意的地方吧:

  1. 对于第一次插入数据的时候,无论实在头部还是尾部,一定要注意对 _first_last 的处理;

  2. 在指定位置添加和删除元素的时候,一定要处理好前节点和后结点之间的联系,并且在删除的操作中别忘记了将删除后的节点数据置空。

如果本文章你发现有不正确或者不足之处,欢迎你在下方留言或者扫描下方的二维码留言也可!

动手实现基础的ArrayList和LinkedList


原文始发于微信公众号(Taonce):动手实现基础的ArrayList和LinkedList