数据结构06——双向链表（增删改查）

单链表的缺点

双向链表的思路分析

源代码实现增删改查

package list; import java.awt.font.TextMeasurer; import java.beans.beancontext.BeanContext; import java.util.Stack; /** * @program: DataStructures * description: * @author: Mr.Zhang * @create: 2020-28-06_20:28 **/ public class DoubleListDemo { public static void main(String[] args) { // 测试 // 1. 首先添加四个节点,普通方法 DoubleList doubleList = new DoubleList(); // doubleList.addElementAtLast(new HeroLink2(1, "宋江", "及时雨")); // doubleList.addElementAtLast(new HeroLink2(2, "卢俊义", "玉麒麟")); // doubleList.addElementAtLast(new HeroLink2(4, "吴用", "智多星")); // doubleList.addElementAtLast(new HeroLink2(3, "林冲", "豹子头")); // 测试按id号顺序添加 doubleList.addEleById(new HeroLink2(1, "宋江", "及时雨")); doubleList.addEleById(new HeroLink2(2, "卢俊义", "玉麒麟")); doubleList.addEleById(new HeroLink2(4, "吴用", "智多星")); doubleList.addEleById(new HeroLink2(3, "林冲", "豹子头")); // 2. 测试打印链表全部数据 doubleList.showAllEle(doubleList.getHead()); // 3. 测试删除数据 // doubleList.delById(5); // System.out.println("删除后的数据："); // doubleList.showAllEle(doubleList.getHead()); // 4. 测试修改数据 // doubleList.updateById(new HeroLink2(2, "卢俊义", "卢俊义(修改后)")); // System.out.println("修改后的双链表："); // doubleList.showAllEle(doubleList.getHead()); } } // 单链表类 class DoubleList { // 头节点 private HeroLink2 head = new HeroLink2(0, "", ""); public HeroLink2 getHead() { return head; } // 判断双链表是否为空 // public boolean judgeNull(HeroLink2 head) { // return head.next == null; // } // 显示双链表全部有效元素 public void showAllEle(HeroLink2 head) { // 1. 判断链表是否为空 if (head.next == null) { System.out.println("链表为空，显示全部为无"); return; } // 2. 链表不为空，遍历打印 HeroLink2 temp = head.next; while (temp != null) { System.out.println(temp); temp = temp.next; } } // 添加元素，尾插 public void addElementAtLast(HeroLink2 heroLink2) { // 1. 判断此双链表是否为空 if (head.next == null) { // 直接插入 head.next = heroLink2; heroLink2.pre = head; return; } // 2. 遍历，直到找到最后一个节点 HeroLink2 temp = head.next; while (temp.next != null) temp = temp.next; // 3. 找到最后一个节点进行插入 temp.next = heroLink2; heroLink2.pre = temp; } // 添加元素，顺序添加 public void addEleById(HeroLink2 heroLink2) { // 首先判断单链表是否为空，空则直接添加 if (head.next == null) { head.next = heroLink2; heroLink2.pre = head; return; } HeroLink2 temp = head.next; while (true) { // 查到最后一个元素，包括链表为空的情况, 直接插入 if (temp.next == null) { if (heroLink2.id > temp.id) { temp.next = heroLink2; heroLink2.pre = temp; } if (heroLink2.id < temp.id) { temp.pre.next = heroLink2; temp.pre = heroLink2; heroLink2.pre = temp.pre; heroLink2.next = temp; } if (heroLink2.id == temp.id) System.out.println("此元素已经存在！！，不能添加。"); break; } // 此时至少有一个元素了 if (heroLink2.id < temp.id) { temp.pre.next = heroLink2; temp.pre = heroLink2; heroLink2.pre = temp.pre; heroLink2.next = temp; break; } if (heroLink2.id == temp.id) System.out.println("此元素已经存在！！，不能添加。"); temp = temp.next; } } // 删除指定id号的元素 public void delById(int id) { // 1. 判断链表是否为空，为空则不能删除 if (head.next == null) { System.out.println("此链表为空，不能进行删除！！！"); return; } // 2. 遍历查询，进行删除, 两个及以上的元素 HeroLink2 temp = head.next; while (true) { // 判断是否到达了最后一个元素，直接删除 if (temp.next == null) { if (temp.id == id) { // 进行删除 temp.pre.next = null; // = temp.next也可以 }else System.out.println("没有找到要删除的元素"); break; } // 中间元素的删除 if (temp.id == id) { // 找到了元素，进行删除 temp.next.pre = temp.pre; temp.pre.next = temp.next; break; }else System.out.println("没有找到要删除的元素"); temp = temp.next; } } // 修改指定id号的元素 public void updateById(HeroLink2 newHeroLink) { // 1. 判断链表是否为空，为空则不能删除 if (head.next == null) { System.out.println("此链表为空，不能进行修改！！！"); return; } // 2. 遍历查询，进行删除, 两个及以上的元素 HeroLink2 temp = head.next; boolean flag = false; // 是否查找到元素的标志 while (temp != null) { if (temp.id == newHeroLink.id) { // 找到了 flag = true; break; } temp = temp.next; } if (flag) { // 找到了需要修改的元素, 只修改昵称 temp.nickName = newHeroLink.nickName; }else System.out.println("没有查找到需要修改的元素！！！"); } } // 英雄类，也就是节点类 class HeroLink2 { public int id; public String name; public String nickName; public HeroLink2 next; public HeroLink2 pre; // 构造函数，初始化 public HeroLink2(int id, String name, String nickName) { this.id = id; this.name = name; this.nickName = nickName; } // 打印 @Override public String toString() { return "HeroLink2{" + "id=" + id + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}'; } }