자료구조: linked list

Leet code의 linked list 챕터를 공부하고 이해를 위해 작성하였다.

1. Intro:

• Singly linked list는 value와 reference field(다음 노드를 가리킴)를 가지고 있는 구조이다.

struct SinglyListNode{
	int val;
    SinglyListNode* next;
    SinglyListNode(int x) : val(x), next(NULL){}
};

• 배열과는 다르게 element에 random하게 접근할 수는 없다. i-th element에 접근하고 싶다면 head node부터 시작하여 순회해야 하므로 average O(N) time이 걸린다. (N은 linked list의 length)
• 그럼에도 왜 사용하냐 묻는다면 다음에 설명된 insert와 delete를 보면 알 수 있다.

2. Add operation

prev와 next사이에 curr이라는 node를 끼워 넣고 싶다하자.

아래 이미지와 같이

• curr의 "next" field를 prev의 "next"인 next node와 연결해준다.
  

• 그리고나서 prev의 "next"는 curr를 가리키게 하면 된다.
  

• insert되는 지점의 뒤쪽에 위치한 모든 element를 다 움직여야하는 array와는 다르게 linked list는 O(1) time complexity로 insertion을 해결할 수 있다.

Delete operation

prev와 next사이에 있는 curr을 삭제하고 싶다하자.

• 삭제하려는 curr노드의 이전인 prev를 찾는다.
• 그리고 prev의 "next"를 curr의 다음 노드인 next와 이어준다.
  
• 삭제하려는 node의 prev를 찾아야하기 때문에 time complexity는 O(N)이다.
• space complexity는 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);
 */