Java數(shù)據(jù)結(jié)構(gòu)中雙向鏈表的實現(xiàn)
更新時間：2022年05月26日 14:10:03 作者：Bro_cat
這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)中雙向鏈表的實現(xiàn),雙向鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu),它允許在鏈表中的任意位置進(jìn)行高效的插入和刪除操作,需要的朋友可以參考下
引言
雙向鏈表（Double Linked List）是一種常見的數(shù)據(jù)結(jié)構(gòu)，它允許在鏈表中的任意位置進(jìn)行高效的插入和刪除操作。與單向鏈表不同，雙向鏈表中的每個節(jié)點不僅包含指向下一個節(jié)點的指針，還包含指向前一個節(jié)點的指針。這種結(jié)構(gòu)使得雙向鏈表在某些操作上比單向鏈表更加靈活和高效。
雙向鏈表的結(jié)構(gòu)
在Java中，雙向鏈表可以通過一個內(nèi)部類Node來表示鏈表中的每個節(jié)點。每個節(jié)點包含三個屬性：
prev：指向前一個節(jié)點的指針。next：指向下一個節(jié)點的指針。data：節(jié)點存儲的數(shù)據(jù)。
static class Node {
Node prev; // 指向前一個節(jié)點
Node next; // 指向下一個節(jié)點
int data; // 節(jié)點數(shù)據(jù)
public Node(Node prev, Node next, int data) {
this.prev = prev;
this.next = next;
this.data = data;
}
}雙向鏈表的初始化
在雙向鏈表的初始化過程中，我們通常會創(chuàng)建兩個哨兵節(jié)點（head和tail），它們分別代表鏈表的頭和尾。這兩個節(jié)點不存儲實際數(shù)據(jù)，僅用于簡化鏈表的操作。
public DoubleLinkedList() {
head = new Node(null, null, 0);
tail = new Node(null, null, 0);
head.next = tail;
tail.prev = head;
}雙向鏈表的基本操作
1. 插入操作
雙向鏈表支持在鏈表的任意位置插入新節(jié)點。以下是幾個常見的插入操作：
在鏈表頭部插入節(jié)點：
public void addfirst(int data) {
add(0, data);
}在鏈表尾部插入節(jié)點：
public void addlast(int data) {
Node prev = tail.prev;
Node newNode = new Node(prev, tail, data);
prev.next = newNode;
tail.prev = newNode;
}在指定位置插入節(jié)點：
public void add(int index, int data) {
Node prev = findNode(index - 1);
Node next = prev.next;
Node newNode = new Node(prev, next, data);
prev.next = newNode;
next.prev = newNode;
if (prev == null) {
throw illegalIndex(index);
}
}2. 刪除操作
雙向鏈表同樣支持在鏈表的任意位置刪除節(jié)點。以下是幾個常見的刪除操作：
刪除鏈表頭部的節(jié)點：
public void removefirst() {
remove(0);
}刪除鏈表尾部的節(jié)點：
public void removelast() {
Node removeNode = tail.prev;
Node prev = removeNode.prev;
prev.next = tail;
tail.prev = prev;
}刪除指定位置的節(jié)點：
public void remove(int index) {
Node prev = findNode(index - 1);
Node removeNode = prev.next;
Node next = removeNode.next;
prev.next = next;
next.prev = prev;
if (prev == null || removeNode == tail) {
throw illegalIndex(index);
}
}3. 查找操作
雙向鏈表可以通過索引查找節(jié)點：
public Node findNode(int index) {
int i = -1;
for (Node current = head; current != tail; current = current.next, i++) {
if (i == index) {
return current;
}
}
return null;
}4. 遍歷操作
雙向鏈表可以通過遍歷操作輸出鏈表中的所有節(jié)點數(shù)據(jù)：
public void traverse() {
Node current = head.next;
while (current != tail) {
System.out.println(current.data);
current = current.next;
}
}5. 修改操作
根據(jù)索引修改節(jié)點的的值
public void set(int index, int data) {
Node node = findNode(index);
if (node == null || node == tail) {
throw illegalIndex(index);
}
node.data = data;
}應(yīng)用場景
雙向鏈表在許多場景中都有廣泛的應(yīng)用，例如：
- LRU緩存：雙向鏈表可以用于實現(xiàn)LRU（Least Recently Used）緩存算法，通過鏈表的插入和刪除操作來維護(hù)緩存中的數(shù)據(jù)。
- 瀏覽器歷史記錄：瀏覽器的歷史記錄可以通過雙向鏈表來實現(xiàn)，用戶可以向前或向后導(dǎo)航。
- 文本編輯器：在文本編輯器中，雙向鏈表可以用于實現(xiàn)光標(biāo)的移動和文本的插入與刪除。
源碼
下面是上面提到的所有源碼
package school.doublelinkedlist;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* 文件名: null.java
* 作者: 20526
* 創(chuàng)建時間: 2024/9/9 17:28
* 描述:雙向鏈表
*/
public class DoubleLinkedList implements Iterator<Integer> {
private Node head;//頭哨兵節(jié)點
private Node tail;//尾哨兵節(jié)點
public DoubleLinkedList() {
head = new Node(null, null, 0);
tail = new Node(null, null, 0);
head.next = tail;
tail.prev = head;
}
@Override
public boolean hasNext() {
Node current = head.next;
return current!= tail;
}
@Override
public Integer next() {
Node current = head.next;
if (!hasNext()) {
throw new NoSuchElementException();
}
int data = current.data;
current = current.next;
return data;
}
static class Node {
Node prev;//指向前一個節(jié)點
Node next;//指向下一個節(jié)點
int data;//節(jié)點數(shù)據(jù)
public Node(Node prev, Node next, int data) {
this.prev = prev;
this.next = next;
this.data = data;
}
}
public Node findNode(int index) {
int i =-1;
for(Node current = head;current!=tail;current=current.next,i++){
if(i==index){
return current;
}
}
return null;
}
public void traverse() {
Node current = head.next;
while (current != tail) {
System.out.println(current.data);
current = current.next;
}
}
public void addfirst(int data) {
add(0, data);
}
public void addlast(int data) {
Node prev = tail.prev;
Node newNode = new Node(prev, tail, data);
prev.next = newNode;
}
public void add(int index, int data) {
Node prev = findNode(index-1);
Node next = prev.next;
Node newNode = new Node(prev, next, data);
prev.next = newNode;
next.prev = newNode;
if (prev == null){
throw illegalIndex(index);
}
}
public void removefirst() {
remove(0);
}
public void removelast() {
Node removeNode = tail.prev;
Node prev = removeNode.prev;
prev.next = tail;
tail.prev = prev;
}
public void remove(int index) {
Node prev = findNode(index-1);
Node removeNode = prev.next;
Node next = removeNode.next;
prev.next = next;
next.prev = prev;
if (prev == null){
throw illegalIndex(index);
}
if (removeNode == tail){
throw illegalIndex(index);
}
}
public void set(int index, int data) {
Node node = findNode(index);
if (node == null || node == tail) {
throw illegalIndex(index);
}
node.data = data;
}
private IllegalArgumentException illegalIndex(int index) {
throw new IllegalArgumentException(
String.format("Index: [%d]不合法%n", index));
}
}測試類
package school.doublelinkedlist;
import org.junit.Test;
public class DoubleLinkedListTest {
@Test
public void test() {
DoubleLinkedList list = new DoubleLinkedList();
list.add(0,1);
list.add(1,2);
list.add(2,3);
list.addlast(4);
list.traverse();
}
}總結(jié)
雙向鏈表是一種靈活且高效的數(shù)據(jù)結(jié)構(gòu)，它通過每個節(jié)點中的前后指針，使得在鏈表中的任意位置進(jìn)行插入和刪除操作變得簡單。希望對你有所幫助。
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)中雙向鏈表的實現(xiàn)的文章就介紹到這了,更多相關(guān)Java雙向鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
SpringBoot HttpMessageConverter消息轉(zhuǎn)換器的使用詳解
在整個數(shù)據(jù)流轉(zhuǎn)過程中，前端的請求報文轉(zhuǎn)化為Java對象，Java對象轉(zhuǎn)化為響應(yīng)報文，這里就用到了消息轉(zhuǎn)換器HttpMessageConverter2022-06-06
Java 多態(tài)中繼承的轉(zhuǎn)型詳解與用法分析
繼承是java面向?qū)ο缶幊碳夹g(shù)的一塊基石，因為它允許創(chuàng)建分等級層次的類。繼承就是子類繼承父類的特征和行為，使得子類對象（實例）具有父類的實例域和方法，或子類從父類繼承方法，使得子類具有父類相同的行為2021-10-10
這篇文章主要介紹了Java同步代碼塊和同步方法原理與應(yīng)用,結(jié)合具體案例形式分析了使用java同步代碼塊和同步方法實現(xiàn)買票功能的相關(guān)原理與操作技巧,需要的朋友可以參考下2019-10-10
ConstraintValidator類如何實現(xiàn)自定義注解校驗前端傳參
這篇文章主要介紹了ConstraintValidator類實現(xiàn)自定義注解校驗前端傳參的操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-06-06
在工作中，我們用到分布式緩存的時候，第一選擇就是Redis，今天介紹一下SpringBoot如何集成Redis的，具有一定的參考價值，感興趣的可以了解一下2021-09-09
這篇文章主要給大家介紹了關(guān)于Java中你所不知道的一些關(guān)于Integer的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2017-12-12
這篇文章主要介紹了Java如何把map分割成多個map,本文通過實例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友參考下吧2024-08-08
詳解SpringCloud-Alibaba-Seata分布式事務(wù)
這篇文章主要介紹了SpringCloud-Alibaba-Seata分布式事務(wù)的相關(guān)知識，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-12-12
這篇文章主要介紹了java編寫簡單的ATM存取系統(tǒng)，附上思路和具體實現(xiàn)代碼，適合新人練手用，推薦給小伙伴們。2015-02-02
這篇文章主要介紹了一學(xué)即會之JDK版本快速切換方法,詳細(xì)給大家講解了如何下載、安裝和配置多個JDK版本,并通過設(shè)置環(huán)境變量和編寫批處理腳本來切換JDK版本,需要的朋友可以參考下2025-03-03