快捷導航

Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之環(huán)形鏈表

更新時間：2022年02月18日 10:49:44 作者：我是小白呀

無論是靜態(tài)鏈表還是動態(tài)鏈表,有時在解決具體問題時,需要我們對其結(jié)構(gòu)進行稍微地調(diào)整。比如,可以把鏈表的兩頭連接,使其成為了一個環(huán)狀鏈表,通常稱為循環(huán)鏈表

概述

從今天開始, 小白我將帶大家開啟 Java 數(shù)據(jù)結(jié)構(gòu) & 算法的新篇章.

鏈表

鏈表 (Linked List) 是一種遞歸的動態(tài)數(shù)據(jù)結(jié)構(gòu). 鏈表以線性表的形式, 在每一個節(jié)點存放下一個節(jié)點的指針. 鏈表解決了數(shù)組需要先知道數(shù)據(jù)大小的缺點, 增加了節(jié)點的指針域, 空間開銷較大.

鏈表包括三類:

單向鏈表
雙向鏈表
循環(huán)鏈表

環(huán)形鏈表

環(huán)形鏈表 (Circular Linked List) 將單鏈表最后一個節(jié)點指向頭節(jié)點, 即為環(huán)形鏈表. 如圖:

環(huán)形鏈表實現(xiàn)

Node 類

// Node類
private class Node<E> {

    public E e;  // 元素
    private Node next;  // 下一個節(jié)點

    // 構(gòu)造
    public Node(E e) {
        this.e = e;
        this.next = null;
    }

    @Override
    public String toString() {
        return e.toString();
    }
}

insert 方法

// 插入數(shù)據(jù)
public void insert(E e) {

    // 創(chuàng)建節(jié)點
    Node node = new Node(e);

    if (size == 0) {
        head = node;
        head.next = head;
        tail = head;
    } else {
        tail.next = node;
        node.next = tail;
        tail = node;
    }

    size ++;
}

remove 方法

// 刪除元素
public void remove(int index) {

    // 檢查索引是否越界
    if (index < 0 || index > size) {
        throw new RuntimeException("Invalid Index");
    }

    // 獲取index前一個節(jié)點
    Node prev = head;
    for (int i = 0; i < index - 1; i++) {
        prev = prev.next;
    }

    // 刪除數(shù)據(jù)
    Node retNode = prev.next;
    prev.next = retNode.next;

    size --;
}

main

// main
public static void main(String[] args) {

    // 創(chuàng)建循環(huán)鏈表
    CircularLinkedList<Integer> circularLinkedList = new CircularLinkedList<>();

    // 插入
    for (int i = 0; i < 5; i++) {
        circularLinkedList.insert(i);
        System.out.println(circularLinkedList);
    }

    // 刪除
    for (int i = 0; i < 2; i++) {
        circularLinkedList.remove(0);
        System.out.println(circularLinkedList);
    }
}

輸出結(jié)果:

0
0->1
0->1->2
0->1->2->3
0->1->2->3->4
0->2->3->4
0->3->4

完整代碼

public class CircularLinkedList<E> {

    // Node類
    private class Node<E> {

        public E e;  // 元素
        private Node next;  // 下一個節(jié)點

        // 構(gòu)造
        public Node(E e) {
            this.e = e;
            this.next = null;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    // 頭節(jié)點和尾節(jié)點
    private Node head = null;
    private Node tail = null;
    private int size;  // 鏈表大小

    // 構(gòu)造函數(shù)
    public CircularLinkedList() {
        head = new Node(null);
        size = 0;
    }

    // 插入數(shù)據(jù)
    public void insert(E e) {

        // 創(chuàng)建節(jié)點
        Node node = new Node(e);

        if (size == 0) {
            head = node;
            head.next = head;
            tail = head;
        } else {
            tail.next = node;
            node.next = tail;
            tail = node;
        }

        size ++;
    }

    // 刪除元素
    public void remove(int index) {

        // 檢查索引是否越界
        if (index < 0 || index > size) {
            throw new RuntimeException("Invalid Index");
        }

        // 獲取index前一個節(jié)點
        Node prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }

        // 刪除數(shù)據(jù)
        Node retNode = prev.next;
        prev.next = retNode.next;

        size --;
    }

    // 鏈表是否為空
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {

        StringBuilder builder = new StringBuilder();
        Node cur = head;
        while (cur != tail) {
            builder.append(cur + "->");
            cur = cur.next;
        }
        builder.append(cur);

        return builder.toString();
    }

    // main
    public static void main(String[] args) {

        // 創(chuàng)建循環(huán)鏈表
        CircularLinkedList<Integer> circularLinkedList = new CircularLinkedList<>();

        // 插入
        for (int i = 0; i < 5; i++) {
            circularLinkedList.insert(i);
            System.out.println(circularLinkedList);
        }

        // 刪除
        for (int i = 0; i < 2; i++) {
            circularLinkedList.remove(0);
            System.out.println(circularLinkedList);
        }
    }
}

到此這篇關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之環(huán)形鏈表的文章就介紹到這了,更多相關(guān)Java 環(huán)形鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: