Java链表_手写一个LinkedList

发表于 分类于 阅读次数： 本文字数： 7k 阅读时长 ≈ 6 分钟
引言：数据结构——链表

LinkedList

在线性表家族中，

对于数组、栈、队列来说，他们虽然实现了动态，但底层却还是静态的

但是对于链表来说，它是真正的动态，但失去了随机读取的功能

方法如下
image

代码如下：

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
/**
 * 手写一个链表
 * @author BlackKnight
 */
public class LinkedList<E>{
    /**
     * 链表的核心——结点
     * 私有内部类
     */
    private class Node{
        public E e;
        public Node next;

        /**
         * 方便我的LinkedList类来访问结点
         * 有多个重载方法
         * @param e
         * @param next
         */
        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e,null);
        }

        public Node() {
            this(null,null);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "e=" + e +
                    ", next=" + next +
                    '}';
        }
    }

    private Node head;
    private int size;

    public LinkedList() {
        this.head = null;
        this.size = 0;
    }
    public int getSize(){
        return size;
    }
    public boolean isEmpty(){
        return size==0;
    }

    /**
     * 向链表头添加结点
     * @param e
     */
    public void addFirst(E e){
        /*不同于数组在末尾添加元素，链表更容易在头head添加元素
          将一个元素添加到一个链表的头部，其实只需要两步就能完成
            1. 将要插入的结点的next指向当前链表的head
            2. 再把head重新指向被插入结点
         */
        //Node node = new Node(e);
        //node.next = head;
        //head = node;
        //上述三行代码可以更 优雅 ，一行就可以完成
        head = new Node(e,head);
        size++;
    }

    /**
     * 向链表中间添加结点
     * @param index
     * @param e
     */
    public void add(int index, E e){
        if(index<0||index>size){
            throw new IllegalArgumentException("无效的index");
        }
        //如果要放在第0个位置上，就需要判断一下，因为没有第-1个结点
        //但是我们可以单独设置一个 虚拟头结点 来避免这种判断
        if(index==0){
            addFirst(e);
        }else {
            Node prev = head;
            //插入的核心：找到所要插入位置的前一个结点！
            //这里的循环条件注意要理解，不理解可以画画图，举举例子
            for(int i=0; i < index - 1 ;i++){
                prev = prev.next;
            }
            //Node node = new Node(e);
            //node.next = prev.next;
            //prev.next = node;
            //同样，可以更加的优雅
            prev.next = new Node(e,prev.next);
            size++;
        }
    }

    public void addLast(E e){
        add(size,e);
    }

}

上述的代码并没有写完，因为在使用过程中，带有虚拟头结点的链表是非常多的，所以我们下面来写使用带有虚拟头结点的链表

真正的代码如下：

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
package linkedList;

import java.util.StringJoiner;

/**
 * 手写一个链表
 * @author BlackKnight
 */
public class LinkedList<E>{
    /**
     * 链表的核心——结点
     * 私有内部类
     */
    private class Node{
        public E e;
        public Node next;

