腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

軟件下載

android MAC 驅(qū)動(dòng)下載字體下載 DLL

源碼下載

PHP ASP.NET ASP JSP

軟件編程

C# JAVA C 語言 Delphi Android

網(wǎng)絡(luò)編程

PHP ASP.NET ASP JavaScript

在線工具

CSS格式化 JS格式化 Html轉(zhuǎn)化為Js

數(shù)據(jù)庫

MYSQL MSSQL oracle DB2 MARIADB

CMS

PHPCMS DEDECMS 帝國CMS WordPress

常用工具

PHP開發(fā)工具 python Photoshop 必備軟件

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

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

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

概述

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

鏈表

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

鏈表包括三類:

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

環(huán)形鏈表

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

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

Node 類

// Node類
private class Node<E> {

    public E e;  // 元素
    private Node next;  // 下一個(gè)節(jié)點(diǎn)

    // 構(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é)點(diǎn)
    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前一個(gè)節(jié)點(diǎn)
    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;  // 下一個(gè)節(jié)點(diǎn)

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

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

    // 頭節(jié)點(diǎn)和尾節(jié)點(diǎn)
    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é)點(diǎn)
        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前一個(gè)節(jié)點(diǎn)
        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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: