Java 資料結構與演算法系列精講之單向連結串列

2022-02-18 13:04:30

概述

從今天開始, 小白我將帶大家開啟 Jave 資料結構 & 演演算法的新篇章.

連結串列

連結串列 (Linked List) 是一種遞迴的動態資料結構. 連結串列以線性表的形式, 在每一個節點存放下一個節點的指標. 連結串列解決了陣列需要先知道資料大小的缺點, 增加了節點的指標域, 空間開銷較大.

連結串列包括三類:

單向連結串列
雙向連結串列
迴圈連結串列

單向連結串列

單向連結串列 (Single Linked List) 是連結串列中最簡單的一種形式. 單向連結串列每個節點包含兩個部分, 第一部分是資訊, 第二部分是下一個節點. (元素 + 指標)

單向連結串列實現

Node 類

// Node類
private class Node {


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

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

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

add 方法

// 新增資料
public void add(int index, E e) {

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

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

    // 新增資料
    SingleLinkedList.Node node = new SingleLinkedList.Node(e);
    node.next = prev.next;
    prev.next = node;
    size++;
}

remove 方法

// 刪除資料
public void remove(int index) {

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

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

    // 刪除資料
    Node retNode = prev.next;
    prev.next = retNode.next;

    size --;
}

get 方法

// 通過索引獲取連結串列數資料
public E get(int index) {

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

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

set 方法

// 通過索引設定連結串列資料
public E set(int index,E e) {

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

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

    // 設定新值
    cur.e = e;

   return cur.e;
}

contain 方法

// 連結串列是否包含元素
public boolean contains(E e) {
        Node cur = dummyHead.next;

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

main

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

    // 建立單向連結串列
    SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>();

    // 新增資料
    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);

    // 刪除資料
    for (int i = 0; i < 8; i++) {
        singleLinkedList.remove(0);
        System.out.println(singleLinkedList);
    }
}

輸出結果:

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;  // 下一個節點

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

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

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

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

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

    // 新增資料
    public void add(int index, E e) {

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

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

        // 新增資料
        Node node = new Node(e);
        node.next = prev.next;
        prev.next = node;
        size ++;
    }

    // 刪除資料
    public void remove(int index) {

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

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

        // 刪除資料
        Node retNode = prev.next;
        prev.next = retNode.next;

        size --;
    }


    // 通過索引獲取連結串列數資料
    public E get(int index) {

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

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

        return cur.e;
    }

    // 通過索引設定連結串列資料
    public E set(int index,E e) {

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

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

        // 設定新值
        cur.e = e;

        return cur.e;
    }

    // 連結串列是否包含元素
    public boolean contains(E e) {
        Node cur = dummyHead.next;

        // 遍歷所有節點
        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) {

        // 建立單向連結串列
        SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>();

        // 新增資料
        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);

        // 刪除資料
        for (int i = 0; i < 8; i++) {
            singleLinkedList.remove(0);
            System.out.println(singleLinkedList);
        }
    }
}

到此這篇關於Java 資料結構與演算法系列精講之單向連結串列的文章就介紹到這了,更多相關Java 單向連結串列內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！