1 原理介绍

链表和数组的区别在于，数组的插入和删除操作需要整个数组一起跟着动，这样的效率很低。举个例子：打麻将时，当有一个麻将子，其大小正好在已经排序好的麻将中间，如果需要插入进原来的麻将序列，那么需要将之前或者之后的麻将全部移动，这样很费时间，所以链表可以弥补这种不足。

1.1 增

链表的插入操作包括两种：

  • 直接在末尾追加
  • 在中间的某个位置插入

如下图所示，两种方式需要单独考虑。

示意图

1.2 删

链表的删除，也包括两种：

  • 直接删除末尾的节点
  • 删除中间的节点

方式1删除：

使用两个指针，一个指针指向当前的节点，一个指针指向当前节点的前驱节点，前驱节点的后驱直接指向点前节点的后驱，即可实现删除功能。

方式1删除

方式2删除：

只使用一个指针，将当前节点的后一个节点的数据赋值到当前节点，并将当前节点的后驱指向后一个节点的后一个节点。

方式2 删除

1.3 改

修改其实就是先查找是否有需要修改的这个数据，如果没有这个数据返回false，否则就修改数据。

1.4 查

查找数据也是一个一个遍历，但是如果链表有重复数据的话，只会返回第一次查找的数据。

2 代码实现

2.1 创建链表

链表中的节点的定义：

1
2
3
4
5
6
7
8
9
10
11
class Node {
        T data;
        Node next = null;//下一个节点

        public Node(T data) {
            this.data = data;
        }

        public Node() {
        }
    }

2.2 插入元素

