双向链表应用实例
双向链表的操作分析和实现
使用带 head 头的双向链表实现
管理单向链表的缺点分析:
- 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
- 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除
时节点，总是找到 temp,temp 是待删除节点的前一个节点 - 分析了双向链表如何完成遍历，添加，修改和删除的思路
对上图的说明:
分析 双向链表的遍历，添加，修改，删除的操作思路===》代码实现 - 历 遍历 方和 单链表一样，只是可以向前，也可以向后查找
- 加 添加 (默认添加到双向链表的最后)
(1) 先找到双向链表的最后这个节点
(2) temp.next = newHeroNode
(3) newHeroNode.pre = temp; - 改 修改 思路和 原来的单向链表一样.
- 删除
(1) 因为是双向链表，因此，我们可以实现自我删除某个节点
(2) 直接找到要删除的这个节点，比如 temp
(3) temp.pre.next = temp.next
(4) temp.next.pre = temp.pre;
双向链表的代码实现
DoubleLinkedListNode.java
package com.yg.datastructures.linkedlist;/*** @Description: 双链表的模型* @Author yg* @Date 2021-03-24 9:42*/
public class DoubleLinkedListNode {private int id;private String name;private int age;private String phone;private DoubleLinkedListNode next;private DoubleLinkedListNode pre;public DoubleLinkedListNode(int id, String name, int age, String phone) {this.id = id;this.name = name;this.age = age;this.phone = phone;}public int getId() {return id;}public void setId(int id) {this.id = id;}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}public String getPhone() {return phone;}public void setPhone(String phone) {this.phone = phone;}public DoubleLinkedListNode getNext() {return next;}public void setNext(DoubleLinkedListNode next) {this.next = next;}public DoubleLinkedListNode getPre() {return pre;}public void setPre(DoubleLinkedListNode pre) {this.pre = pre;}@Overridepublic String toString() {return "DoubleLinkedListNode{" +"id=" + id +", name='" + name + '\'' +", age=" + age +", phone='" + phone + '\'' +'}';}
}DoubleLinkedList.java
package com.yg.datastructures.linkedlist;import java.util.Stack;/*** @Description: 双链表操作* @Author yg* @Date 2021-03-24 9:42*/
public class DoubleLinkedList {DoubleLinkedListNode head = new DoubleLinkedListNode(0, "", 0, "");/*** 获取头节点，空的头节点** @return*/public DoubleLinkedListNode getHead() {return head;}/*** 获取链表 的长度** @return*/public int getLength() {if (getHead().getNext() == null) {return 0;}int sum = 0;DoubleLinkedListNode temp = getHead().getNext();while (true) {if (temp != null) {sum++;} else {break;}temp = temp.getNext();}return sum;}/*** 添加节点** @param DoubleLinkedListNode*/public void addNode(DoubleLinkedListNode doubleLinkedListNode) {DoubleLinkedListNode temp = getHead();while (true) {if (temp.getId() == doubleLinkedListNode.getId()) {throw new RuntimeException("添加的节点id已经存在：" + doubleLinkedListNode);}if (temp.getNext() == null) {//找到了最后的节点，将添加的节点添加到尾部break;}temp = temp.getNext();}temp.setNext(doubleLinkedListNode);//双链表增加 向前指向doubleLinkedListNode.setPre(temp);}/*** 按照id顺序添加节点** @param DoubleLinkedListNode*/public void addOrderById(DoubleLinkedListNode doubleLinkedListNode) {DoubleLinkedListNode temp = getHead();boolean flag = false;while (true) {if (temp.getNext() == null) {break;}//找到要添加的前一个id DoubleLinkedListNode.getId()<= 当前对比的id//需要找到添加的位置的前一个节点，if (doubleLinkedListNode.getId() < temp.getNext().getId()) {break;} else if (doubleLinkedListNode.getId() == temp.getNext().getId()) {flag = true;break;}temp = temp.getNext();}//temp 就是那个节点if (flag) {System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", doubleLinkedListNode.getId());} else {//这里添加注意顺序，如果颠倒则会链表无限循环了doubleLinkedListNode.setNext(temp.getNext());temp.setNext(doubleLinkedListNode);}}/*** 更新节点 单链表一样** @param DoubleLinkedListNode* @return*/public DoubleLinkedListNode updateNode(DoubleLinkedListNode DoubleLinkedListNode) {if (head.getNext() == null) {throw new RuntimeException("链表为空，无有效数据更新！");}//从第一关元素遍历，不能给更新头节点DoubleLinkedListNode temp = head.getNext();//标志位判断是否找到更新节点boolean flag = false;while (true) {if (temp.getId() == DoubleLinkedListNode.getId()) {//说明找到了，flag = true;break;}if (temp.getNext() == null) {//说明已经到最后了，也没有找到。System.out.println("没有找到要更新的节点：" + DoubleLinkedListNode);break;}temp = temp.getNext();}if (flag) {//进来表示找到了temp.setAge(DoubleLinkedListNode.getAge());temp.setName(DoubleLinkedListNode.getName());temp.setPhone(DoubleLinkedListNode.getPhone());return temp;}return null;}/*** 删除节点* // 1 对于双向链表，我们可以直接找到要删除的这个节点* // 2 找到后，自我删除即可** @param delNo*/public void delNode(int delNo) {if (isNull()) {//删除从第一个节点开始遍历DoubleLinkedListNode temp = getHead().getNext();boolean flag = false;while (true) {if (temp == null) {//表示已经找完了，还没有找到删除的元素break;}if (temp.getId() == delNo) {//找到要删除节点flag = true;break;}temp = temp.getNext();}if (flag) {//进来表示找到了，此时的temp 就是要删除的if (temp.getNext() != null) {temp.getPre().setNext(temp.getNext());temp.getNext().setPre(temp.getPre());} else {//如果是最后一个节点temp.getPre().setNext(null);}}}}/*** 打印链表*/public void showList() {if (isNull()) {DoubleLinkedListNode temp = getHead().getNext();System.out.println("----------准备打印列表------------");while (true) {if (temp == null) {//表示已经到头了break;}System.out.println(temp);temp = temp.getNext();}System.out.println("----------打印列表结束------------");}}/*** 查找单链表中的倒数第 k 个结点* //思路* //1. 编写一个方法，接收 head 节点，同时接收一个 index* //2. index 表示是倒数第 index 个节点* //3. 先把链表从头到尾遍历，得到链表的总的长度 getLength* //4. 得到 size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到* //5. 如果找到了，则返回该节点，否则返回 nulll** @param DoubleLinkedListNode 链表* @param index 倒数个数* @return*/public DoubleLinkedListNode findLastIndexNode(DoubleLinkedListNode DoubleLinkedListNode, int index) {int length = getLength();DoubleLinkedListNode temp = DoubleLinkedListNode;if (isNull()) {//有效性判断if (index <= 0 || index > length) {return null;}for (int i = 0; i < length - index + 1; i++) {temp = temp.getNext();}return temp;}return null;}/*** 判断是否为空** @return*/public boolean isNull() {if (head.getNext() == null) {System.out.println("链表为空，无法操作！");return false;}return true;}/*** 将单链表反转** @param head 链表的头* @return*/public DoubleLinkedListNode reverseLinkedList(DoubleLinkedListNode head) {if (head.getNext() == null || head.getNext().getNext() == null) {//链表为空或者只有一个元素，无需反转return head;}//定义一个辅助的指针(变量)，帮助我们遍历原来的链表//遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 newNode 的最前端//头插法DoubleLinkedListNode newNode = new DoubleLinkedListNode(0, "", 0, "");DoubleLinkedListNode temp = head.getNext();DoubleLinkedListNode next = null;while (true) {if (temp != null) {//临时保存下一个节点next = temp.getNext();//设置当前节点的下一个节点为新链表的第一个节点temp.setNext(newNode.getNext());//设置新链表的第一个节点为当前插入的节点。newNode.setNext(temp);//temp 右移动temp = next;}else{break;}}//将 head.next 指向 newNode.next , 实现单链表的反转head.setNext(newNode.getNext());return head;}/*** 单链表的逆序打印代码* 利用栈 实现* @param head*/public void reversePrint(DoubleLinkedListNode head){Stack<DoubleLinkedListNode> stack = new Stack<DoubleLinkedListNode>();DoubleLinkedListNode temp = head.getNext();while(true){if(temp == null){break;}stack.push(temp);temp = temp.getNext();}while(stack.size()>0){System.out.println("出栈顺序："+stack.pop());}}
}DoubleLinkedListDemo.java
package com.yg.datastructures.linkedlist;/*** @Description: TODO(这里用一句话描述这个类的作用)* @Author yg* @Date 2021-03-24 9:40*/
public class DoubleLinkedListDemo {public static void main(String[] args) {DoubleLinkedListNode node1 = new DoubleLinkedListNode(1, "李白", 18, "18609287231");DoubleLinkedListNode node2 = new DoubleLinkedListNode(2, "杜甫", 20, "18709873321");DoubleLinkedListNode node3 = new DoubleLinkedListNode(3, "白居易", 22, "1818873321");DoubleLinkedListNode node4 = new DoubleLinkedListNode(4, "李清照", 25, "17638779333");DoubleLinkedListNode node5 = new DoubleLinkedListNode(5, "王安石", 33, "1887788772");DoubleLinkedList doubleLinkedList = new DoubleLinkedList();doubleLinkedList.addNode(node1);doubleLinkedList.addNode(node2);doubleLinkedList.addNode(node4);doubleLinkedList.showList();doubleLinkedList.delNode(2);System.out.println("-------------删除后链表--------------");doubleLinkedList.showList();System.out.println("-------------添加5后链表--------------");doubleLinkedList.addNode(node5);doubleLinkedList.showList();System.out.println("-------------顺序添加2，3后链表--------------");doubleLinkedList.addOrderById(node2);doubleLinkedList.addOrderById(node3);doubleLinkedList.showList();System.out.println("-------------修改后链表--------------");doubleLinkedList.updateNode(new DoubleLinkedListNode(1, "茅以升", 33, "1879983332"));doubleLinkedList.showList();System.out.println("链表长度length = " + doubleLinkedList.getLength());System.out.println("链表的倒数第3个节点=" + doubleLinkedList.findLastIndexNode(doubleLinkedList.getHead(), 3));DoubleLinkedListNode reverseLinkedListNode = doubleLinkedList.reverseLinkedList(doubleLinkedList.getHead());System.out.println("---------------反转后的链表为--------------");doubleLinkedList.showList();System.out.println("----------------逆序打印链表---------------");doubleLinkedList.reversePrint(doubleLinkedList.getHead());}
}运行结果：
D:\jdk1.8.0_251\bin\java.exe -agentlib:jdwp=transport=dt_socket,address=127.0.0.1:1466,suspend=y,server=n -javaagent:C:\Users\Administrator\AppData\Local\JetBrains\IntelliJIdea2020.3\captureAgent\debugger-agent.jar -Dfile.encoding=UTF-8 -classpath "D:\jdk1.8.0_251\jre\lib\charsets.jar;D:\jdk1.8.0_251\jre\lib\deploy.jar;D:\jdk1.8.0_251\jre\lib\ext\access-bridge-64.jar;D:\jdk1.8.0_251\jre\lib\ext\cldrdata.jar;D:\jdk1.8.0_251\jre\lib\ext\dnsns.jar;D:\jdk1.8.0_251\jre\lib\ext\jaccess.jar;D:\jdk1.8.0_251\jre\lib\ext\jfxrt.jar;D:\jdk1.8.0_251\jre\lib\ext\localedata.jar;D:\jdk1.8.0_251\jre\lib\ext\nashorn.jar;D:\jdk1.8.0_251\jre\lib\ext\sunec.jar;D:\jdk1.8.0_251\jre\lib\ext\sunjce_provider.jar;D:\jdk1.8.0_251\jre\lib\ext\sunmscapi.jar;D:\jdk1.8.0_251\jre\lib\ext\sunpkcs11.jar;D:\jdk1.8.0_251\jre\lib\ext\zipfs.jar;D:\jdk1.8.0_251\jre\lib\javaws.jar;D:\jdk1.8.0_251\jre\lib\jce.jar;D:\jdk1.8.0_251\jre\lib\jfr.jar;D:\jdk1.8.0_251\jre\lib\jfxswt.jar;D:\jdk1.8.0_251\jre\lib\jsse.jar;D:\jdk1.8.0_251\jre\lib\management-agent.jar;D:\jdk1.8.0_251\jre\lib\plugin.jar;D:\jdk1.8.0_251\jre\lib\resources.jar;D:\jdk1.8.0_251\jre\lib\rt.jar;D:\IdeaProjects\datastructures\target\classes;D:\RepMaven\org\springframework\boot\spring-boot-starter-web\2.4.4\spring-boot-starter-web-2.4.4.jar;D:\RepMaven\org\springframework\boot\spring-boot-starter\2.4.4\spring-boot-starter-2.4.4.jar;D:\RepMaven\org\springframework\boot\spring-boot\2.4.4\spring-boot-2.4.4.jar;D:\RepMaven\org\springframework\boot\spring-boot-autoconfigure\2.4.4\spring-boot-autoconfigure-2.4.4.jar;D:\RepMaven\org\springframework\boot\spring-boot-starter-logging\2.4.4\spring-boot-starter-logging-2.4.4.jar;D:\RepMaven\ch\qos\logback\logback-classic\1.2.3\logback-classic-1.2.3.jar;D:\RepMaven\ch\qos\logback\logback-core\1.2.3\logback-core-1.2.3.jar;D:\RepMaven\org\apache\logging\log4j\log4j-to-slf4j\2.13.3\log4j-to-slf4j-2.13.3.jar;D:\RepMaven\org\apache\logging\log4j\log4j-api\2.13.3\log4j-api-2.13.3.jar;D:\RepMaven\org\slf4j\jul-to-slf4j\1.7.30\jul-to-slf4j-1.7.30.jar;D:\RepMaven\jakarta\annotation\jakarta.annotation-api\1.3.5\jakarta.annotation-api-1.3.5.jar;D:\RepMaven\org\yaml\snakeyaml\1.27\snakeyaml-1.27.jar;D:\RepMaven\org\springframework\boot\spring-boot-starter-json\2.4.4\spring-boot-starter-json-2.4.4.jar;D:\RepMaven\com\fasterxml\jackson\core\jackson-databind\2.11.4\jackson-databind-2.11.4.jar;D:\RepMaven\com\fasterxml\jackson\core\jackson-annotations\2.11.4\jackson-annotations-2.11.4.jar;D:\RepMaven\com\fasterxml\jackson\core\jackson-core\2.11.4\jackson-core-2.11.4.jar;D:\RepMaven\com\fasterxml\jackson\datatype\jackson-datatype-jdk8\2.11.4\jackson-datatype-jdk8-2.11.4.jar;D:\RepMaven\com\fasterxml\jackson\datatype\jackson-datatype-jsr310\2.11.4\jackson-datatype-jsr310-2.11.4.jar;D:\RepMaven\com\fasterxml\jackson\module\jackson-module-parameter-names\2.11.4\jackson-module-parameter-names-2.11.4.jar;D:\RepMaven\org\springframework\boot\spring-boot-starter-tomcat\2.4.4\spring-boot-starter-tomcat-2.4.4.jar;D:\RepMaven\org\apache\tomcat\embed\tomcat-embed-core\9.0.44\tomcat-embed-core-9.0.44.jar;D:\RepMaven\org\glassfish\jakarta.el\3.0.3\jakarta.el-3.0.3.jar;D:\RepMaven\org\apache\tomcat\embed\tomcat-embed-websocket\9.0.44\tomcat-embed-websocket-9.0.44.jar;D:\RepMaven\org\springframework\spring-web\5.3.5\spring-web-5.3.5.jar;D:\RepMaven\org\springframework\spring-beans\5.3.5\spring-beans-5.3.5.jar;D:\RepMaven\org\springframework\spring-webmvc\5.3.5\spring-webmvc-5.3.5.jar;D:\RepMaven\org\springframework\spring-aop\5.3.5\spring-aop-5.3.5.jar;D:\RepMaven\org\springframework\spring-context\5.3.5\spring-context-5.3.5.jar;D:\RepMaven\org\springframework\spring-expression\5.3.5\spring-expression-5.3.5.jar;D:\RepMaven\mysql\mysql-connector-java\8.0.23\mysql-connector-java-8.0.23.jar;D:\RepMaven\org\slf4j\slf4j-api\1.7.30\slf4j-api-1.7.30.jar;D:\RepMaven\org\springframework\spring-core\5.3.5\spring-core-5.3.5.jar;D:\RepMaven\org\springframework\spring-jcl\5.3.5\spring-jcl-5.3.5.jar;D:\JetBrains\IntelliJ IDEA 2020.3\lib\idea_rt.jar" com.yg.datastructures.linkedlist.DoubleLinkedListDemo
Connected to the target VM, address: '127.0.0.1:1466', transport: 'socket'
----------准备打印列表------------
DoubleLinkedListNode{id=1, name='李白', age=18, phone='18609287231'}
DoubleLinkedListNode{id=2, name='杜甫', age=20, phone='18709873321'}
DoubleLinkedListNode{id=4, name='李清照', age=25, phone='17638779333'}
----------打印列表结束------------
-------------删除后链表--------------
----------准备打印列表------------
DoubleLinkedListNode{id=1, name='李白', age=18, phone='18609287231'}
DoubleLinkedListNode{id=4, name='李清照', age=25, phone='17638779333'}
----------打印列表结束------------
-------------添加5后链表--------------
----------准备打印列表------------
DoubleLinkedListNode{id=1, name='李白', age=18, phone='18609287231'}
DoubleLinkedListNode{id=4, name='李清照', age=25, phone='17638779333'}
DoubleLinkedListNode{id=5, name='王安石', age=33, phone='1887788772'}
----------打印列表结束------------
-------------顺序添加2，3后链表--------------
----------准备打印列表------------
DoubleLinkedListNode{id=1, name='李白', age=18, phone='18609287231'}
DoubleLinkedListNode{id=2, name='杜甫', age=20, phone='18709873321'}
DoubleLinkedListNode{id=3, name='白居易', age=22, phone='1818873321'}
DoubleLinkedListNode{id=4, name='李清照', age=25, phone='17638779333'}
DoubleLinkedListNode{id=5, name='王安石', age=33, phone='1887788772'}
----------打印列表结束------------
-------------修改后链表--------------
----------准备打印列表------------
DoubleLinkedListNode{id=1, name='茅以升', age=33, phone='1879983332'}
DoubleLinkedListNode{id=2, name='杜甫', age=20, phone='18709873321'}
DoubleLinkedListNode{id=3, name='白居易', age=22, phone='1818873321'}
DoubleLinkedListNode{id=4, name='李清照', age=25, phone='17638779333'}
DoubleLinkedListNode{id=5, name='王安石', age=33, phone='1887788772'}
----------打印列表结束------------
链表长度length = 5
链表的倒数第3个节点=DoubleLinkedListNode{id=3, name='白居易', age=22, phone='1818873321'}
---------------反转后的链表为--------------
----------准备打印列表------------
DoubleLinkedListNode{id=5, name='王安石', age=33, phone='1887788772'}
DoubleLinkedListNode{id=4, name='李清照', age=25, phone='17638779333'}
DoubleLinkedListNode{id=3, name='白居易', age=22, phone='1818873321'}
DoubleLinkedListNode{id=2, name='杜甫', age=20, phone='18709873321'}
DoubleLinkedListNode{id=1, name='茅以升', age=33, phone='1879983332'}
----------打印列表结束------------
----------------逆序打印链表---------------
出栈顺序：DoubleLinkedListNode{id=1, name='茅以升', age=33, phone='1879983332'}
出栈顺序：DoubleLinkedListNode{id=2, name='杜甫', age=20, phone='18709873321'}
出栈顺序：DoubleLinkedListNode{id=3, name='白居易', age=22, phone='1818873321'}
出栈顺序：DoubleLinkedListNode{id=4, name='李清照', age=25, phone='17638779333'}
出栈顺序：DoubleLinkedListNode{id=5, name='王安石', age=33, phone='1887788772'}
Disconnected from the target VM, address: '127.0.0.1:1466', transport: 'socket'Process finished with exit code 0
](https://img-blog.csdnimg.cn/2019011510012640.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppbmdMaXNlbg==,size_16,color_FFFFFF,t_70)
