Java实现双向链表（Java实现双向链表增删改查）

本文实例为大家分享了java实现双向链表的具体代码，供大家参考，具体内容如下

1、双向链表

1.1 双向链表的每个节点组成包含节点数据，上一个节点（pre），下一个节点（next）

1.2 双向链表节点结构

class Node {

//节点数据data

int data;

Node pre;

Node next;

public Node(int data) {

this.data = data;

}

public Node() {

super();

}

}

2、双向链表的增删改查（crud）

2.1 双向链表的增删改查

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入口函数）

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）、后续对删除函数修改有空再操作（待完成）

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。