avatar
文章
40
标签
36
分类
18
主页
时间轴
标签
类别
友链
娱乐
关于
Hobo's blog
主页
时间轴
标签
类别
友链
娱乐
关于
手写LinkedList（仿照源码）
|Java基础
字数总计:2.2k|阅读时长: 10 分钟
|阅读量:|评论数:

LinkedList简述

LinkedList底层使用一个Node数据结构，有前后两个指针，双向链表实现的。相对数组，链表插入效率较高，只需要更改前后两个指针即可；另外链表不存在扩容问题，因为链表不要求存储空间连续，每次插入数据都只是改变last指针；另外，链表所需要的内存比数组要多，因为他要维护前后两个指针；它适合删除，插入较多的场景。

LinkedList是一个继承于AbstractSequentialList的双向链表。

  1. 它也可以被当作堆栈、队列或双端队列进行操作;
  2. 继承了AbstractSequentialList,这个类提供了一个基本的List接口实现，为实现序列访问的数据储存结构的提供了所需要的最小化的接口实现。对于支持随机访问数据的List比如数组，应该优先使用AbstractList。
  3. 实现 List 接口，List是Collection的子接口，它是一个元素有序(按照插入的顺序维护元素顺序)、可重复、可以为null的集合;
  4. 实现 Deque 接口，即能将LinkedList当作双端队列使用;
  5. 实现了Cloneable接口，即覆盖了函数clone()，能克隆;
  6. 实现java.io.Serializable接口，支持序列化;
    非同步;
    1
    2
    3
    public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable {...}

手写实现

Node类

在MyLinkedList类中定义Node节点类（静态内部类）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static class Node<E> {
	//前节点   
	 Node<E> prev;
	 //当前节点
	 E item;
	 //后节点
	 Node<E> next;
	
	 public Node(Node<E> prev, E item, Node<E> next) {
	     this.item = item;
	     this.prev = prev;
	     this.next = next;
	 }
 }

定义MyLinkedList的属性

size（长度）、first（头节点）、last（尾节点）

1
2
3
4
5
6
7
8
9
10
public class MyLinkedList<E> {
    //链表的长度
    int size = 0;
    //链表的头部   
    Node<E> first;
     //链表的尾部
    Node<E> last;
	
	...
}

定义增删改查方法

插入

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
/**
    * 在链表尾部插入
    * @param e
    */
   public void add(E e) {
       //创造节点，将节点连接链表
       Node<E> newNode = new Node<E>(last, e, null);
       //链表连接节点
       if (last == null) {
           //链表为空
           //新节点赋值给头节点
           first = newNode;
       } else {
       	//链表不为空
           //将当前链表last的下一个节点指向新节点（连接）  last-->newNode
           last.next = newNode;
       }
       //将新节点变为尾节点
       last = newNode;
       size++;
   }
/**
    * 根据索引插入
    *
    * @param index
    * @param e
    */
   public void add(int index, E e) {
   	//当前索引下的节点
       Node<E> succ = getNode(index);
       //前继节点
       Node<E> prev = succ.prev;
       //创建新节点并连接链表
       Node<E> newNode = new Node<>(prev, e, succ);
       //将链表连接新节点
       succ.prev = newNode;
       if (prev == null) {
       	//如果prev为空，则表示链表为空，则新节点赋值给首节点
           first = newNode;
       } else {
       	//prev的前节点连接新节点
           prev.next = newNode;
       }
       size++;
   }
   /**
    * 将集合c中数据在链表末尾添加
    *
    * @param c
    * @return
    */
   public boolean addAll(Collection<? extends E> c) {
       return addAll(size, c);
   }

   /**
    * 将集合c中数据在链表指定位置添加
    *
    * @param index
    * @param c
    * @return
    */
   public boolean addAll(int index, Collection<? extends E> c) {
       //检查index是否合法
       if (index < 0 && index > size) {
           throw new IndexOutOfBoundsException("指定的位置不合法：" + index);
       }
       Object[] items = c.toArray();
       int length = items.length;
       if (length == 0) {
           return false;
       }
       Node<E> succ, prev;
       //获得当前索引下的节点和前节点
       if (index == size) {
           succ = null;
           prev = last;
       } else {
           succ = getNode(index);
           prev = succ.prev;
       }
       //插入
       for (Object item : items) {
           E e = (E) item;
           Node<E> newNode = new Node<E>(prev, e, null);
           if (prev == null) {
               first = newNode;
           } else {
               prev.next = newNode;
           }
           prev = newNode;

       }
       //定义尾节点
       if (succ == null) {
           last = prev;
       } else {
           prev.next = succ;
           succ.prev = prev;
       }
       size += length;
       return true;
   }

查询

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
 /**
    * 根据索引获取节点
    *
    * @param index
    * @return
    */
   Node<E> getNode(int index) {
       //首先判断index是否合法
       //size>>1 相当于 size/(2的1次方)
       if (index < (size >> 1)) {
           //从头部开始找
           Node<E> x = first;
           for (int i = 0; i < index; i++) {
               x = x.next;
           }
           return x;
       } else {
           //从尾部开始找
           Node<E> x = last;
           for (int i = size - 1; i > index; i--) {
               x = x.prev;
           }
           return x;
       }
   }
/**
    * 根据索引查询数据
    *
    * @param index
    * @return
    */
   public E get(int index) {
       //首先判断index是否合法
       checkElementIndex(index);
       return getNode(index).item;
   }

修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
    * 根据索引修改
    *
    * @param index
    * @param e
    * @return 返回先前位于指定位置的元素
    */
   public E set(int index, E e) {
       checkElementIndex(index);
       //获取当前索引下的节点，并且修改为新数据
       Node<E> succ = getNode(index);
       E oldVal = succ.item;
       succ.item = e;
       return oldVal;
   }

