数据结构之双向链表_node.setpre

作者：2023面试高手 | 2024-04-18 05:14:52

踩

node.setpre

前面已经介绍过了单链表，这篇文章介绍一下双向链表。双向链表的节点比单链表的节点多一个pre域，也就是存放当前节点的前一个节点地址的地方。

单链表里有许多操作是要找到待操作节点的前一个节点的，而双向链表则不需要，因为双向链表可以得到当前节点的前一个和后一个节点信息，可以完成相应的操作。
双向链表节点：
在这里插入图片描述
节点类：

class Node{
	//pre表示前一个节点，next表示后一个节点
	//no表示序号，其他为一些数据
	private Node pre;
	private Node next;
	private int no;
	private String name;
    private String nickname;
    public Node(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }
	@Override
	public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
	//get set 方法省略
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

双向链表类（带头节点）：
双向链表的基本操作后面追加

class TwoWayLinkedList{
	private Node head = new Node(0,"","");
	//无参构造函数
	public TwoWayLinkedList(){
	}
	public void setHead(Node node){
		this.head = node;
	}
	public Node getHead(){
		return this.head;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

接下来就是给双向链表类添加一些基本方法了，插入这里提供按序号插入法，其他插入类似，然后就是删除，修改，遍历方法了。

添加节点方法（按序号插入），该方法在双向链表类内部
思路：
插入节点的插入位置在cur指针的前面时
1）插入时先设置待插入节点的node的pre域，即把cur的pre域设置为node的pre域
2）再把cur的pre域对应节点的next域设为node
3）然后将cur的的pre域设为node，node的next域设为cur 即：
node.setPre(cur.getPre());
node.setNext(cur);
cur.getPre().setNext(node);
cur.setPre(node);

插入节点的插入位置在cur指针后面时又分为：在链表尾部插入和在链表头部插入（即链表为空时插入第一个节点）
特别注意：插入第一个节点时和在链表尾部插入时，cur很容易出现空指针异常，所以要分三种插入的情况

参数：节点（Node）
返回值：无

public void add(Node node){
	//先判断链表是否为空，为空说明这是插入的第一个节点
	//第一个节点插入因为head的next域为空
	//head.getNext().getPre()会报空指针异常错误
	//所以给第一个节点设置pre域时要直接指向head
	if(head.getNext()==null){
		node.setNext(head.getNext());
		node.setPre(head);
		head.setNext(node);
		return;
	}
	//代码走到这里说明双向链表至少有一个节点
	//创建一个cur指针，指向链表的第一个节点
	Node cur = head.getNext();
	//如果cur指向最后一个节点还没有比待插入节点序号大的
	//就插入到链表最后
	while(true){
		//如果cur当前指向的节点序号大于待插入节点的序号
		//说明待插入节点应该插在cur当前指向节点的前一个位置
		//插入之后就退出循环，插入方法也就执行完了
		if(cur.getNo()>node.getNo()){
			node.setPre(cur.getPre());
			node.setNext(cur);
			cur.getPre().setNext(node);
			cur.setPre(node);
			break;
		}else if(cur.getNo()==node.getNo()){
			//编号存在就不插入，退出循环
			System.out.printf("编号%d已存在\n",node.getNo());
			break;
		}else if(cur.getNext()==null){
			//判断当前cur指向的是不是最后一个节点
			//如果是，就插入到链表最后
			//进入这个if分支
			//说明待插入节点序号比前面节点序号都大
			//而且待插入节点序号不存在于链表中
			node.setPre(cur);
			cur.setNext(node);
			//节点初始化时，其pre与next默认指向null
			//所以不需要让node的next域再设置为null
			//或者设为cur的next域
			break;
		}
		//如果上面的if分支一个都没进入
		//说明cur指向的节点不满足，让cur指向下一个节点
		cur = cur.getNext();
	}
}
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

插入方法写好之后就可以写遍历方法，将双向链表进行打印输出，该方法还是在双向链表类内部
参数：无
返回值：无

public void print(){
	//先判断链表是否为空
	if(head.getNext()==null){
		System.out.println("双向链表为空");
		return;
	}
	//定义一个cur指针指向链表的头节点，然后遍历链表
	Node cur = head;
	//开始遍历
	while(true){
		//cur指向链表最后一个节点就退出循环
		if(cur.getNext()==null){
			break;
		}
		//因为cur初始化是head
		//所以打印cur指向的下一个节点
		//打印时需要打印当前节点和前一个节点
		//避免插入时节点pre域出现问题
		System.out.println("now:"+cur.getNext()+
		"pre:"+cur.getNext().getPre());
		//然后让cur指向下一个节点
		cur = cur.getNext();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

链表删除思路：
1）先遍历通过cur找到待删除节点
此时cur指向的就是待删除节点，让待删除节点的前一个节点的next域直接跨过待删除节点指向待删除节点的next域。
2）让待删除节点的下一个节点的pre域直接跨过待删除节点指向待删除节点的pre域

cur.getPre().setNext(cur.getNext());
cur.getNext().setPre(cur.getPre());
特别注意：如果待删除节点是链表最后一个，那么cur.getNext()就为空，2）的操作就会出现空指针异常，这里需要判断一下

参数：待删除节点的序号（int）
返回值：无
该方法仍然在双向链表内部

public void remove(int no){
	//先判断链表是否为空
	if(head.getNext()==null){
		System.out.println("链表为空");
		return;
	}
	//创建一个cur指针来遍历链表，初始化指向链表第一个节点
	Node cur = head.getNext();
	while(true){
		if(cur.getNo()==no){//找到待删除节点
			cur.getPre().setNext(cur.getNext());
			if(cur.getNext()!=null){
				//如果待删除节点为链表最后一个节点
				//不执行下面语句
				cur.getNext().setPre(cur.getPre());
			}
			break;
		}else if(cur.getNext()==null){
			//当前cur指向的是链表最后一个节点
			//说明没有传来的序号匹配不到待删除节点
			System.out.println("没有该编号:"+no+"节点");
			break;
		}
		//未执行上面代码，让cur后移
		cur = cur.getNext();
	}
}
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

链表修改节点信息思路：

修改节点信息与删除节点类似，遍历找到待更新节点，然后替换信息，未找到就在控制台输出提醒，不可修改节点序号

参数：一个节点（node）
返回值：无

public void update(Node node){
	//先判断链表是否为空
	if(head.getNext()==null){
		System.out.println("链表为空");
		return;
	}
	//创建一个cur指针来遍历链表，初始化指向链表第一个节点
	Node cur = head.getNext();
	while(true){
		if(cur.getNo()==node.getNo()){//找到待修改节点
			//修改节点信息
			cur.setName(node.getName());
			cur.setNickname(node.getNickname());
			break;
		}else if(cur.getNext()==null){
			//当前cur指向的是链表最后一个节点
			//说明传来节点的序号匹配不到
			System.out.println("没有该编号:"
			+node.getNo()+"节点");
			break;
		}
		//未执行上面代码，让cur后移
		cur = cur.getNext();
	}
}
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

之前单链表的操作，如：单链表长度，获取倒数第k个节点，单链表反转，单链表反向输出，合并两个有序单链表为一个单链表且仍然有序。
双向链表的操作，下面直接给出代码，思路是和单链表的类似，就是设置节点pre域麻烦一点。

双向链表全部代码如下：

package com.sixteen.linkedlist;

public class TwoWayLinkedListDemo {
    public static void main(String[] args) {
        TwoWayLinkedList twoWayLinkedList = new TwoWayLinkedList();
        twoWayLinkedList.add(new Node(1,"宋江","及时雨"));
        twoWayLinkedList.add(new Node(3,"吴用","智多星"));
        twoWayLinkedList.add(new Node(2,"卢俊义","玉麒麟"));
        twoWayLinkedList.add(new Node(4,"林冲","豹子头"));
        System.out.println("原双向链表-----");
        twoWayLinkedList.print();
        /*System.out.println(getSize(twoWayLinkedList.getHead()));
        twoWayLinkedList.update(new Node(2,"卢俊义222","玉麒麟222"));
        System.out.println("修改后的双向链表-----");
        twoWayLinkedList.print();*/
        /*System.out.println(getTheLastIndexNode(twoWayLinkedList.getHead(), 1));
        System.out.println(getTheLastIndexNode(twoWayLinkedList.getHead(), 4));
        System.out.println(getTheLastIndexNode(twoWayLinkedList.getHead(), 2));
        System.out.println(getTheLastIndexNode(twoWayLinkedList.getHead(), 6));*/
        /*twoWayLinkedList.remove(3);
        System.out.println("-----");
        twoWayLinkedList.print();*/
        /*//reversePrint(twoWayLinkedList.getHead());
        reverse(twoWayLinkedList.getHead());
        System.out.println("反转后的双向链表-----");
        twoWayLinkedList.print();*/
        /*TwoWayLinkedList twoWayLinkedList1 = new TwoWayLinkedList();
        twoWayLinkedList1.add(new Node(1,"宋江","及时雨"));
        twoWayLinkedList1.add(new Node(3,"吴用","智多星"));
        twoWayLinkedList1.add(new Node(5,"卢俊义","玉麒麟"));
        twoWayLinkedList1.add(new Node(7,"林冲","豹子头"));
        TwoWayLinkedList twoWayLinkedList2 = new TwoWayLinkedList();
        twoWayLinkedList2.add(new Node(2,"宋江2","及时雨2"));
        twoWayLinkedList2.add(new Node(4,"吴用4","智多星4"));
        twoWayLinkedList2.add(new Node(6,"卢俊义6","玉麒麟6"));
        twoWayLinkedList2.add(new Node(8,"林冲8","豹子头8"));
        TwoWayLinkedList twoWayLinkedList = mergeTwoTwoWayLinkedList(twoWayLinkedList1, twoWayLinkedList2);
        twoWayLinkedList.print();*/
    }

    public static Node getTheLastIndexNode(Node head,int index){
        if (head.getNext()==null){
            return null;
        }
        int size = getSize(head);
        if (index<0 || index>size){
            return null;
        }
        Node temp = head.getNext();
        for (int i = 0; i < size-index; i++) {
            temp = temp.getNext();
        }
        return temp;
    }

    public static int getSize(Node head){
        if (head.getNext()==null){
            return 0;
        }
        int count = 0;
        Node temp = head.getNext();
        while (temp!=null){
            count++;
            temp = temp.getNext();
        }
        return count;
    }

    public static TwoWayLinkedList mergeTwoTwoWayLinkedList(TwoWayLinkedList twoWayLinkedList1,
                                                            TwoWayLinkedList twoWayLinkedList2){
        Node head1 = twoWayLinkedList1.getHead();
        Node head2 = twoWayLinkedList2.getHead();
        if (head1.getNext()==null || head2.getNext()==null){
            return head1.getNext()==null ? twoWayLinkedList2:twoWayLinkedList1;
        }
        Node cur = head1.getNext();
        Node node;
        while (cur!=null){
            node = cur;
            cur = cur.getNext();
            twoWayLinkedList2.add(node);
        }
        return twoWayLinkedList2;
    }

    public static void reverse(Node head){
        //如果链表为空或链表只有一个元素，不做任何操作
        if (head.getNext()==null){
            System.out.println("链表为空");
            return;
        }
        if (head.getNext().getNext()==null){
            return;
        }
        Node temp = head.getNext();
        Node reverseNode = new Node(0,"","");
        Node node;
        while (temp!=null){
            node = temp;
            temp = temp.getNext();
            if (reverseNode.getNext()==null){
                node.setNext(reverseNode.getNext());
                node.setPre(reverseNode);
                reverseNode.setNext(node);
            }else {
                node.setNext(reverseNode.getNext());
                node.setPre(reverseNode);
                reverseNode.getNext().setPre(node);
                reverseNode.setNext(node);
            }
        }
        head.setNext(reverseNode.getNext());
    }

    public static void reversePrint(Node head){
        //链表为空或者链表只有一个节点时，直接输出
        if (head.getNext()==null){
            System.out.println("链表为空");
            return;
        }
        if (head.getNext().getNext()==null){
            System.out.println(head.getNext());
            return;
        }
        Node temp = head.getNext();
        //while循环结束之后temp定位到最后一个节点，然后再反向遍历链表
        while (temp.getNext()!=null){
            temp = temp.getNext();
        }
        while (temp.getPre()!=null){
            System.out.println(temp);
            temp = temp.getPre();
        }
    }
}
class TwoWayLinkedList{
    private Node head = new Node(0,"","");

    public Node getHead() {
        return head;
    }

    public void setHead(Node head) {
        this.head = head;
    }

    public void add(Node node){
        if (head.getNext()==null){
            node.setPre(head);
            node.setNext(head.getNext());
            head.setNext(node);
            return;
        }
        Node cur = head.getNext();
        while (true){
            if (cur.getNo()>node.getNo()){
                node.setPre(cur.getPre());
                node.setNext(cur);
                cur.getPre().setNext(node);
                cur.setPre(node);
                break;
            }else if (cur.getNo()==node.getNo()){
                System.out.printf("编号%d已存在\n",node.getNo());
                break;
            }else if (cur.getNext()==null){
                node.setPre(cur);
                cur.setNext(node);
                break;
            }
            cur = cur.getNext();
        }
    }

    public void remove(int no){
        if (head.getNext()==null){
            System.out.println("链表为空");
            return;
        }
        Node cur = head.getNext();
        while (true){
            if (cur.getNo()==no){
                cur.getPre().setNext(cur.getNext());
                if (cur.getNext()!=null){//如果当前cur指向的是链表最后一个节点，就不执行下面的操作
                    cur.getNext().setPre(cur.getPre());
                }
                if (cur.getNext()==null){//找到相应节点且这个节点是最后一个节点
                    cur.getPre().setNext(null);
                }else {
                    cur.getPre().setNext(cur.getNext());
                    cur.getNext().setPre(cur.getPre());
                }
                break;
            }else if (cur.getNext()==null){
                System.out.println("没有编号"+no+"的节点");
                break;
            }
            cur = cur.getNext();
        }
    }
    public void update(Node node){
        if (head.getNext()==null){
            System.out.println("链表为空");
            return;
        }
        Node cur = head.getNext();
        while (true){
            if (cur.getNo()==node.getNo()){
                cur.setName(node.getName());
                cur.setNickname(node.getNickname());
                break;
            }else if (cur.getNext()==null){
                System.out.println("没有编号"+node.getNo()+"节点");
                break;
            }
            cur = cur.getNext();
        }
    }

    public void print(){
        if (head.getNext()==null){
            System.out.println("链表为空");
            return;
        }
        Node cur = head;
        while (true){
            if (cur.getNext()==null){
                break;
            }
            System.out.println("now:"+cur.getNext()+
                    "pre:"+cur.getNext().getPre());
            cur = cur.getNext();
        }
    }
}

class Node{
    private Node pre;
    private Node next;
    private int no;
    private String name;
    private String nickname;
    public Node(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }

    public Node getPre() {
        return pre;
    }

    public void setPre(Node pre) {
        this.pre = pre;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getNickname() {
        return nickname;
    }

    public void setNickname(String nickname) {
        this.nickname = nickname;
    }
}
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
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/444181