首先判断是否是一个空链表，如果是，则创建新链表，并将数据赋值给新节点，否则在末尾追加，或者在中间任意位置处插入。

  • 在末尾追加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean add(T data) {
        Node newNode = new Node(data);
        if (null == head) {
            head = newNode;
            return true;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
        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
public boolean insert(int index, T data) {
        Node newNode = new Node(data);
        //if index=1, special opearate
        if (index == 1) {
            if (head == null) { //head is not existed
                head = newNode;
                return true;
            } else { //head is existed
                Node temp = head;
                newNode.next = temp;
                head = newNode;
                return true;
            }
        }
        //index not true -> false
        if (index < 1 || index > this.length()) {
            return false;
        }
        int count = 1;//count the current node
        Node temp = head;
        while (count < index) {
            count += 1;
            temp = temp.next;
        }
        newNode.next = temp.next;
        temp.next = newNode;
        length++;
        return true;
    }

2.3 删除元素

2.3.1 方法1

上面介绍过了方式1的删除方式，这里主要展示关键代码实现：

1
2
3
4
5
6
7
8
9
10
Node pre = head;
Node cur = head.next;
while (cur != null) {
    if (cur.data == data) {
        foundNum++;
        pre.next = cur.next;
    }
    pre = cur;
    cur = cur.next;
}
2.3.2 方法2

关键代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Node temp = head;
while (temp != null) {
    if (temp.data == data) {
        foundNum += 1;

        T tempData = temp.data;
        temp.data = temp.next.data;
        temp.next.data = tempData;
        temp.next = temp.next.next;

        length--;
        return true;
    }
    temp = temp.next;
}

2.4 查询元素

对着链表中的元素一个一个遍历，直到找到为止，如果找不到则返回false：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int search(T data) {
        if (length == 0) {
            return -1;
        }
        int index = 0;
        int foundIndex = 0;
        Node temp = head;
        while (temp.next != null) {
            index++;
            if (temp.next.data == data) {
                foundIndex++;
                return index;
            }
            temp = temp.next;
        }
        if (foundIndex == 0)
            return -1;
        return index;
    }

2.5 打印元素

1
2
3
4
5
6
7
8
public boolean printNode() {
        Node temp = head;
        while (temp.next != null) {
            System.out.print(temp.next.data + "\t");
            temp = temp.next;
        }
        return true;
    }

2.6 获取长度

定义了一个全局变量，用来存储链表的长度，当插入元素成功之后，自加1，删除之后自减1,。

3 完整代码

MyLinkNode.java文件：

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
public class MyLinkNode<T> {
    private int length = 0;

    Node head = new Node();

    public Node getHead() {
        return head;
    }

    class Node {
        T data;
        Node next = null;//下一个节点

        public Node(T data) {
            this.data = data;
        }

        public Node() {
        }
    }

    public boolean add(T data) {
        Node newNode = new Node(data);
        if (null == head) {
            head = newNode;
            return true;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
        length++;
        return true;
    }

    public boolean insert(int index, T data) {
        Node newNode = new Node(data);
        //if index=1, special opearate
        if (index == 1) {
            if (head == null) { //head is not existed
                head = newNode;
                return true;
            } else { //head is existed
                Node temp = head;
                newNode.next = temp;
                head = newNode;
                return true;
            }
        }
        //index not true -> false
        if (index < 1 || index > this.length()) {
            return false;
        }
        int count = 1;//count the current node
        Node temp = head;
        while (count < index) {
            count += 1;
            temp = temp.next;
        }
        newNode.next = temp.next;
        temp.next = newNode;
        length++;
        return true;
    }

    public boolean printNode() {
        Node temp = head;
        while (temp.next != null) {
            System.out.print(temp.next.data + "\t");
            temp = temp.next;
        }
        return true;
    }

    public int length() {
        return length;
    }

    public boolean delete(T data) {
        if (head == null) {
            return false;
        }
        int foundNum = 0;
        /*
        方式1：
        使用两个指针，一个指针指向当前指针，一个指针当前指针的前驱，当删除时，直接忽略需要删除的节点即可
         */
        Node pre = head;
        Node cur = head.next;
        while (cur != null) {
            if (cur.data == data) {
                foundNum++;
                pre.next = cur.next;
            }
            pre = cur;
            cur = cur.next;
        }
        /*
        方式2：将要删除的节点(假设要删除的节点的位置3)的下一个节点（位置是4）的数据赋值到当前要删除的节点，
        此时当前节点（位置是3）的数据是下一节点（位置是4）的数据，然后将当前节点（位置是3）的后驱指向一下节点（位置是4）
        的下一节点（位置是5）
         */
//        Node temp = head;
//        while (temp != null) {
//            if (temp.data == data) {
//                foundNum += 1;
//
//                T tempData = temp.data;
//                temp.data = temp.next.data;
//                temp.next.data = tempData;
//                temp.next = temp.next.next;
//
//                length--;
//                return true;
//            }
//            temp = temp.next;
//        }

        if (foundNum == 0) {
            System.out.println("not found data ->" + data);
            return false;
        }
        length--;
        return true;
    }

    public boolean delete(int index) {
        if (index == 1) {

            Node temp = head;
            head = temp.next;
            System.out.println(head.data + "---" + head.next.toString());
            return true;
        }
        if (index < 1 || index >= this.length()) {
            return false;
        }
        int count = 0;
        Node temp = head;
        while (count < index) {
            count++;
            temp = temp.next;
        }
        temp.next = temp.next.next;
        length--;

        return true;
    }



    public int search(T data) {
        if (length == 0) {
            return -1;
        }
        int index = 0;
        int foundIndex = 0;
        Node temp = head;
        while (temp.next != null) {
            index++;
            if (temp.next.data == data) {
                foundIndex++;
                return index;
            }
            temp = temp.next;
        }
        if (foundIndex == 0)
            return -1;
        return index;
    }

    public boolean update(T oldData, T data) {
        if (length == 0)
            return false;
        int foundNum = 0;
        Node temp = head;
        if (oldData instanceof String) {
            while (temp.next != null) {
                if ((oldData.equals(temp.data))) {
                    foundNum++;
                    temp.data = data;
                    return true;
                }
                temp = temp.next;
            }
        } else if (oldData instanceof Number) {
            while (temp.next != null) {
                if (temp.data == oldData) {
                    foundNum++;
                    temp.data = data;
                    return true;
                }
                temp = temp.next;
            }
        }
        if (foundNum == 0)
            return false;
        return true;

    }
}

测试java文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class TestLink {
    public static void main(String[] args) {
        MyLinkNode<String> myLinkNode = new MyLinkNode<>();
        myLinkNode.add("1");
        myLinkNode.add("2");
        myLinkNode.add("3");
        myLinkNode.add("4");
        myLinkNode.insert(3,"insert");
        myLinkNode.printNode();
        System.out.println("length="+myLinkNode.length());
        System.out.println("\n");
        myLinkNode.delete("insert");
        myLinkNode.printNode();
        System.out.println("length="+myLinkNode.length());

    }
}

写在最后

欢迎大家关注鄙人的公众号【麦田里的守望者zhg】，让我们一起成长，谢谢。
微信公众号