本文实例为大家分享了Java实现双向链表的具体代码，供大家参考，具体内容如下
1、双向链表
1.1 双向链表的每个节点组成包含节点数据，上一个节点（pre），下一个节点（next）
1.2 双向链表节点结构
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Node { //节点数据data int data; Node pre; Node next;
public Node( int data) { this .data = data; } public Node() { super (); }
} |
2、双向链表的增删改查（crud）
2.1 双向链表的增删改查
|
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 |
public class DoubleLinkedList { private Node first; private Node current;
private static class Node {
int data; Node pre; Node next;
public Node( int data) { super (); this .data = data; }
public Node() { super (); }
}
public DoubleLinkedList() { super (); }
/** * 双向链表增加 */ public void add( int val) { // 如果是头结点 if (first == null ) { Node node = new Node(val); first = node; first.pre = null ; first.next = null ; current = first; } else { Node node = new Node(val); current.next = node; node.pre = current; current = node; } }
/** * 双向链表的删除 删除所有值为val的元素 */ public void del( int val) { if (first == null ) { System.out.println( "双向链表为空，无法进行删除操作！" ); } else {
Node node = first; while ( true ) { // 首节点的删除可能 if (node.data == val) { //如果只有一个节点 if (node.next== null ) { node= null ; first= null ; System.out.println( "删除所有的" +val+ "成功" ); return ; } else { node = node.next; node.pre.next= null ; node.pre= null ; first=node; //删除后重新循环判断首节点是否值相等 continue ; }
} else {
while (node.next != null ) { if (node.data == val) { node.pre.next = node.next; node.next.pre = node.pre; Node tempNode = node.pre; node.pre= null ; node.next= null ; node = tempNode; } node = node.next; } // 末节点删除可能 if (node.data == val) { node.pre.next= null ; node.pre= null ;
} System.out.println( "删除所有的" +val+ "成功" ); //末节点判断完成后，结束循环 return ; } } }
} /** * 遍历双向链表操作 */ public void traverse() { if (first== null ) { System.out.println( "双向链表为空" ); } else { Node node = first; //循环遍历到倒数第二个节点截止 while (node.next!= null ) { System.out.print(node.data+ " " ); node=node.next; } //遍历最后一个节点 System.out.print(node.data); } } /** * 双向链表插入操作,在所有值为value的后面插入一个数insert */ public void insert( int value, int insert) {
if (first== null ) { System.out.println( "双向链表为空，无法插入" ); } else { Node node = first; //循环遍历到倒数第二个节点截止 while (node.next!= null ) { if (node.data==value) { Node insertNode = new Node(insert); node.next.pre = insertNode; insertNode.next = node.next; node.next = insertNode; insertNode.pre = node; } node=node.next; } //最后一个节点后插入 if (node.data == value) { Node insertNode = new Node(insert); node.next = insertNode; insertNode.pre = node; } System.out.println(); System.out.println( "插入操作完成" );
} } /** * 双向链表修改数据,将所有值为val的修改为revised */ public void revise( int val, int revised) { if (first== null ) { System.out.println( "双向链表为空，无法修改" ); } else { Node node = first; while (node.next!= null ) { if (node.data == val) { node.data = revised; } node=node.next; } if (node.data == val) {} node.data = revised; } System.out.println( "修改操作完成" ); } /** * 查找双向链表中是否包含val值 * @param val */ public void contain( int val) { if (first== null ) { System.out.println( "链表为空，无法查找" ); } else { Node node = first; while (node!= null ) { if (node.data==val) { System.out.println( "该链表中包含" +val+ "的值" ); return ; } else { node=node.next; } } System.out.println( "该链表不包含" +val); } }
} |
2.2 测试类（main入口函数）
|
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 |
public class Main { public static void main(String[] args) { DoubleLinkedList list = new DoubleLinkedList();
list.add( 1 ); list.add( 1 ); list.add( 2 ); list.insert( 1 , 3 ); list.add( 2 ); list.add( 3 ); list.traverse(); System.out.println(); list.del( 1 );
list.traverse(); list.add( 4 ); System.out.println(); list.traverse(); System.out.println(); list.contain( 4 );
list.contain( 3 ); list.contain( 0 );
} } |
3、一些缺点待修改
1）、循环结束是到倒数第二个节点截止的，要考虑多种不同的情况，头节点删除，尾结点删除等，导致删除函数复杂了很多
2）、在contain函数中有修改到循环到最后一个节点
3）、后续对删除函数修改有空再操作（待完成）
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。
原文链接：https://blog.csdn.net/qq_43498002/article/details/118252022