删除

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
/**
 * 根据索引删除
 *
 * @param index
 * @return
 */
public E remove(int index) {
    checkElementIndex(index);
    //当前索引下的节点
    Node<E> succ = getNode(index);
    //前继节点
    Node<E> prev = succ.prev;
    //后继节点
    Node<E> next = succ.next;
    if (prev == null) {
    	//删除的为头节点
        first = next;
    } else {
        prev.next = next;
        succ.prev = null;
    }

    if (next == null) {
    	//删除的为尾节点
        last = prev;
    } else {
        next.prev = prev;
        succ.next = null;
    }
    size--;
    return succ.item;
}

实现代码（全）

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
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
package com.clh.test.mylist;

import java.util.Collection;

/**
 * 手写LinkedList
 * LinkedList是java中的双向链表， 是List接口链表的实现，特点是增删快，查找慢。
 *
 * @author 华华
 * @date 2020/4/27
 **/
public class MyLinkedList<E> {

    /**
     * 链表的长度
     */
    int size = 0;
    /**
     * 链表的头部
     */
    Node<E> first;
    /**
     * 链表的尾部
     */
    Node<E> last;

    public MyLinkedList() {
    }

    public MyLinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    public int size() {
        return size;
    }

    /**
     * 将集合c中数据在链表末尾添加
     *
     * @param c
     * @return
     */
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

    /**
     * 将集合c中数据在链表指定位置添加
     *
     * @param index
     * @param c
     * @return
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        //检查index是否合法
        if (index < 0 && index > size) {
            throw new IndexOutOfBoundsException("指定的位置不合法：" + index);
        }
        Object[] items = c.toArray();
        int length = items.length;
        if (length == 0) {
            return false;
        }
        Node<E> succ, prev;
        //获得当前索引下的节点和前节点
        if (index == size) {
            succ = null;
            prev = last;
        } else {
            succ = getNode(index);
            prev = succ.prev;
        }
        //插入
        for (Object item : items) {
            E e = (E) item;
            Node<E> newNode = new Node<E>(prev, e, null);
            if (prev == null) {
                first = newNode;
            } else {
                prev.next = newNode;
            }
            prev = newNode;

        }
        //定义尾节点
        if (succ == null) {
            last = prev;
        } else {
            prev.next = succ;
            succ.prev = prev;
        }
        size += length;
        return true;
    }

    /**
     * 在链表尾部插入
     *
     * @param e
     */
    public void add(E e) {
        //创造节点，将节点连接链表
        Node<E> newNode = new Node<E>(last, e, null);
        //链表连接节点
        if (last == null) {
            //表示链表为空时新节点赋值给首节点
            first = newNode;
        } else {
            //将当前链表last的下一个节点指向新节点（连接）  last-->newNode
            last.next = newNode;
        }
        //将新节点变为尾节点
        last = newNode;
        size++;
    }

    /**
     * 根据索引插入
     *
     * @param index
     * @param e
     */
    public void add(int index, E e) {
        Node<E> succ = getNode(index);
        Node<E> prev = succ.prev;
        Node<E> newNode = new Node<>(prev, e, succ);
        succ.prev = newNode;
        if (prev == null) {
            first = newNode;
        } else {
            prev.next = newNode;
        }
        size++;
    }

    /**
     * 根据索引查询数据
     *
     * @param index
     * @return
     */
    public E get(int index) {
        //首先判断index是否合法
        checkElementIndex(index);
        return getNode(index).item;
    }

    /**
     * 根据索引获取节点
     *
     * @param index
     * @return
     */
    Node<E> getNode(int index) {
        //首先判断index是否合法
        //size>>1 相当于 size/(2的1次方)
        if (index < (size >> 1)) {
            //从头部开始找
            Node<E> x = first;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            //从尾部开始找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }
    }

    /**
     * 判断参数是否为当前链表的索引
     *
     * @param index
     */
    private void checkElementIndex(int index) {
        if (index >= 0 && index < size) {
            return;
        } else {
            throw new IndexOutOfBoundsException("index不合法！！index:" + index + ",size:" + size);
        }
    }

    /**
     * 根据索引修改
     *
     * @param index
     * @param e
     * @return 返回先前位于指定位置的元素
     */
    public E set(int index, E e) {
        checkElementIndex(index);
        Node<E> succ = getNode(index);
        E oldVal = succ.item;
        succ.item = e;
        return oldVal;
    }

    /**
     * 根据索引删除
     *
     * @param index
     * @return
     */
    public E remove(int index) {
        checkElementIndex(index);
        Node<E> succ = getNode(index);
        Node<E> prev = succ.prev;
        Node<E> next = succ.next;
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            succ.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            succ.next = null;
        }
        size--;
        return succ.item;
    }

    /**
     * 节点类
     *
     * @param <E>
     */
    private static class Node<E> {
        /**
         * 前节点
         */
        Node<E> prev;
        //当前节点
        E item;
        //后节点
        Node<E> next;

        public Node(Node<E> prev, E item, Node<E> next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }
}

总结

LinkedList的插入思路就是将新节点连接链表、再将链表连接新节点，如果是根据索引插入就要判断索引是否合法，是否在首部或尾部进行插入。删改查都差不多

文章作者: Hobo
文章链接: https://hobo-clh.github.io/2020/04/28/%E6%89%8B%E5%86%99LinkedList/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Hobo's blog！
Java集合链表
打赏
  • 微信
    微信
  • 支付宝
    支付宝
相关推荐
2020-06-09
环形链表以及约瑟夫问题
2020-06-09
单链表以及常见算法题
2020-05-04
HashMap在JDK1.7和1.8的区别
2020-04-29
手写ArrayList（仿照源码）
评论
繁