快捷導(dǎo)航

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

更新時(shí)間：2022年05月25日 16:33:54 作者：away.....

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

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

1、雙向鏈表

1.1 雙向鏈表的每個(gè)節(jié)點(diǎn)組成包含節(jié)點(diǎn)數(shù)據(jù)，上一個(gè)節(jié)點(diǎn)（pre），下一個(gè)節(jié)點(diǎn)（next）

1.2 雙向鏈表節(jié)點(diǎn)結(jié)構(gòu)

class Node {
//節(jié)點(diǎn)數(shù)據(jù)data
?? ??? ?int data;
?? ??? ?Node pre;
?? ??? ?Node next;

?? ??? ?public Node(int data) {
?? ??? ??? ?this.data = data;
?? ??? ?}
?? ??? ?public Node() {
?? ??? ??? ?super();
?? ??? ?}
?? ??? ?

?? ?}

2、雙向鏈表的增刪改查（crud）

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) {
?? ??? ?// 如果是頭結(jié)點(diǎn)
?? ??? ?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("雙向鏈表為空，無(wú)法進(jìn)行刪除操作！");
?? ??? ?} else {
?? ??? ??? ?
?? ??? ??? ?Node node = first;
?? ??? ??? ?while(true) {
?? ??? ??? ??? ?// 首節(jié)點(diǎn)的刪除可能
?? ??? ??? ??? ?if (node.data == val) {
?? ??? ??? ??? ??? ?//如果只有一個(gè)節(jié)點(diǎn)
?? ??? ??? ??? ??? ?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;
?? ??? ??? ??? ??? ??? ?//刪除后重新循環(huán)判斷首節(jié)點(diǎn)是否值相等
?? ??? ??? ??? ??? ??? ?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;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?// 末節(jié)點(diǎn)刪除可能
?? ??? ??? ??? ??? ?if (node.data == val) {
?? ??? ??? ??? ??? ??? ?node.pre.next=null;
?? ??? ??? ??? ??? ??? ?node.pre=null;

?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?System.out.println("刪除所有的"+val+"成功");
?? ??? ??? ??? ??? ?//末節(jié)點(diǎn)判斷完成后，結(jié)束循環(huán)
?? ??? ??? ??? ??? ?return;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?}

?? ?}
?? ?/**
?? ? * 遍歷雙向鏈表操作
?? ? */
?? ?public void traverse() {
?? ??? ?if(first==null) {
?? ??? ??? ?System.out.println("雙向鏈表為空");
?? ??? ?}else {
?? ??? ??? ?Node node = first;
?? ??? ??? ?//循環(huán)遍歷到倒數(shù)第二個(gè)節(jié)點(diǎn)截止
?? ??? ??? ?while(node.next!=null) {
?? ??? ??? ??? ?System.out.print(node.data+" ");
?? ??? ??? ??? ?node=node.next;
?? ??? ??? ?}
?? ??? ??? ?//遍歷最后一個(gè)節(jié)點(diǎn)
?? ??? ??? ?System.out.print(node.data);
?? ??? ?}
?? ?}
?? ?/**
?? ? * 雙向鏈表插入操作,在所有值為value的后面插入一個(gè)數(shù)insert
?? ? */
?? ?public void insert(int value,int insert) {
?? ??? ?
?? ??? ?if(first==null) {
?? ??? ??? ?System.out.println("雙向鏈表為空，無(wú)法插入");
?? ??? ?}else {
?? ??? ??? ?Node node = first;
?? ??? ??? ?//循環(huán)遍歷到倒數(shù)第二個(gè)節(jié)點(diǎn)截止
?? ??? ??? ?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;
?? ??? ??? ?}
?? ??? ??? ?//最后一個(gè)節(jié)點(diǎn)后插入
?? ??? ??? ?if(node.data == value) {
?? ??? ??? ??? ?Node insertNode = new Node(insert);
?? ??? ??? ??? ?node.next = insertNode;
?? ??? ??? ??? ?insertNode.pre = node;
?? ??? ??? ?}
?? ??? ??? ?System.out.println();
?? ??? ??? ?System.out.println("插入操作完成");
?? ??? ??? ?
?? ??? ?}
?? ?}
?? ?/**
?? ? * 雙向鏈表修改數(shù)據(jù),將所有值為val的修改為revised
?? ? */
?? ?public void revise(int val,int revised) {
?? ??? ?if(first==null) {
?? ??? ??? ?System.out.println("雙向鏈表為空，無(wú)法修改");
?? ??? ?}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("鏈表為空，無(wú)法查找");
?? ??? ?}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 測(cè)試類(lèi)（main入口函數(shù)）

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);

?? ?}
}

3、一些缺點(diǎn)待修改

1）、循環(huán)結(jié)束是到倒數(shù)第二個(gè)節(jié)點(diǎn)截止的，要考慮多種不同的情況，頭節(jié)點(diǎn)刪除，尾結(jié)點(diǎn)刪除等，導(dǎo)致刪除函數(shù)復(fù)雜了很多
2）、在contain函數(shù)中有修改到循環(huán)到最后一個(gè)節(jié)點(diǎn)
3）、后續(xù)對(duì)刪除函數(shù)修改有空再操作（待完成）

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

您可能感興趣的文章: