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),它允許在鏈表中的任意位置進行高效的插入和刪除操作,需要的朋友可以參考下

引言

雙向鏈表（Double Linked List）是一種常見的數(shù)據(jù)結(jié)構(gòu)，它允許在鏈表中的任意位置進行高效的插入和刪除操作。與單向鏈表不同，雙向鏈表中的每個節(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）緩存算法，通過鏈表的插入和刪除操作來維護緩存中的數(shù)據(jù)。
瀏覽器歷史記錄：瀏覽器的歷史記錄可以通過雙向鏈表來實現(xiàn)，用戶可以向前或向后導航。
文本編輯器：在文本編輯器中，雙向鏈表可以用于實現(xiàn)光標的移動和文本的插入與刪除。

源碼

下面是上面提到的所有源碼

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