数据结构——链表(java)_java 链表

链表

1. 基本介绍

1.1 定义

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

如图所示：

1.2 链表分类

单向、双向；带头、不带头；循环、非循环
重点：单向不带头非循环、双向不带头非循环（集合类底层）

如图：单项带头非循环链表结构

如图：单向带头循环链表结构

如图：双向不带头循环链表结构

3.不带头非循环单链表CURD

代码展示：

package demo3;

/**
 * @author zq
 * 不带头非循环单链表相关操作
 */
public class MySingleList {

    class Node {
        public int val;//存储数据
        public Node next;//存储下一个节点地址

        public Node(int val) {
            //不知道下一个节点位置，只需要val
            this.val = val;
        }

    }
    public Node head;//代表当前头节点的引用

    //遍历链表
        //创建链表
        public void createLink(){
            Node node1 = new Node(12);
            Node node2 = new Node(45);
            Node node3 = new Node(23);
            Node node4 = new Node(90);

            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            head = node1;
        }
        //遍历链表,利用head遍历链表
        public void display() {
            while (head != null){
                System.out.println(head.val);
                head = head.next;
            }
        }
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key){
            Node cur = head;
            while (cur != null){
                if (cur.val == key){
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
        //头插法
        public void addFirst(int data){
            Node node = new Node(data);
            node.next = head;
            head = node;
        }

        //尾插法,需判断head是否为空
        public void addLast(int data){
            Node node = new Node(data);
            if (head == null) {
                head = node;
                return;
            }
                Node cur = head;
                while (cur.next != null) {
                    cur = cur.next;
                }
                cur.next = node;
            }




        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data){
            checkindex(index);
            if (index == 0){
                addFirst(data);
                return;
            }
            if (index == size()){
                addLast(data);
                return;
            }

            Node cur = findIndexSubOne(index);
            Node node = new Node(data);
            node.next = cur.next;
            cur.next = node;



        }
        /*
        找到index-1处的节点
         */
        private Node findIndexSubOne(int index){
            Node cur = head;
            int count = 0;
            while (count != index -1 ){
                cur = cur.next;
                count++;
            }
            return cur;

        }
        private void checkindex(int index){
            if (index<0||index>size()){
                throw new IndexOutOfException("index位置不合法");
            }
        }

        //删除第一次出现关键字为key的节点
        public void remove(int key){
            if (head.val == key){
                head = head.next;
                return;
            }
          Node cur = searchPrev(key);
            if (cur == null){
                return;
            }
          cur.next = cur.next.next;
        }

        //删除所有值为key的节点
        public void removeAllKey(int key){

            if (head == null){
                return;
            }
            //如果前俩个节点值均为key时。
            // 或者用if放到最后，直接删掉漏掉的节点
            while (head.val==key){
                head = head.next;
            }
            Node prev = head;
            Node cur = head.next;
            while (cur != null){
                if (cur.val == key){
                    prev.next = cur.next;
                    cur = cur.next;
                }else{
                    prev = cur;
                    cur = cur.next;
                }
            }

        }
        //找到关键字key的前一个节点
    private Node searchPrev(int key){
            if (head== null){
                return null;//链表为空时
            }
            Node cur = head;
            while (cur.next!= null){
                if (cur.next.val == key){
                    return cur;
                }
                cur = cur.next;
            }
            return null;//没有需要删除的节点
    }

        //得到单链表的长度
        public int size(){
            int count = 0;
            Node cur = head;
            while (cur != null){
                count++;
                cur = cur.next;
            }
            return count;
        }

        /*
        保证列表中每一个节点都被回收
         */
        public void clear() {
            ListNode cur = head;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        head = null;
        last = null;
        }
}


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

4.不带头非循环双向链表CURD

代码展示：

package demo4;

import demo3.MySingleList;

import java.util.List;

/**
 * @author zq
 * LinkedList的实现
 * 双向链表
 */
public class MyLinkedList {
    static class ListNode{
        ListNode prev;
        ListNode next;
        int val;

        public ListNode(int val) {
            //不知道下一个节点位置，只需要val
            this.val = val;
        }

    }
    public MyLinkedList.ListNode head;//代表当前头节点的引用
    public MyLinkedList.ListNode last;//代表最后节点的引用


    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        if (head == null) {
            head = node;
            last = node;
        }else{
            node.next = head;
            node.prev = null;
            head.prev = node;
            head = node;
        }

    }
    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if (head == null){
            head = node;
            last = node;
        }else{
            last.next = node;
            node.prev = last;
            node.next = null;
            last = node;
        }

    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        ListNode node = new ListNode(data);
        checkindex(index);
        if (index==0){
            addFirst(data);
            return;
        }
        if (index==size()){
            addLast(data);
            return;
        }
        ListNode cur = findIndex(index);
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;



    }
    //判断插入位置是否合法
    private void checkindex(int index){
        if (index<0||index>size()){
            throw new IndexOutOfException("index位置不合法");
        }
    }
    /*
    找到index处的节点
         */
    private ListNode findIndex(int index){
        ListNode cur = head;
        while (index != 0){
            cur = cur.next;
            index--;
        }
        return cur;

    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = head;
        while(cur != null){
            if (cur.val == key){
                return true;
            }
            cur = cur.next;
        }

        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                //删除的是头节点
                if(cur == head) {
                    head=head.next;
                    //如果只有一个节点时处理方式
                    //否则会有空指针异常
                    if (head !=null) {
                        head.prev = null;
                    }
                }else{
                    //中间，尾巴都能用此行代码。
                    cur.prev.next = cur.next;
                    if (cur.next != null){
                        //不是尾巴节点
                        cur.next.prev = cur.prev;
                    }else {
                        last = cur.prev;
                    }
                }
                return;
            }
            cur = cur.next;
        }
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                //删除的是头节点
                if(cur == head) {
                    head=head.next;
                    //如果只有一个节点时处理方式
                    //否则会有空指针异常
                    if (head !=null) {
                        head.prev = null;
                    }
                }else{
                    //中间，尾巴都能用此行代码。
                    cur.prev.next = cur.next;
                    if (cur.next != null){
                        //不是尾巴节点
                        cur.next.prev = cur.prev;
                    }else {
                        last = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }


    }
    //得到单链表的长度
    public int size(){
        int len = 0;
        ListNode cur = head;
        while (cur != null){
            cur = cur.next;
            len++;
        }

        return len;
    }
    public void display(){
        ListNode cur = head;
       while (cur !=null){
           System.out.print(cur.val + " ");
           cur = cur.next;
       }
    }
    public void clear(){
        head = null;
    }
}

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