設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置： 程式碼之家 >> 編程語言 >  >> Java 程式設計 >> Java 相關知識

Java 循環鏈結串列實作：單向循環與雙向循環完整指南

     編輯：Java 相關知識

循環鏈結串列核心特徵

  • 單向循環：尾節點 next 指向頭節點 (或虛擬頭節點)
  • 雙向循環：尾節點 next 指向頭節點，頭節點 prev 指向尾節點
  • 終止條件：遍歷時 curr.next == head 而非 curr == null
  • 應用：循環輪詢 (Round Robin)、音樂播放循環、Josephus 問題、緩衝區

統一介面 (承接上篇)

package list;

import java.util.Map;

public interface IListOps<T> {
    boolean insertNode(T node);
    boolean insertPosNode(int pos, T node);
    boolean deleteNode(int pos);
    boolean updateNode(int pos, Map<String, Object> data);
    T getNode(int pos, Map<String, Object> data);
    void printList();
    int getSize();
}

一、單向循環鏈結串列

節點類別 (沿用 SNode)

package list;

public class SNode {
    private String data;
    private SNode next;
    // getter/setter/toString 同前
}

核心實作

package list;

import java.util.HashMap;
import java.util.Map;

public class SinglyCircularList implements IListOps<SNode> {
    private final SNode head = new SNode("HEAD");
    private int size = 0;

    @Override public int getSize() { return size; }

    /** 初始化：頭節點指向自己 */
    private void init() {
        if (size == 0) head.setNext(head);
    }

    /** 尾部插入：找到尾節點 (next == head) */
    @Override
    public boolean insertNode(SNode node) {
        init();
        if (size == 0) {
            head.setNext(node);
            node.setNext(head); // 關鍵：指向頭節點形成循環
        } else {
            SNode curr = head;
            while (curr.getNext() != head) curr = curr.getNext(); // 找尾節點
            curr.setNext(node);
            node.setNext(head);
        }
        size++;
        return true;
    }

    /** 指定位置插入 (1-based) */
    @Override
    public boolean insertPosNode(int pos, SNode node) {
        init();
        if (pos <= 0 || pos > size + 1) return false;
        
        if (size == 0) { // 空串列
            head.setNext(node);
            node.setNext(head);
            size++;
            return true;
        }
        
        if (pos == size + 1) return insertNode(node); // 尾插
        
        // 找到第 pos-1 個節點 (前驅)
        SNode prev = head;
        for (int i = 1; i < pos; i++) prev = prev.getNext();
        
        node.setNext(prev.getNext());
        prev.setNext(node);
        size++;
        return true;
    }

    /** 指定位置刪除 */
    @Override
    public boolean deleteNode(int pos) {
        if (pos <= 0 || pos > size) return false;
        
        // 找到第 pos-1 個節點 (前驅)
        SNode prev = head;
        for (int i = 1; i < pos; i++) prev = prev.getNext();
        
        // 刪除 prev.next
        prev.setNext(prev.getNext().getNext());
        size--;
        System.gc();
        return true;
    }

    @Override
    public boolean updateNode(int pos, Map<String, Object> data) {
        SNode node = getNode(pos, null);
        if (node != null && data != null) {
            node.setData((String) data.get("data"));
            return true;
        }
        return false;
    }

    @Override
    public SNode getNode(int pos, Map<String, Object> data) {
        if (pos <= 0 || pos > size) return null;
        SNode curr = head.getNext();
        for (int i = 1; i < pos; i++) curr = curr.getNext();
        return curr;
    }

    @Override
    public void printList() {
        System.out.println("=== 單向循環鏈結串列 (長度: " + size + ") ===");
        if (size == 0) { System.out.println("空串列"); return; }
        
        SNode curr = head.getNext();
        int idx = 1;
        do {
            System.out.println("第 " + idx++ + " 節點: " + curr);
            curr = curr.getNext();
        } while (curr != head); // 關鍵：直到回到頭節點
    }

    public static void main(String[] args) {
        SinglyCircularList list = new SinglyCircularList();
        list.insertNode(new SNode("節點1"));
        list.insertNode(new SNode("節點2"));
        list.insertNode(new SNode("節點3"));
        list.insertPosNode(2, new SNode("插入節點"));
        list.printList();
        list.deleteNode(2);
        list.printList();
    }
}

二、雙向循環鏈結串列

節點類別 (沿用 DNode)

package list;

public class DNode {
    private DNode prev;
    private String data;
    private DNode next;
    // getter/setter/toString 同前
}

核心實作

package list;

import java.util.HashMap;
import java.util.Map;

public class DoublyCircularList implements IListOps<DNode> {
    private final DNode head = new DNode("HEAD");
    private int size = 0;

    @Override public int getSize() { return size; }

    /** 初始化：頭節點 prev/next 都指向自己 */
    private void init() {
        if (size == 0) {
            head.setNext(head);
            head.setPrev(head);
        }
    }

    @Override
    public boolean insertNode(DNode node) {
        init();
        if (size == 0) {
            head.setNext(node);
            head.setPrev(node);
            node.setNext(head);
            node.setPrev(head);
        } else {
            DNode tail = head.getPrev(); // 尾節點 = head.prev
            tail.setNext(node);
            node.setPrev(tail);
            node.setNext(head);
            head.setPrev(node);
        }
        size++;
        return true;
    }

    @Override
    public boolean insertPosNode(int pos, DNode node) {
        init();
        if (pos <= 0 || pos > size + 1) return false;
        
        if (size == 0) {
            head.setNext(node); head.setPrev(node);
            node.setNext(head); node.setPrev(head);
            size++; return true;
        }
        
        if (pos == size + 1) return insertNode(node);
        
        // 找到第 pos 個節點 (作為後繼節點)
        DNode curr = head.getNext();
        for (int i = 1; i < pos; i++) curr = curr.getNext();
        
        // 插入到 curr 之前
        DNode prev = curr.getPrev();
        prev.setNext(node);
        node.setPrev(prev);
        node.setNext(curr);
        curr.setPrev(node);
        size++;
        return true;
    }

    @Override
    public boolean deleteNode(int pos) {
        if (pos <= 0 || pos > size) return false;
        
        DNode curr = head.getNext();
        for (int i = 1; i < pos; i++) curr = curr.getNext();
        
        DNode prev = curr.getPrev();
        DNode next = curr.getNext();
        
        prev.setNext(next);
        next.setPrev(prev); // 雙向必須雙向斷開/連接
        
        size--;
        System.gc();
        return true;
    }

    @Override
    public boolean updateNode(int pos, Map<String, Object> data) {
        DNode node = getNode(pos, null);
        if (node != null && data != null) {
            node.setData((String) data.get("data"));
            return true;
        }
        return false;
    }

    @Override
    public DNode getNode(int pos, Map<String, Object> data) {
        if (pos <= 0 || pos > size) return null;
        DNode curr = head.getNext();
        for (int i = 1; i < pos; i++) curr = curr.getNext();
        return curr;
    }

    @Override
    public void printList() {
        System.out.println("=== 雙向循環鏈結串列 (長度: " + size + ") ===");
        if (size == 0) { System.out.println("空串列"); return; }
        
        DNode curr = head.getNext();
        int idx = 1;
        do {
            System.out.println("第 " + idx++ + " 節點: " + curr);
            curr = curr.getNext();
        } while (curr != head);
    }

    public static void main(String[] args) {
        DoublyCircularList list = new DoublyCircularList();
        list.insertPosNode(1, new DNode("節點1"));
        list.insertPosNode(2, new DNode("節點2"));
        list.insertPosNode(3, new DNode("節點3"));
        list.insertPosNode(2, new DNode("插入節點"));
        list.printList();
        list.deleteNode(2);
        list.printList();
    }
}

三、關鍵差異總結表

特性單向循環雙向循環
頭節點初始化head.next = headhead.next = head.prev = head
尾節點判斷curr.next == headcurr.next == head (或 head.prev == tail)
尾部插入遍歷找尾 O(n)head.getPrev() 直接得尾 O(1)
插入指標更新2 個 next4 個指標 (prev/next 對稱)
刪除指標更新1 個 next2 個指標 (prev.next, next.prev)
反向遍歷不可可 (curr = curr.prev)
Josephus 問題適用 (單向計數)適用 (雙向可雙向計數)

四、經典應用：Josephus 問題 (約瑟夫環)

/** 
 * N 個人圍圈，從第 1 個報數，報到 M 的人出列，繼續報數，求最後剩下誰
 * 單向循環鏈結串列完美模擬
 */
public class Josephus {
    public static int solve(int n, int m) {
        SinglyCircularList list = new SinglyCircularList();
        for (int i = 1; i <= n; i++) list.insertNode(new SNode(String.valueOf(i)));
        
        SNode curr = list.getNode(1, null); // 從第1個開始
        while (list.getSize() > 1) {
            // 移動 m-1 步 (當前已算1)
            for (int i = 1; i < m; i++) curr = curr.getNext();
            
            // 刪除當前節點：需要前驅節點
            // 單向循環無直接前驅，需從 head 找或維護 prev
            // 此處簡化：轉用索引刪除
            int pos = 1;
            SNode temp = list.getNode(1, null);
            while (temp != curr) { temp = temp.getNext(); pos++; }
            list.deleteNode(pos);
            
            // 下一輪從被刪節點的下一個開始
            curr = curr.getNext();
        }
        return Integer.parseInt(list.getNode(1, null).getData());
    }

    public static void main(String[] args) {
        System.out.println("Josephus(5,3) = " + solve(5, 3)); // 輸出 4
        System.out.println("Josephus(10,2) = " + solve(10, 2)); // 輸出 5
    }
}

五、音樂播放器循環播放模擬

