赞
踩
1、单向链表查找的方向只能是一个方向,而双向链表可以向前或向后查找
2、单向链表不能自我删除,需要靠辅助节点。而双向链表则可以自我删除,所以单链表删除节点时总是要先找到temp节点,temp节点是待删除节点的前一个节点(认真体会)
1、先找到双向链表的最后那个节点,如temp节点
2、修改节点的前后链接
temp.next = newNode;
newNode.pre = temp;
1、双向链表可以自我删除
2、找到要删除的那个节点,如temp节点
3、修改节点的前后链接
temp.pre.next = temp.next;
temp.next.pre = temp.pre;
思路与修改单链表相同
与单链表的遍历方法一样,区别是可以向前或向后查找。
/** * 添加一个节点到双向链表的最后 * (请注意:是添加到链表的最后) */ public void addToEnd(HisNode hisNode) { // 因为head节点不能动,因此需要一个辅助变量temp HisNode temp = head; // 遍历链表,找到最后 while (true) { // 找到链表的最后 if (temp.next == null) { break; } // 如果没有找到最后,将temp后移 temp = temp.next; } // 当退出while循环时,temp就指向了链表的最后 temp.next = hisNode; hisNode.pre = temp; }
测试添加节点功能:
// 创建节点
HisNode node1 = new HisNode(1, "宋江", "及时雨");
HisNode node2 = new HisNode(2, "卢俊义", "玉麒麟");
HisNode node3 = new HisNode(3, "吴用", "智多星");
HisNode node4 = new HisNode(4, "林冲", "豹子头");
// 创建一个双向链表并添加节点到末尾
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.addToEnd(node1);
doubleLinkedList.addToEnd(node2);
doubleLinkedList.addToEnd(node3);
doubleLinkedList.addToEnd(node4);
// 遍历双链表
System.out.println("遍历双向链表:");
doubleLinkedList.list();
添加效果:
/** * 从双向链表中删除一个节点 * 1、对于双向链表,我们可以直接找到这个节点 * 2、自我删除即可 */ public void del(int no) { // 判断当前链表是否为空 if (head.next == null) { System.out.println("链表为空,无法删除"); return; } // 辅助变量 HisNode temp = head.next; // 是否找到待删除节点的标志 boolean flag = false; while (true) { // 已经到链表的最后 if (temp == null) { break; } // 找到待删除节点的前一个节点 if (temp.no == no) { flag = true; break; } // temp后移,遍历 temp = temp.next; } // 判断是否找到待删除节点 if (flag) { // temp.next = temp.next.next; //单向链表的删除 temp.pre.next = temp.next; // 如果是最后一个节点,注意空指针 if (temp.next != null) { temp.next.pre = temp.pre; } } else { System.out.printf("要删除的 %d 节点不存在\n", no); } }
测试删除节点:
// 删除
doubleLinkedList.del(3);
System.out.println("删除节点后的双向链表是:");
doubleLinkedList.list();
删除效果:
/** * 修改一个节点的内容(与单向链表的修改方法一样) */ public void update(HisNode newHisNode) { // 判断是否为空 if (head.next == null) { System.out.println("链表为空"); return; } // 定义一个辅助变量 HisNode temp = head.next; // 表示是否找到该节点 boolean flag = false; while (true) { // 已遍历完链表 if (temp == null) { break; } // 找到需要修改的节点,根据no编号修改 if (temp.no == newHisNode.no) { // 找到了 flag = true; break; } temp = temp.next; } // 根据flag判断是否找到要修改的节点 if (flag) { temp.name = newHisNode.name; temp.nickName = newHisNode.nickName; } else { System.out.printf("没有找到编号 %d 的节点,不能修改\n", newHisNode.no); } }
测试修改节点:
// 修改
HisNode newHisNode = new HisNode(4, "公孙胜", "入云龙");
doubleLinkedList.update(newHisNode);
System.out.println("修改节点后的双向链表是:");
doubleLinkedList.list();
修改效果:
/** * 遍历双向链表 */ public void list() { // 判断是否为空 if (head.next == null) { System.out.println("链表为空"); return; } // 因为头节点不能动,因此需要一个辅助变量来遍历 HisNode temp = head.next; while (true) { // 判断是否到链表最后 if (temp == null) { break; } // 输出节点信息 System.out.println(temp); // 将temp后移,此处一定小心 temp = temp.next; } }
之前的示例已展示过遍历效果了哦。
任意定义一个节点类,如HisNode
package com.company.linkedlist.doubles; /** * 每个HisNode对象就是一个节点 */ public class HisNode { public int no; public String name; public String nickName; /** * 指向前一个节点, 默认为null */ public HisNode pre; /** * 指向下一个节点,默认为null */ public HisNode next; public HisNode(int no, String name, String nickName) { this.no = no; this.name = name; this.nickName = nickName; } /** * 为了显示方法,我们重新toString */ @Override public String toString() { return "HisNode{" + "no=" + no + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}'; } }
package com.company.linkedlist.doubles; /** * 创建一个双向链表的类 */ public class DoubleLinkedList { /** * 先初始化一个头结点,头结点不要动,不存放具体的数据 */ private HisNode head = new HisNode(0, "", ""); /** * 返回头节点 */ public HisNode getHead() { return head; } /** * 添加一个节点到双向链表的最后 * (请注意:是添加到链表的最后) */ public void addToEnd(HisNode hisNode) { // 因为head节点不能动,因此需要一个辅助变量temp HisNode temp = head; // 遍历链表,找到最后 while (true) { // 找到链表的最后 if (temp.next == null) { break; } // 如果没有找到最后,将temp后移 temp = temp.next; } // 当退出while循环时,temp就指向了链表的最后 temp.next = hisNode; hisNode.pre = temp; } /** * 从双向链表中删除一个节点 * 1、对于双向链表,我们可以直接找到这个节点 * 2、自我删除即可 */ public void del(int no) { // 判断当前链表是否为空 if (head.next == null) { System.out.println("链表为空,无法删除"); return; } // 辅助变量 HisNode temp = head.next; // 是否找到待删除节点的标志 boolean flag = false; while (true) { // 已经到链表的最后 if (temp == null) { break; } // 找到待删除节点的前一个节点 if (temp.no == no) { flag = true; break; } // temp后移,遍历 temp = temp.next; } // 判断是否找到待删除节点 if (flag) { // temp.next = temp.next.next; //单向链表的删除 temp.pre.next = temp.next; // 如果是最后一个节点,注意空指针 if (temp.next != null) { temp.next.pre = temp.pre; } } else { System.out.printf("要删除的 %d 节点不存在\n", no); } } /** * 修改一个节点的内容(与单向链表的修改方法一样) */ public void update(HisNode newHisNode) { // 判断是否为空 if (head.next == null) { System.out.println("链表为空"); return; } // 定义一个辅助变量 HisNode temp = head.next; // 表示是否找到该节点 boolean flag = false; while (true) { // 已遍历完链表 if (temp == null) { break; } // 找到需要修改的节点,根据no编号修改 if (temp.no == newHisNode.no) { // 找到了 flag = true; break; } temp = temp.next; } // 根据flag判断是否找到要修改的节点 if (flag) { temp.name = newHisNode.name; temp.nickName = newHisNode.nickName; } else { System.out.printf("没有找到编号 %d 的节点,不能修改\n", newHisNode.no); } } /** * 遍历双向链表 */ public void list() { // 判断是否为空 if (head.next == null) { System.out.println("链表为空"); return; } // 因为头节点不能动,因此需要一个辅助变量来遍历 HisNode temp = head.next; while (true) { // 判断是否到链表最后 if (temp == null) { break; } // 输出节点信息 System.out.println(temp); // 将temp后移,此处一定小心 temp = temp.next; } } }
package com.company.linkedlist.doubles; public class DoubleLinkedListDemo { public static void main(String[] args) { // 创建节点 HisNode node1 = new HisNode(1, "宋江", "及时雨"); HisNode node2 = new HisNode(2, "卢俊义", "玉麒麟"); HisNode node3 = new HisNode(3, "吴用", "智多星"); HisNode node4 = new HisNode(4, "林冲", "豹子头"); // 创建一个双向链表并添加节点到末尾 DoubleLinkedList doubleLinkedList = new DoubleLinkedList(); doubleLinkedList.addToEnd(node1); doubleLinkedList.addToEnd(node2); doubleLinkedList.addToEnd(node3); doubleLinkedList.addToEnd(node4); // 遍历双链表 System.out.println("遍历双向链表:"); doubleLinkedList.list(); // 删除 doubleLinkedList.del(3); System.out.println("删除节点后的双向链表是:"); doubleLinkedList.list(); // 修改 HisNode newHisNode = new HisNode(4, "公孙胜", "入云龙"); doubleLinkedList.update(newHisNode); System.out.println("修改节点后的双向链表是:"); doubleLinkedList.list(); } }
微信公众号:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。