欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java?數(shù)據(jù)結(jié)構(gòu)與算法系列精講之單向鏈表

 更新時間:2022年02月18日 10:59:12   作者:我是小白呀  
單向鏈表特點是鏈表的鏈接方向是單向的,訪問要通過順序讀取從頭部開始。鏈表是使用指針構(gòu)造的列表,是由一個個結(jié)點組裝起來的,又稱為結(jié)點列表。其中每個結(jié)點都有指針成員變量指向列表中的下一個結(jié)點,head指針指向第一個結(jié)點稱為表頭,而終止于最后一個指向nuLL的指針

概述

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

鏈表

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

鏈表包括三類:

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

單向鏈表

單向鏈表 (Single Linked List) 是鏈表中最簡單的一種形式. 單向鏈表每個節(jié)點包含兩個部分, 第一部分是信息, 第二部分是下一個節(jié)點. (元素 + 指針)

單向鏈表實現(xiàn)

Node 類

// Node類
private class Node {


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

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

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

add 方法

// 添加數(shù)據(jù)
public void add(int index, E e) {

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

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

    // 添加數(shù)據(jù)
    SingleLinkedList.Node node = new SingleLinkedList.Node(e);
    node.next = prev.next;
    prev.next = node;
    size++;
}

remove 方法

// 刪除數(shù)據(jù)
public void remove(int index) {

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

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

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

    size --;
}

get 方法

// 通過索引獲取鏈表數(shù)數(shù)據(jù)
public E get(int index) {

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

    // 獲取index前一個節(jié)點
    Node cur = dummyHead.next;
    for (int i = 0; i < index; i++) {
        cur = cur.next;
    }
    
    return cur.e;
}

set 方法

// 通過索引設(shè)置鏈表數(shù)據(jù)
public E set(int index,E e) {

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

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

    // 設(shè)置新值
    cur.e = e;

   return cur.e;
}

contain 方法

// 鏈表是否包含元素
public boolean contains(E e) {
        Node cur = dummyHead.next;

        // 遍歷所有節(jié)點
        while (cur != null) {
            if (cur.e.equals(e)) {
                return true;
            }
            cur = cur.next;
        }
    return false;
}

main

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

    // 創(chuàng)建單向鏈表
    SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>();

    // 添加數(shù)據(jù)
    for (int i = 0; i < 8; i++) {
        singleLinkedList.addFirst(i);
        System.out.println(singleLinkedList);
    }

    // 是否包含元素
    System.out.println(singleLinkedList.contains(0));
    System.out.println(singleLinkedList.contains(10));

    // set
    singleLinkedList.set(0, 9);
    singleLinkedList.set(1, 7);
    System.out.println(singleLinkedList);

    // 刪除數(shù)據(jù)
    for (int i = 0; i < 8; i++) {
        singleLinkedList.remove(0);
        System.out.println(singleLinkedList);
    }
}

輸出結(jié)果:

0->NULL
1->0->NULL
2->1->0->NULL
3->2->1->0->NULL
4->3->2->1->0->NULL
5->4->3->2->1->0->NULL
6->5->4->3->2->1->0->NULL
7->6->5->4->3->2->1->0->NULL
true
false
9->7->5->4->3->2->1->0->NULL
7->5->4->3->2->1->0->NULL
5->4->3->2->1->0->NULL
4->3->2->1->0->NULL
3->2->1->0->NULL
2->1->0->NULL
1->0->NULL
0->NULL
NULL

完整代碼

public class SingleLinkedList<E> {


    private Node dummyHead;  // 頭指針
    private int size;  // 鏈表大小

    // Node類
    private class Node {


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

    // 構(gòu)造
    public SingleLinkedList() {
        dummyHead = new Node(null);
        size = 0;
    }

    // 表首添加元素
    public void addFirst(E e) {
        add(0, e);
    }

    // 表尾添加元素
    public void addLast(E e){
        add(size, e);
    }

    // 添加數(shù)據(jù)
    public void add(int index, E e) {

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

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

        // 添加數(shù)據(jù)
        Node node = new Node(e);
        node.next = prev.next;
        prev.next = node;
        size ++;
    }

    // 刪除數(shù)據(jù)
    public void remove(int index) {

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

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

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

        size --;
    }


    // 通過索引獲取鏈表數(shù)數(shù)據(jù)
    public E get(int index) {

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

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

        return cur.e;
    }

    // 通過索引設(shè)置鏈表數(shù)據(jù)
    public E set(int index,E e) {

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

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

        // 設(shè)置新值
        cur.e = e;

        return cur.e;
    }

