JAVA实现单链表

发表于 | 分类于 |

​ 刚开始学习java不久的时候以为java没有指针。。。不知道怎么弄链表，java中有基本数据类型和引用数据类型（其实就是指针）。如果对引用不够了解请访问 http://zwmf.iteye.com/blog/1738574 （写得特别好，就没必要重复了）。

实现链表的思路：

　　1）链表类，结点类（链表类的内部类），在main()方法创建一条链表类对象，通过方法逐步创建结点类，通过引用链接起来成为链表。

　　2）结点类包含数据和对下个结点的引用，以及可以对数据赋值的构造函数。

　　3）链表类的构造方法，只构造出不含数据的头结点。（外部类可以直接对内部类的私有成员进行访问，这样就可以直接修改引用）

主体代码：
1
2
3
4
5
6
public  class MyLink<E>{
    private class Node{
            privare Object data;         //保存数据
            private Node next;           //对下个结点的引用
        }  
}
完整版代码：
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
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
package Date_Structures.LinkedList;

public class MyLink {

    public static void main(String[] args) {
        MyLink list=new MyLink();
        list.addNode(5);
        list.addNode(3);
        list.addNode(1);
        list.addNode(2);
        list.addNode(55);
        list.addNode(36);
        System.out.println("LinkLength:"+list.linkListLength(head));
        list.printListReversely(head);
        list.traverse(head);
        list.deleteNode(head,4);
        System.out.println("after delete(4):");
        list.printListReversely(head);
        list.traverse(head);
        list.insertNode(head,4,7);
        System.out.println("after insert(4,7):");
        list.traverse(head);
    }

    static Node head=null;

    public class Node{
        //数据域
        public int data;
        //指针域，指向下一个节点
        public Node next=null;
        public Node() {
        }
        public Node(int data) {
            this.data = data;
        }
    }

    /**
     * 向链表添加数据
     *
     * @param value 要添加的数据
     */
    public void addNode(int value) {
        //初始化要加入的节点
        Node newNode = new Node(value);
        if(head==null){
            head=new Node();
        }
        //临时节点
        Node temp = head;
        // 找到尾节点
        while (temp.next != null) {
            temp = temp.next;
        }
        // 已经包括了头节点.next为null的情况了～
        temp.next = newNode;
    }

    /**
     * 遍历链表
     *
     * @param head 头节点
     */
    public void traverse(Node head) {
        //临时节点，从首节点开始
        Node temp = head.next;

        while (temp != null) {
            System.out.println("当前节点：" + temp.data);
            //继续下一个
            temp = temp.next;
        }
    }

    /**
     * 插入节点
     *
     * @param head  头指针
     * @param index 要插入的位置
     * @param value 要插入的值
     */
    public void insertNode(Node head, int index, int value) {
        //首先需要判断指定位置是否合法，
        if (index < 1 || index > linkListLength(head) + 1) {
            System.out.println("插入位置不合法。");
            return;
        }
        //临时节点，从头节点开始
        Node temp = head;
        //记录遍历的当前位置
        int currentPos = 0;
        //初始化要插入的节点
        Node insertNode = new Node(value);
        while (temp.next != null) {
            //找到上一个节点的位置了
            if ((index - 1) == currentPos) {
                //temp表示的是上一个节点
                //将原本由上一个节点的指向交由插入的节点来指向
                insertNode.next = temp.next;
                //将上一个节点的指针域指向要插入的节点
                temp.next = insertNode;
                return;
            }
            currentPos++;
            temp = temp.next;
        }

    }

    /**
     * 获取链表的长度
     * @param head 头指针
     */
    public static int  linkListLength(Node head) {
        int length = 0;
        //临时节点，从首节点开始
        Node temp = head.next;
        // 找到尾节点
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }

    /**
     * 根据位置删除节点
     *
     * @param head  头指针
     * @param index 要删除的位置
     */
    public void deleteNode(Node head, int index) {
        //首先需要判断指定位置是否合法，
        if (index < 1 || index > linkListLength(head) + 1) {
            System.out.println("删除位置不合法。");
            return;
        }
        //临时节点，从头节点开始
        Node temp = head;
        //记录遍历的当前位置
        int currentPos = 0;
        while (temp.next != null) {
            //找到上一个节点的位置了
            if ((index - 1) == currentPos) {
                //temp表示的是上一个节点
                //temp.next表示的是想要删除的节点
                //将想要删除的节点存储一下
                Node deleteNode = temp.next;
                //想要删除节点的下一个节点交由上一个节点来控制
                temp.next = deleteNode.next;
                //Java会回收它，设置不设置为null应该没多大意义了(个人觉得,如果不对请指出哦～)
                deleteNode = null;
                return;
            }
            currentPos++;
            temp = temp.next;
        }
    }

    /**
     * 对链表进行排序
     *
     * @param head
     *
     */
    public void sortLinkList(Node head) {
        Node currentNode;
        Node nextNode;
        for (currentNode = head.next; currentNode.next != null; currentNode = currentNode.next) {
            for (nextNode = head.next; nextNode.next != null; nextNode = nextNode.next) {
                if (nextNode.data > nextNode.next.data) {
                    int temp = nextNode.data;
                    nextNode.data = nextNode.next.data;
                    nextNode.next.data = temp;
                }
            }
        }
    }

    /**
     * 找到链表中倒数第k个节点(设置两个指针p1、p2，让p2比p1快k个节点，同时向后遍历，当p2为空，则p1为倒数第k个节点
     *
     * @param head
     * @param k    倒数第k个节点
     */
    public Node findKNode(Node head, int k) {
        if (k < 1 || k > linkListLength(head))
            return null;
        Node p1 = head;
        Node p2 = head;
        // p2比怕p1快k个节点
        for (int i = 0; i < k - 1; i++)
            p2 = p2.next;
        // 只要p2为null，那么p1就是倒数第k个节点了
        while (p2.next != null) {
            p2 = p2.next;
            p1 = p1.next;
        }
        return p1;
    }

    /**
     * 删除链表重复数据(跟冒泡差不多，等于删除就是了)
     *
     * @param head 头节点
     */
    public void deleteDuplecate(Node head) {
        //临时节点，(从首节点开始-->真正有数据的节点)
        Node temp = head.next;
        //当前节点(首节点)的下一个节点
        Node nextNode = temp.next;
        while (temp.next != null) {
            while (nextNode.next != null) {
                if (nextNode.next.data == nextNode.data) {
                    //将下一个节点删除(当前节点指向下下个节点)
                    nextNode.next = nextNode.next.next;
                } else {
                    //继续下一个
                    nextNode = nextNode.next;
                }
            }
            //下一轮比较
            temp = temp.next;
        }
    }

    /**
     * 查询单链表的中间节点
     */
    public static Node searchMid(Node head) {
        Node p1 = head;
        Node p2 = head;
        // 一个走一步，一个走两步，直到为null，走一步的到达的就是中间节点
        while (p2 != null && p2.next != null && p2.next.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }

    /**
     * 通过递归从尾到头输出单链表
     *
     * @param head 头节点
     */
    public  void printListReversely(Node head) {
        if (head != null) {
            printListReversely(head.next);
            System.out.println(head.data);
        }
    }

    /**
     * 实现链表的反转
     *
     * @param node 链表的头节点
     */
    public Node reverseLinkList(Node node) {

        Node prev ;
        if (node == null || node.next == null) {
            prev = node;
        } else {
            Node tmp = reverseLinkList(node.next);
            node.next.next = node;
            node.next = null;
            prev = tmp;
        }
        return prev;
    }
}
看官可在此打赏