Javaを使用して一方向チェーンテーブルを実装し、チェーンテーブルの反転を完了します.

Javaを使用して一方向チェーンテーブルを実装し、チェーンテーブルの反転を完了します.
アルゴリズムとデータ構造はプログラマーが逃れられない壁であるため,余暇を利用して基礎的なアルゴリズムとデータ構造を学習し始める.ここでは、簡単な単一チェーンテーブルを実現する過程を記録します.間違いがあれば、ご指摘ください.
ニーズの明確化
Javaでは、よく使われるデータコンテナの中で、チェーンテーブルと密接な関係にあるのはLinkedListで、その下層は双方向チェーンテーブルとして実現され、ここではそれを参照物として、自分の簡単な一方向チェーンテーブルを実現します.また,添削,サイズ取得などの機能もサポートする必要がある.以下に示すように,まず,添削改ざん手法がサポートする範囲を定義した.

    /**
     *       
     * add(index, E)        index >= 0 && index <= size
     * remove(index)        index >= 0 && index < size
     * set(index, E)        index >= 0 && index < size
     * get(index)           index >= 0 && index < size
     */

チェーンテーブルノードの定義
ノードの定義は簡単ですが、ここでは単純化のため汎用型はサポートされず、ノードに格納されるデータ型はintに固定されています.

    private static class Node {
        private int item;
        private Node next;

        public Node(int item, Node next) {
            this.item = item;
            this.next = next;
        }

        public void setItem(int item) {
            this.item = item;
        }

        @Override
        public String toString() {
            return String.valueOf(this.item);
        }
    }

補助メソッドの定義
一方向チェーンテーブルである以上、コンテナにはfirst参照を持つだけでよく、last参照は必要ありません.チェーンテーブルのサイズを表すsizeを定義する必要があります.また、テスト結果の表示を容易にするために、toStringメソッドを書き直します.コードは次のとおりです.

public class SingleLinkedList {

    private int size = 0;
    private Node first = null;
    ...
}

    /**
     *         。
     * @return
     */
    public int getSize() {
        return size;
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (first != null) {
            Node curr = first;
            while (curr != null) {
                sb.append(String.valueOf(curr));
                if (curr.next != null) {
                    sb.append(",").append(" ");
                }
                curr = curr.next;
            }
        }
        sb.append("]");
        return sb.toString();
    }

クエリーメソッドgetの定義(index)
既存のデータでデータを取得するのは最も簡単で、これは最も簡単で、一方向チェーンテーブルコンテナには最初のノードfirst参照しか格納されていないため、直接角標indexで取得することはできません.firstから角標に基づいて順次遍歴する必要があります.コードは以下の通りです.

    /**
     *         。
     *
     * @param index
     * @return
     */
    public Node get(int index) {
        checkElementIndex(index);

        Node x = first;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }

追加メソッドadd(index,value)の定義
他の3つのグループの方法(取得、修正、削除)とは異なり、追加方法はチェーンテーブルの既存のデータ範囲だけでなく、角がsizeと表記された位置もサポートする必要があります.現在の位置にノードを挿入するには、前のノードを取得し、前のノードのnextが新しいノードを指し、新しいノードのnextがその位置の元のノードを指す必要があります.いくつかの特殊な状況の処理に注意し、sizeの数値が増加したことを忘れないでください.コードは次のとおりです.

    /**
     *     index       
     *
     * @param index
     * @param value
     * @return
     */
    public boolean add(int index, int value) {
        checkPositionIndex(index);

        if (index == 0) {
            if (first == null) {
                first = new Node(value, null);
            } else {
                Node next = get(0);
                Node node = new Node(value, next);
                first = node;
            }
        } else {
            Node prev = get(index - 1);
            Node node = new Node(value, prev.next);
            prev.next = node;
        }
        size++;
        return true;
    }

修正方法set(index,value)の定義
修正方法も簡単で、すでに存在するノードを角標に基づいて取得し、ノードに格納されているデータを修正するだけで、コードは以下の通りです.

    public boolean set(int index, int value) {
        checkElementIndex(index);
        Node node = get(index);
        node.setItem(value);
        return true;
    }

削除メソッドremove(index)の定義
現在位置のノードを削除します.コアは、前のノードのnextを現在位置の次のノードに向けることです.追加方法と同様に、極端な処理を行う必要があります.コードは以下の通りです.

    public boolean remove(int index) {
        checkElementIndex(index);

        // size > 0
        if (getSize() == 1) {//size == 1
            first = null;
        } else {// size > 1
            if (index == 0) {//        
                first = first.next;
            } else if (getSize() - 1 == index) {//         
                Node prev = get(index - 1);
                prev.next = null;
            } else {//        
                get(index - 1).next = get(index).next;
            }
        }
        size--;
        return true;
    }

チェーンテーブルの反転を実現
一方向チェーンテーブルの反転を実現するために,遍歴中に各ノードのnextを前のノードに向ける.コードは次のとおりです.

    /**
     *     
     *
     * @return
     */
    public Node reverseList() {
        Node prev = null;
        Node curr = first;
        while (curr != null) {
            Node temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        logFromHead("reverseList", prev);
        return prev;
    }

完全なコードは
プロジェクトでSingleLinkedListを検索すればよい.githubトランスミッションゲートhttps://github.com/tinyvampirepudge/DataStructureDemo
giteeトランスミッションゲートhttps://gitee.com/tinytongtong/DataStructureDemo
リファレンス
https://leetcode.com/problems/reverse-linked-list/description/