    // 鏈表是否包含元素
    public boolean contains(E e) {
        Node cur = dummyHead.next;

        // 遍歷所有節(jié)點
        while (cur != null) {
            if (cur.e.equals(e)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    // 獲取鏈表大小
    public int getSize() {
        return size;
    }

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

    @Override
    public String toString() {

        StringBuilder builder = new StringBuilder();
        Node cur = dummyHead.next;
        while (cur != null) {
            builder.append(cur + "->");
            cur = cur.next;
        }
        builder.append("NULL");
        return builder.toString();
    }

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

        // 創(chuàng)建單向鏈表
        SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>();

        // 添加數(shù)據(jù)
        for (int i = 0; i < 8; i++) {
            singleLinkedList.addFirst(i);
            System.out.println(singleLinkedList);
        }

        // 是否包含元素
        System.out.println(singleLinkedList.contains(0));
        System.out.println(singleLinkedList.contains(10));

        // set
        singleLinkedList.set(0, 9);
        singleLinkedList.set(1, 7);
        System.out.println(singleLinkedList);

        // 刪除數(shù)據(jù)
        for (int i = 0; i < 8; i++) {
            singleLinkedList.remove(0);
            System.out.println(singleLinkedList);
        }
    }
}

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

相關(guān)文章

  • SpringBoot發(fā)送郵箱驗證碼功能

    SpringBoot發(fā)送郵箱驗證碼功能

    這篇文章主要介紹了SpringBoot發(fā)送郵箱驗證碼功能,非常不錯,具有一定的參考借鑒價值,需要的朋友可以參考下
    2019-09-09
  • Java Clone(類的復(fù)制)實例代碼

    Java Clone(類的復(fù)制)實例代碼

    Java Clone(類的復(fù)制)實例代碼,需要的朋友可以參考一下
    2013-03-03
  • 淺談Java中的參數(shù)傳遞問題

    淺談Java中的參數(shù)傳遞問題

    這篇文章主要介紹了Java中的參數(shù)傳遞問題,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-04-04
  • java語法糖之jdk迭代的新特性匯總

    java語法糖之jdk迭代的新特性匯總

    什么是語法糖?泛型、自動裝箱拆箱、變長參數(shù)、增強for循環(huán)、switch字符類型、lambda表達(dá)式等,這些其實都是語法糖。這篇文章主要給大家介紹了關(guān)于java語法糖之jdk迭代的新特性的相關(guān)資料,需要的朋友可以參考下
    2021-05-05
  • Java 并發(fā)編程中如何創(chuàng)建線程

    Java 并發(fā)編程中如何創(chuàng)建線程

    這篇文章主要介紹了Java 并發(fā)編程中如何創(chuàng)建線程,幫助大家更好的理解和學(xué)習(xí)使用Java,感興趣的朋友可以了解下
    2021-03-03
  • SpringCloud環(huán)境搭建過程之Rest使用小結(jié)

    SpringCloud環(huán)境搭建過程之Rest使用小結(jié)

    這篇文章主要介紹了SpringCloud環(huán)境搭建之Rest使用,本文通過實例代碼圖文相結(jié)合給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2022-08-08
  • 詳解Java類動態(tài)加載和熱替換

    詳解Java類動態(tài)加載和熱替換

    本文主要介紹類加載器、自定義類加載器及類的加載和卸載等內(nèi)容,并舉例介紹了Java類的熱替換。
    2021-05-05
  • IDEA使用SequenceDiagram插件繪制時序圖的方法

    IDEA使用SequenceDiagram插件繪制時序圖的方法

    這篇文章主要介紹了IDEA使用SequenceDiagram插件繪制時序圖的方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-09-09
  • Spring MVC溫故而知新系列教程之請求映射RequestMapping注解

    Spring MVC溫故而知新系列教程之請求映射RequestMapping注解

    這篇文章主要介紹了Spring MVC溫故而知新系列教程之請求映射RequestMapping注解的相關(guān)知識,文中給大家介紹了RequestMapping注解提供的幾個屬性及注解說明,感興趣的朋友跟隨腳本之家小編一起學(xué)習(xí)吧
    2018-05-05
  • springboot整合mongodb使用詳解

    springboot整合mongodb使用詳解

    MongoDB是一個文檔數(shù)據(jù)庫(以?JSON?為數(shù)據(jù)模型),由C++語言編寫,旨在為WEB應(yīng)用提供可擴展的高性能數(shù)據(jù)存儲解決方案,本文就給大家介紹一下詳細(xì)介紹一下springboot整合mongodb使用,需要的朋友可以參考下
    2023-07-07

最新評論