データ構造学習ノート——単鎖表

チェーンテーブルの紹介

チェーンテーブル(linked list)は、物理的に非連続で非順序のデータ構造であり、いくつかのノード(node)からなる

である.

単一チェーンテーブルの各ノードは、データを格納変数data、2は次のノードを指すポインタnext

を格納する2つの部分を含む.

双方向チェーンテーブル各ノードは3つの部分を含み、単一チェーンテーブルに基づいて前置ノードを指すprevポインタ

が1つ増えた.

チェーンテーブルの最初のノードはヘッダノードと呼ばれ、最後のノードはテールノードと呼ばれ、テールノードのnextポインタはnull

を指す.

チェーンテーブルのメモリにおける記憶方式は、ランダム記憶

である.
時間の複雑さ

挿入は考慮せず,削除操作前の検索要素のプロセスは挿入と削除のみを考慮し,時間的複雑度はO(1)

である.

チェーンテーブルの検索は先頭ノードから始まり,チェーンテーブルの長さが大きいほど検索時間が長くなり,時間複雑度はO(n)

である.
配列とチェーンテーブルの比較
配列の利点は要素の迅速な位置決めにあり、読み取り操作が多く、書き込み操作が少ないシーンでは、配列がチェーンテーブルに適している利点は、要素の迅速な挿入と削除操作にあり、末尾で要素の削除と挿入が頻繁であれば、チェーンテーブルを使用するとより良い
シングルチェーンテーブルdemo

package com.cc.node;

public class NodeDemo1 {
    //   ，         
    private static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    private Node head;
    private Node last;
    //       
    private int size;

    /**
     *       
     *
     * @param index
     * @param data
     * @throws Exception
     */
    public void insert(int index, int data) throws Exception {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("         ");
        }
        Node insertNode = new Node(data);
        //   
        if (size == 0) {
            head = insertNode;
            last = insertNode;
        } else if (index == 0) {
            //    
            //    ：1.     next     head  ，2.            
            insertNode.next = head;
            head = insertNode;
        } else if (index > 0 && index < size - 1) {
            //    
            //   ：1.     next           ，2.          next       
            Node prevNode = getNode(index - 1);//    
            insertNode.next = prevNode.next;//            
            prevNode.next = insertNode;//         

        } else {
            //    
            //   ，1.       next       ，2.          
            last.next = insertNode;
            last = insertNode;
        }
        //      1
        size++;
    }

    /**
     *             
     *
     * @param index
     * @throws Exception
     */
    public void deleteNode(int index) throws Exception {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("         ");
        }
        Node deleteNode = null;
        if (index == 0) {
            //      
            //              next     
            head = head.next;
        } else if (index > 0 && index < size - 1) {
            //       
            //          ，              
            Node prevNode = getNode(index - 1);
            prevNode.next = prevNode.next.next;
        } else {
            //      
            //          ,1.       next   ，2.            
            Node prevNode = getNode(index - 1);
            prevNode.next = null;
            last = prevNode;
        }
        size--;
    }

    /**
     *             
     *
     * @param index
     * @return
     * @throws Exception
     */
    public Node getNode(int index) throws Exception {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("         ");
        }
        //           
        Node temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     *           
     */
    public void outList() {
        Node temp = head;
        for (int i = 0; i < size; i++) {
            System.out.println(temp.data);
            temp = temp.next;
        }
    }

    public static void main(String[] args) throws Exception {
        NodeDemo1 linkedlist = new NodeDemo1();
        linkedlist.insert(0, 1);
        linkedlist.insert(1, 2);
        linkedlist.insert(2, 3);
        linkedlist.insert(3, 4);
        linkedlist.insert(4, 5);
        linkedlist.insert(5, 6);
        linkedlist.outList();
        linkedlist.deleteNode(5);
        linkedlist.outList();


    }
}