データ構造:linklist

3404 ワード
整理する テキストリンク
Let codeのlink list章を勉強し理解します.

1. Intro:

  • Sigely Linked listは、valueフィールドとreferenceフィールド(次のノードを指す)を有する構造である.
    • struct SinglyListNode{
	int val;
    SinglyListNode* next;
    SinglyListNode(int x) : val(x), next(NULL){}
};
  • の配列とは異なり、要素にランダムにアクセスできません.i-th要素にアクセスするにはheadノードから巡回する必要があるため,平均O(N)時間が必要である.(Nはlinklistのlength)
    • なぜ
  • を使うのかと聞けば、以下に紹介するinsertとdeleteで知ることができます.

    • 2. Add operation


    prevとnextの間にcurrというノードを挿入したい.

    次の図に示します.

  • Currの「next」フィールドはprevの「next」nextノードに関連付けられている.


  • 次にprevの「next」をcurrに指さすとよい.


  • 挿入点の後ろのすべての要素の配列を移動する必要があるのとは異なり,チェーンテーブルのO(1)時間の複雑さは挿入問題を解決することができる.

    • Delete operation


    prevとnextの間のcurrを削除したいです.
  • を削除するcurrノードの前のprevを検索します.
  • とprevの「next」をcurrの次のノードnextに接続します.
  • を削除するノードのprevを検索する必要があるため,時間的複雑度はO(N)である.
  • 空間複雑度O(1)

    • コード#コード#

    class MyLinkedList {
private:
    struct SinglyListNode {
        int val;
        SinglyListNode* next;
        SinglyListNode(int x) : val(x), next(NULL){}
    };
    
    SinglyListNode* head;
public:
    
    MyLinkedList() {
        head = NULL;
    }
    
    SinglyListNode* getNode(int index){
        SinglyListNode* curr = head;
        for(int i = 0; i < index && curr; i++){
            curr = curr->next;
        }
        return curr;
    }
    
    int get(int index) {
        SinglyListNode* curr = getNode(index);
        return curr? curr->val : -1;
    }
    
    void addAtHead(int val) {
        SinglyListNode* curr = new SinglyListNode(val);
        curr->next = head;
        head = curr;
        return;
    }
    
    void addAtTail(int val) {
        if(head==NULL){
            addAtHead(val);
            return;
        }
        
        SinglyListNode* curr = new SinglyListNode(val);
        SinglyListNode* tail = head;
        while(tail && tail->next){
            tail = tail->next;
        }
        tail->next = curr;
        return;
    }
    
    void addAtIndex(int index, int val) {
        if(index == 0){
            addAtHead(val);
            return;
        }
        
        //index범위가 유효한지 체크
        SinglyListNode* prev = getNode(index-1);
        if(!prev) return;
        
        SinglyListNode* curr = new SinglyListNode(val);
        curr->next = prev->next;
        prev->next = curr;
    }
    
    void deleteAtIndex(int index) {
        SinglyListNode* curr = getNode(index);
        if(curr == NULL) return;
        
        if(index==0){
            head = curr->next;
        }else{
            SinglyListNode* prev = getNode(index-1);
            prev->next = curr->next;
        }
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */
    百準14003成長最長の部分数列5
    プリンタ