データ構造接続リスト

接続リスト

順次接続されたノードを表すデータ構造.

画像ソース:https://freestrokes.tistory.com/84
ノード:値と次のノードアドレスを指すポインタで構成されます.

Headノードが指すノードは最初のノードです

ノードのポインタがnullの場合、ノードは最後のノードです.

コンテキストの使用

大量のデータの挿入と削除が必要

接続リスト>アレイ

大量のデータ・クエリーが必要

シナリオ>接続リスト

単一接続リストの実装

Java

public class SingleLinkedList {

    private Node head;
    private int size;

    SingleLinkedList() {
        head = new Node();
        size = 0;
    }

    private class Node {
        public Node next;
        private Object data;

        public Node(Object data) {
            this.data = data;
            this.next = null;
        }
        public Node() {}
    }

    // 첫번째 노드에 새 노드 연결
    public void add2Head(Object data) {
        Node newNode = new Node(data);

        newNode.next = head.next;
        head.next = newNode;

        size++;
    }

    // 마지막 노드에 새 노드 연결
    public void add2Tail(Object data) {

        Node newNode = new Node(data);
        Node now = head;

        // 데이터 순회
        while (now.next != null) {
            now = now.next;
        }
        now.next = newNode;

        size++;
    }

    // 특정 위치에 새 노드 삽입
    public void insert(int idx, Object data) {
        int i = 1;
        Node newNode = new Node(data);
        Node now = head;

        while (i < idx) {
            now = now.next;
            i++;
        }
        newNode.next = now.next;
        now.next = newNode;
    }

    // 특정 위치 노드 삭제
    public Object delete(int idx) {
        int i = 1;
        Object data;

        Node now = head;
        Node removedNode;

        while (i < idx) {
            now = now.next;
            i++;
        }
        removedNode = now.next;
        now.next = removedNode.next;

        data = removedNode.data;

        removedNode = null;

        System.out.println(idx + "번째 데이터, "+ data + " 삭제됐습니당 ");

        return data;
    }

    // 연결리스트 전체 출력
    public void printNodes() {
        Node now = head;

        if (head.next == null) {
            System.out.println("저장된 데이터가 없습니다.");
        }

        while (now.next != null) {
            System.out.println(now.next.data);
            now = now.next;
        }
    }   
}

接続リストのタイプ

単純接続リスト
H(句読点)→[]→[]→[]→[]
欠点:なくすかもしれなくて、私の前が谁なことを知りません

Win接続リスト
H(ヘッダ点)→[]→[]→[]→H(最後にヘッダ点を指す)

利点:紛失を防止し、前に進むと私の前に誰がいるかがわかります.
欠点:接続が切断された場合、フロントエンドが見つからない可能性があります.

デュアル接続リスト

の利点:2つのポインタ(前後)が接続され、ナビゲーションで効率が高い

欠点:実現しにくい.

結論
円形、二層リストは簡単にナビゲートできますが、なかなか実現できません.だから簡単にリストに接続したほうがいいです.