本文实例为大家分享了Java实现双向链表的具体代码，供大家参考，具体内容如下
双向链表与单链表的对比：
1、单向链表查找只能是一个方向，双向链表可以向前或者向后查找
2、单向链表不能自我删除，需要靠辅助节点**（即需要通过找到要删除的节点的前一个节点，通过该节点进行删除的操作，而双向链表只需找到要删除的节点就行了）**。双向链表可以自我删除
双向链表示意图
分析（代码实现原理）：temp为辅助节点（因为头节点不可动）
1、遍历：方式与单链表一致，但是是双向的，可以向前，也可以向后
2、添加（默认添加到最后面）
（1）先找到链表的最后一个节点
（2）temp.next=newnode
（3）newnode.pre=temp
3、修改：思路与原理与单链表一致
4、删除：
（1）因为是双向链表，可以自我删除该节点
（2）找到要删除的节点，假设这个节点为temp
（3）temp.pre.next=temp.next
（4）temp.next.pre=temp.pre
添加节点（按顺序）：
步骤：
（1）找到要添加节点位置的前一个节点(temp)
（2）node.next=temp.next
（3）temp.next.pre=node
（4）temp.next=node
（5）node.pre=temp
代码实现：
|
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
|
public class DoubleLinkedList { //创建头结点。表示链表的头 private Node Head=new Node(0,"",""); //返回头结点 public Node getHead() { return Head; } //AddNode1:添加节点到单链表的尾部 //思路：当不考虑节点顺序 //1、找到链表的最后一个节点 //2、将最后这个节点的Next指向新节点 public void AddNode1(Node node) { //因为头节点不能动，所以需要一个辅助节点遍历 Node temp=Head; while(true) { //找到链表的最后一个节点 if(temp.next==null) { break; } //否则temp=temp的下一个节点 temp=temp.next; } //循环出来之后，temp是最后一个节点 temp.next=node; node.pre=temp; } //AddNode2:添加节点，按顺序 public void AddNode2(Node node) { //因为头结点不能动，所以需要一个辅助节点遍历，找到添加新节点的位置 Node temp=Head; boolean flag=false; //用于标识链表中是否已经存在新节点的顺序 while(true) { //如果该节点是最后一个节点，则新节点添加到最后一个位置 if(temp.next==null) { break; }else if(temp.next.number>node.number) { //说明找到了添加新节点的位置 break; }else if(temp.next.number==node.number) { //说明新节点的顺序已经存在在链表中 flag=true; } temp=temp.next; } if(flag) { System.out.println("该节点的顺序已经存在，插入失败"); }else { //则说明新节点在链表中不存在，插入新节点 //新节点的下一个节点=辅助节点的下一个节点 node.next=temp.next; if(temp.next!=null) { //如果temp的下一个节点不为空，则temp的下一个节点的前一个节点为新节点 temp.next.pre=node; } //辅助节点的下一个节点=新节点 temp.next=node; //新节点的前一个节点为辅助节点 node.pre=temp; } } //删除节点 public void remove(Node node) { if(Head.next==null) { System.out.println("链表为空！"); return; } //创建辅助节点 Node temp=Head.next; boolean flag=false; //标识是否找到了要删除的节点 while(true) { if(temp==null) { //遍历完链表了 break; }else if(temp.number==node.number) { //找到要删除的节点了 flag=true; break; } temp=temp.next; } if(flag) { //链表中存在要删除的节点 temp.pre.next=temp.next; //令temp的前一个节点的下一个节点为temp的后一个节点 if(temp.next!=null) { //如果temp不为最后一个节点的话 temp.next.pre=temp.pre; //令temp的下一个节点的前一个节点为temp的前一个节点 } }else { System.out.printf("不存在编号为%d的节点",node.number); } } //修改节点，按照节点的Number来修改 public void update(Node newNode) { if(Head.next==null) { System.out.println("链表为空！"); return; } //创建辅助节点，对链表遍历，知道找到等于修改节点的number的时候 Node temp=Head.next; boolean flag=false; //用来标识是否找到了修改节点的Number while(true) { if(temp==null) { //则已经遍历完链表 break; } if(temp.number==newNode.number) { flag=true; break; } temp=temp.next; } if(flag) { temp.name=newNode.name; temp.nickName=newNode.nickName; }else { System.out.printf("没有找到编号为%d的节点",newNode.number); } } //展示链表 public void show() { if(Head.next==null) { System.out.println("链表为空！"); return; } //因为头节点不能动，所以通过辅助节点遍历链表 Node temp=Head.next; while(true) { //判断是不是最后一个节点 if(temp.next==null) { System.out.println(temp); break; } System.out.println(temp); //temp指向下一个节点 temp=temp.next; } }}//创建节点class Node{ public int number; public String name; public String nickName; public Node next; //指向下一个节点 public Node pre;//指向前一个节点 //构造器 public Node(int number,String name,String nickName) { this.number=number; this.name=name; this.nickName=nickName; } @Override public String toString() { return "Node [number=" + number + ", name=" + name + ", nickName=" + nickName + "]"; }} |
测试代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public static void main(String[] args) { // TODO 自动生成的方法存根 Node node1=new Node(1,"宋江","及时雨"); Node node2=new Node(2,"卢俊义","玉麒麟"); Node node3=new Node(3,"吴用","智多星"); Node node4=new Node(4,"林冲","豹子头"); Node node5=new Node(4,"linchong","豹子头"); //创建一个链表 DoubleLinkedList linkedList=new DoubleLinkedList(); linkedList.AddNode2(node1); linkedList.AddNode2(node3); linkedList.AddNode2(node4); linkedList.AddNode2(node2); linkedList.show(); System.out.println("------------"); linkedList.remove(node4); linkedList.show(); } |
结果：
Node [number=1, name=宋江, nickName=及时雨]
Node [number=2, name=卢俊义, nickName=玉麒麟]
Node [number=3, name=吴用, nickName=智多星]
Node [number=4, name=林冲, nickName=豹子头]
————————————————————————
Node [number=1, name=宋江, nickName=及时雨]
Node [number=2, name=卢俊义, nickName=玉麒麟]
Node [number=3, name=吴用, nickName=智多星]
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/weixin_43589025/article/details/105884616
