基于Java實(shí)現(xiàn)雙向鏈表

更新時(shí)間：2022年05月26日 15:49:57 作者：fan兒

這篇文章主要為大家詳細(xì)介紹了基于Java實(shí)現(xiàn)雙向鏈表，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

本文實(shí)例為大家分享了Java實(shí)現(xiàn)雙向鏈表的具體代碼，供大家參考，具體內(nèi)容如下

雙向鏈表與單鏈表的對(duì)比：

1、單向鏈表查找只能是一個(gè)方向，雙向鏈表可以向前或者向后查找
2、單向鏈表不能自我刪除，需要靠輔助節(jié)點(diǎn)**（即需要通過(guò)找到要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，通過(guò)該節(jié)點(diǎn)進(jìn)行刪除的操作，而雙向鏈表只需找到要?jiǎng)h除的節(jié)點(diǎn)就行了）**。雙向鏈表可以自我刪除

雙向鏈表示意圖

分析（代碼實(shí)現(xiàn)原理）：temp為輔助節(jié)點(diǎn)（因?yàn)轭^節(jié)點(diǎn)不可動(dòng)）
1、遍歷：方式與單鏈表一致，但是是雙向的，可以向前，也可以向后
2、添加（默認(rèn)添加到最后面）
（1）先找到鏈表的最后一個(gè)節(jié)點(diǎn)
（2）temp.next=newnode
（3）newnode.pre=temp
3、修改：思路與原理與單鏈表一致
4、刪除：
（1）因?yàn)槭请p向鏈表，可以自我刪除該節(jié)點(diǎn)
（2）找到要?jiǎng)h除的節(jié)點(diǎn)，假設(shè)這個(gè)節(jié)點(diǎn)為temp
（3）temp.pre.next=temp.next
（4）temp.next.pre=temp.pre

添加節(jié)點(diǎn)（按順序）：

步驟：

（1）找到要添加節(jié)點(diǎn)位置的前一個(gè)節(jié)點(diǎn)(temp)
（2）node.next=temp.next
（3）temp.next.pre=node
（4）temp.next=node
（5）node.pre=temp

代碼實(shí)現(xiàn)：