public class MusicPlayer {
    private DoublyCircularList playlist = new DoublyCircularList();
    private DNode current = null;

    public void addSong(String name) {
        playlist.insertNode(new DNode(name));
        if (current == null) current = playlist.getNode(1, null);
    }

    public void playCurrent() {
        if (current != null) System.out.println("♪ 正在播放: " + current.getData());
    }

    public void next() {
        if (current != null) {
            current = current.getNext();
            if (current.getData().equals("HEAD")) current = current.getNext(); // 跳過頭節點
            playCurrent();
        }
    }

    public void prev() {
        if (current != null) {
            current = current.getPrev();
            if (current.getData().equals("HEAD")) current = current.getPrev();
            playCurrent();
        }
    }

    public static void main(String[] args) {
        MusicPlayer player = new MusicPlayer();
        player.addSong("歌曲A");
        player.addSong("歌曲B");
        player.addSong("歌曲C");
        player.playCurrent(); // ♪ 歌曲A
        player.next();        // ♪ 歌曲B
        player.next();        // ♪ 歌曲C
        player.next();        // ♪ 歌曲A (循環)
        player.prev();        // ♪ 歌曲C (倒轉)
    }
}

六、常見錯誤與調試技巧

  1. 死循環：遍歷終止條件寫錯 (如 curr != null 而非 curr != head)
  2. 斷環：插入/刪除未正確維護頭尾指標連接
  3. 頭節點資料洩漏：列印/遍歷時誤包含 HEAD 節點
  4. 空串列操作：未檢查 size == 0 直接操作指標
  5. 索引偏移：1-based 邏輯與 0-based 習慣混淆

調試輔助方法

/** 驗證循環完整性 */
public boolean validateCircular() {
    if (size == 0) return head.getNext() == head;
    
    int count = 0;
    Node curr = head.getNext();
    do {
        count++;
        if (count > size * 2) return false; // 防呆
        curr = curr.getNext();
    } while (curr != head);
    
    return count == size;
}

/** 列印指標結構 (除錯用) */
public void debugPrint() {
    Node curr = head;
    do {
        String prevData = curr.getPrev() != null ? curr.getPrev().getData() : "null";
        String nextData = curr.getNext() != null ? curr.getNext().getData() : "null";
        System.out.println("[" + curr.getData() + "] prev=" + prevData + ", next=" + nextData);
        curr = curr.getNext();
    } while (curr != head);
}

七、總結

  • 循環鏈結串列透過頭尾相連消除 null 邊界，簡化循環邏輯
  • 單向循環：結構輕量、適合單向循環遍歷 (Josephus、Round Robin)
  • 雙向循環：O(1) 尾部操作、支援雙向導航 (播放器、瀏覽器歷史)
  • 虛擬頭節點統一空/非空、頭/中/尾操作邏輯，強烈建議採用
  • 關鍵不變量：head.next == head (空) 或 head.prev.next == head (非空) 必須始終成立

掌握循環鏈結串列是理解作業系統排程、網路協議環形緩衝、遊戲邏輯循環等核心基礎，建議多手寫、多畫圖驗證指標變化。

  1. 上一篇文章：
  2. 下一篇文章：
Java 相關知識
SSH 整合筆記（三）：Hibernate 反向工程生成 DAO 並優化專案結構 SSH 整合筆記（三）：Hibernate 反向工程生成 DAO 並優化專案結構

繼完成 Spring 與 Hibernate 整合後，本篇將
Spring JMS 實戰：輕鬆構建企業級非同步訊息系統 Spring JMS 實戰：輕鬆構建企業級非同步訊息系統

為什麼需要非同步訊息？ 在 SOA 架構中，許多業務流程本質
JBoss Seam 學習系列三：JBoss Tools 產生首個 Seam 專案與 CRUD 實戰 JBoss Seam 學習系列三：JBoss Tools 產生首個 Seam 專案與 CRUD 實戰

使用 JBoss Tools 快速產生 Seam 專案與資料
C# 圖片任意多邊形裁剪算法實現 (含完整 WinForms 示例) C# 圖片任意多邊形裁剪算法實現 (含完整 WinForms 示例)

項目背景 本文提供一個完整的 C# WinForms 示例，
Java 管道流（PipedInputStream/PipedOutputStream）實現線程間通訊完整指南 Java 實作鏈結串列與雙向鏈結串列：以物件參考替代指標的優雅實現 Java 實現二維碼與背景圖片合成 Java WebService 文件上傳下載完整實現（Base64 編碼） 微信小程序藍牙BLE開發完整實戰指南 Java 日期時間處理完全指南：Date、Calendar 與新時代 java.time 實戰 Struts 2 迭代異構對象集合：s:iterator 進階技巧
欄目導航
  • Java 程式設計入門
  • Java 相關知識
  • J2EE
  • J2SE
  • J2ME
  • Java 綜合教學
    • Copyright © 程式碼之家 All Rights Reserved