        /**
         * 方便我的LinkedList类来访问结点
         * 有多个重载方法
         * @param e
         * @param next
         */
        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e,null);
        }

        public Node() {
            this(null,null);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "e=" + e +
                    ", next=" + next +
                    '}';
        }
    }

    private Node dummyHead;
    private int size;

    public LinkedList() {
        //虚拟头结点
        this.dummyHead = new Node(null,null);
        this.size = 0;
    }
    public int getSize(){
        return size;
    }
    public boolean isEmpty(){
        return size==0;
    }

    /**
     * 向链表中间添加结点
     * @param index
     * @param e
     */
    public void add(int index, E e){
        if(index<0||index>size){
            throw new IllegalArgumentException("无效的index");
        }
        //设置一个了虚拟头结点 避免判断是不是要插在0的位置上
        Node prev = dummyHead;
        //插入的核心：找到所要插入位置的前一个结点！
        //这里的循环条件注意要理解，不理解可以画画图，举举例子
        for(int i=0; i < index ;i++){
            //因为我们从虚拟头结点开始遍历，条件就不再是 index-1 了
            prev = prev.next;
        }
        //Node node = new Node(e);
        //node.next = prev.next;
        //prev.next = node;
        //同样，可以更加的优雅
        prev.next = new Node(e,prev.next);
        size++;
    }

    /**
     * 向链表头添加结点
     * @param e
     */
    public void addFirst(E e){
        /*
        因为使用了虚拟头结点，所以直接可以复用add方法了
         */
        add(0,e);
        size++;
    }

    /**
     * 向链表位添加结点
     * @param e
     */
    public void addLast(E e){
        add(size,e);
    }

    /**
     * 获得链表第index个元素
     * 并不常用
     * @param index
     * @return
     */
    public E get(int index){
        if(index<0||index>size){
            throw new IllegalArgumentException("无效的index");
        }
        /*
        不同于插入时的遍历，这里的遍历需要遍历到index，而不是index的前一个
         */
        Node cur = dummyHead.next;
        //这里直接赋值到了第0个结点
        for(int i=0 ;i<index;i++){
            cur = cur.next;
        }
        return cur.e;
    }

    public E getFirst(){
        return get(0);
    }
    public E getLast(){
        return get(size);
    }

    /**
     * 修改的方法
     * @param index
     * @param e
     */
    public void set(int index , E e){
        if(index<0||index>size){
            throw new IllegalArgumentException("无效的index");
        }
        Node cur = dummyHead.next;
        for(int i=0 ;i<index;i++){
            cur = cur.next;
        }
        cur.e = e;
    }

    /**
     * 查找
     * @param e
     * @return
     */
    public boolean contains(E e){
        Node cur = dummyHead.next;
        while (cur!=null){
            if(cur.e.equals(e)){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public String toString() {
        StringJoiner sj = new StringJoiner("->","LinkedList: dummyHead->[","]->null");
        Node cur = dummyHead.next;
        while (cur!=null){
            sj.add(cur.e+"");
            cur = cur.next;
        }
        return sj.toString();
    }

    /**
     * 删除一个结点
     * @param index
     * @return
     */
    public E remove(int index){
        if(index<0||index>size){
            throw new IllegalArgumentException("无效的index");
        }
        Node prev = dummyHead;
        /*
        删除一个结点，也是要找要删除结点的前一个结点
         */
        for(int i = 0;i < index;i++){
            prev = prev.next;
        }
        Node ret = prev.next;
        prev.next = prev.next.next;

        //将被删除结点从链表中分离出来
        ret.next = null;
        size--;
        return ret.e;
    }

    public E removeFirst(){
        return remove(0);
    }
    public E removeLast(){
        return remove(size-1);
    }

}

复杂度分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
方法名                  | 时间复杂度 |
--------------------------------------
add()                   |     O(n)   |
addFirst()              |     O(1)   | 
addLast()               |     O(n)   |
--------------------------------------      
remove()                |     O(n)   |
removeFirst()           |     O(1)   |
removeLast()            |     O(n)   |
--------------------------------------
get()                   |     O(n)   |
isEmpty()               |     O(1)   |
contains()              |     O(n)   |
--------------------------------------
set()                   |     O(n)   |

注意：O(n/2) = O(n)

由此可见，除了少数对头操作的方法外，几乎所有的方法，时间复杂度都是O(n)

剖析虚拟头结点的作用

LeetCode中有一道题

删除链表中等于给定值 val 的所有节点。

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

这里有两种不同的解决办法

不用虚拟头结点

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
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //假如一开始就出现了val
        //注意，当删除完一个结点后，不用再移动结点了
        while(head!=null && head.val==val){
            ListNode del = head;
            head = head.next;
            del.next = null;
        }

        if(head==null){
            return null;
        }

        ListNode prev = head;

        //这里删除中间出现的val
        while(prev.next!=null){
            if(prev.next.val == val){
                ListNode delNode = prev.next;
                prev.next = prev.next.next;
                delNode.next = null;
            }
            else prev = prev.next;
        }
        return head;
    }
}

使用虚拟头结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode prev = dummyHead;
        //这里删除中间出现的val
        while(prev.next!=null){
            if(prev.next.val == val){
                ListNode delNode = prev.next;
                prev.next = prev.next.next;
                delNode.next = null;
            }
            else prev = prev.next;
        }
        return dummyHead.next;
    }
}

区别

使用虚拟头结点，可以不用再讨论head的特殊性，因为此时所有的结点都有一个前置的结点

返回的时候返回虚拟头结点的next即可

所以我们可以有如下总结

  • 如果只是操作头结点，则我们可以不使用虚拟头结点
  • 如果要对中间的结点进行操作，使用虚拟头结点可以避免分类讨论
  • 两者可以互换，但要注意条件

参考资料

参考资料：
来自慕课liuyubobobo的教程