public class DoubleLinkedList {
?? ? //創(chuàng)建頭結(jié)點(diǎn)。表示鏈表的頭
?? ?private Node Head=new Node(0,"","");
?? ?
?? ?//返回頭結(jié)點(diǎn)
?? ?public Node getHead() {
?? ??? ?return Head;
?? ?}
?? ?//AddNode1:添加節(jié)點(diǎn)到單鏈表的尾部
?? ?//思路：當(dāng)不考慮節(jié)點(diǎn)順序
?? ?//1、找到鏈表的最后一個(gè)節(jié)點(diǎn)
?? ?//2、將最后這個(gè)節(jié)點(diǎn)的Next指向新節(jié)點(diǎn)
?? ?public void AddNode1(Node node) {
?? ??? ?//因?yàn)轭^節(jié)點(diǎn)不能動(dòng)，所以需要一個(gè)輔助節(jié)點(diǎn)遍歷
?? ??? ?Node temp=Head;
?? ??? ?while(true) {
?? ??? ??? ?//找到鏈表的最后一個(gè)節(jié)點(diǎn)
?? ??? ??? ?if(temp.next==null) {
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ??? ?//否則temp=temp的下一個(gè)節(jié)點(diǎn)
?? ??? ??? ?temp=temp.next;
?? ??? ??? ?
?? ??? ?}
?? ??? ?//循環(huán)出來(lái)之后，temp是最后一個(gè)節(jié)點(diǎn)
?? ??? ?temp.next=node;
?? ??? ?node.pre=temp;
?? ?}
?? ?
?? ?//AddNode2:添加節(jié)點(diǎn)，按順序
?? ?public void AddNode2(Node node) {
?? ??? ?//因?yàn)轭^結(jié)點(diǎn)不能動(dòng)，所以需要一個(gè)輔助節(jié)點(diǎn)遍歷，找到添加新節(jié)點(diǎn)的位置
?? ??? ?Node temp=Head;
?? ??? ?boolean flag=false; //用于標(biāo)識(shí)鏈表中是否已經(jīng)存在新節(jié)點(diǎn)的順序
?? ??? ?while(true) {
?? ??? ??? ?//如果該節(jié)點(diǎn)是最后一個(gè)節(jié)點(diǎn)，則新節(jié)點(diǎn)添加到最后一個(gè)位置
?? ??? ??? ?if(temp.next==null) {
?? ??? ??? ??? ?break;
?? ??? ??? ?}else if(temp.next.number>node.number) { //說(shuō)明找到了添加新節(jié)點(diǎn)的位置
?? ??? ??? ??? ?break;
?? ??? ??? ?}else if(temp.next.number==node.number) { //說(shuō)明新節(jié)點(diǎn)的順序已經(jīng)存在在鏈表中
?? ??? ??? ??? ?flag=true;
?? ??? ??? ?}
?? ??? ??? ?temp=temp.next;
?? ??? ?}
?? ??? ?if(flag) {
?? ??? ??? ?System.out.println("該節(jié)點(diǎn)的順序已經(jīng)存在，插入失敗");
?? ??? ?}else {
?? ??? ??? ?//則說(shuō)明新節(jié)點(diǎn)在鏈表中不存在，插入新節(jié)點(diǎn)
?? ??? ??? ?//新節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)=輔助節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
?? ??? ??? ?node.next=temp.next;
?? ??? ??? ?if(temp.next!=null) { ? //如果temp的下一個(gè)節(jié)點(diǎn)不為空，則temp的下一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為新節(jié)點(diǎn)
?? ??? ??? ??? ?temp.next.pre=node;
?? ??? ??? ?}
?? ??? ??? ?//輔助節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)=新節(jié)點(diǎn)
?? ??? ??? ?temp.next=node;
?? ??? ??? ?//新節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為輔助節(jié)點(diǎn)
?? ??? ??? ?node.pre=temp;
?? ??? ?}
?? ??? ?
?? ?}
?? ?
?? ?//刪除節(jié)點(diǎn)
?? ?public void remove(Node node) {
?? ??? ?if(Head.next==null) {
?? ??? ??? ?System.out.println("鏈表為空！");
?? ??? ??? ?return;
?? ??? ?}
?? ??? ?//創(chuàng)建輔助節(jié)點(diǎn)
?? ??? ?Node temp=Head.next;
?? ??? ?boolean flag=false; //標(biāo)識(shí)是否找到了要?jiǎng)h除的節(jié)點(diǎn)
?? ??? ?while(true) {
?? ??? ??? ?if(temp==null) { //遍歷完鏈表了
?? ??? ??? ??? ?break;
?? ??? ??? ?}else if(temp.number==node.number) { //找到要?jiǎng)h除的節(jié)點(diǎn)了
?? ??? ??? ??? ?flag=true;
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ??? ?temp=temp.next;
?? ??? ?}
?? ??? ?if(flag) { //鏈表中存在要?jiǎng)h除的節(jié)點(diǎn)
?? ??? ??? ?
?? ??? ??? ??? ?temp.pre.next=temp.next;?? ?//令temp的前一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為temp的后一個(gè)節(jié)點(diǎn)
?? ??? ??? ??? ?if(temp.next!=null) { ? ? ? //如果temp不為最后一個(gè)節(jié)點(diǎn)的話
?? ??? ??? ??? ??? ?temp.next.pre=temp.pre; ? ?//令temp的下一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為temp的前一個(gè)節(jié)點(diǎn)
?? ??? ??? ??? ?}
?? ??? ??? ?
?? ??? ?}else {
?? ??? ??? ?System.out.printf("不存在編號(hào)為%d的節(jié)點(diǎn)",node.number);
?? ??? ?}
?? ?}
?? ?
?? ?//修改節(jié)點(diǎn)，按照節(jié)點(diǎn)的Number來(lái)修改
?? ?public void update(Node newNode) {
?? ??? ?if(Head.next==null) {
?? ??? ??? ?System.out.println("鏈表為空！");
?? ??? ??? ?return;
?? ??? ?}
?? ??? ?//創(chuàng)建輔助節(jié)點(diǎn)，對(duì)鏈表遍歷，知道找到等于修改節(jié)點(diǎn)的number的時(shí)候
?? ??? ?Node temp=Head.next;
?? ??? ?boolean flag=false; //用來(lái)標(biāo)識(shí)是否找到了修改節(jié)點(diǎn)的Number
?? ??? ?while(true) {
?? ??? ??? ?if(temp==null) { //則已經(jīng)遍歷完鏈表
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ??? ?if(temp.number==newNode.number) {
?? ??? ??? ??? ?flag=true;
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ??? ?temp=temp.next;
?? ??? ?}
?? ??? ?if(flag) {
?? ??? ??? ?temp.name=newNode.name;
?? ??? ??? ?temp.nickName=newNode.nickName;
?? ??? ?}else {
?? ??? ??? ?System.out.printf("沒(méi)有找到編號(hào)為%d的節(jié)點(diǎn)",newNode.number);
?? ??? ?}
?? ?}
?? ?//展示鏈表
?? ?public void show() {
?? ??? ?if(Head.next==null) {
?? ??? ??? ?System.out.println("鏈表為空！");
?? ??? ??? ?return;
?? ??? ?}
?? ??? ?//因?yàn)轭^節(jié)點(diǎn)不能動(dòng)，所以通過(guò)輔助節(jié)點(diǎn)遍歷鏈表
?? ??? ?Node temp=Head.next;
?? ??? ?while(true) {
?? ??? ??? ?//判斷是不是最后一個(gè)節(jié)點(diǎn)
?? ??? ??? ?if(temp.next==null) {
?? ??? ??? ??? ?System.out.println(temp);
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ??? ?System.out.println(temp);
?? ??? ??? ?//temp指向下一個(gè)節(jié)點(diǎn)
?? ??? ??? ?temp=temp.next;
?? ??? ?}
?? ?}

}

//創(chuàng)建節(jié)點(diǎn)
class Node{
?? ?public int number;
?? ?public String name;
?? ?public String nickName;
?? ?public Node next; //指向下一個(gè)節(jié)點(diǎn)
?? ?public Node pre;//指向前一個(gè)節(jié)點(diǎn)
?? ?//構(gòu)造器
?? ?public Node(int number,String name,String nickName) {
?? ??? ?this.number=number;
?? ??? ?this.name=name;
?? ??? ?this.nickName=nickName;
?? ??? ?
?? ??? ?
?? ?}

?? ?@Override
?? ?public String toString() {
?? ??? ?return "Node [number=" + number + ", name=" + name + ", nickName=" + nickName + "]";
?? ?}
}

測(cè)試代碼：

public static void main(String[] args) {
?? ??? ?// TODO 自動(dòng)生成的方法存根
?? ??? ?Node node1=new Node(1,"宋江","及時(shí)雨");
?? ??? ?Node node2=new Node(2,"盧俊義","玉麒麟");
?? ??? ?Node node3=new Node(3,"吳用","智多星");
?? ??? ?Node node4=new Node(4,"林沖","豹子頭");
?? ??? ?Node node5=new Node(4,"linchong","豹子頭");
?? ??? ?//創(chuàng)建一個(gè)鏈表
?? ??? ?DoubleLinkedList linkedList=new DoubleLinkedList();
?? ??? ?linkedList.AddNode2(node1);
?? ??? ?linkedList.AddNode2(node3);
?? ??? ?linkedList.AddNode2(node4);
?? ??? ?linkedList.AddNode2(node2);
?? ??? ?linkedList.show();
?? ??? ?
?? ??? ?System.out.println("------------");
?? ??? ?linkedList.remove(node4);
?? ??? ?linkedList.show();
?? ?}

結(jié)果：

Node [number=1, name=宋江, nickName=及時(shí)雨]
Node [number=2, name=盧俊義, nickName=玉麒麟]
Node [number=3, name=吳用, nickName=智多星]
Node [number=4, name=林沖, nickName=豹子頭]
————————————————————————
Node [number=1, name=宋江, nickName=及時(shí)雨]
Node [number=2, name=盧俊義, nickName=玉麒麟]
Node [number=3, name=吳用, nickName=智多星]

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: