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.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); } }
1)、循环结束是到倒数第二个节点截止的,要考虑多种不同的情况,头节点删除,尾结点删除等,导致删除函数复杂了很多
2)、在contain函数中有修改到循环到最后一个节点
3)、后续对删除函数修改有空再操作(待完成)
以上就是Java如何实现双向链表的详细内容,更多请关注php中文网其它相关文章!