[알고리즘👽] 13. 단일 연결 리스트(2)

단일 연결 리스트 : get 메소드 소개

Get

인덱스 혹은 위치를 의미하는 숫자를 인자로 받아서 주어진 위치에 있는 노드를 반환하는 메소드입니다.

의사코드

• 인자로 index를 받는다.
• 인덱스가 음수이거나 혹은 리스트의 길이보다 같거나 클 경우 동작할 수 없습니다. 이 경우 null을 반환한다.
• loop를 통해 인덱스가 지정하는 위치에 이를 때까지 반복해서 이동한 다음 해당 인덱스 위치에 있는 노드를 반환한다.

솔루션

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList {
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    get(index) {
        if(index < 0 || index >= this.lenght) return null;
        var counter = 0;
        var current = this.head;
        while(counter !== index) {
            current = current.next;
            counter++;
        }
        return current;
    }
}

let list = new SinglyLinkedList();

단일 연결 리스트 : set 메소드 소개

Set()

리스트의 인덱스에 위치한 노드 값을 업데이트한다.

의사코드

• 인자로 값과 인덱스를 받습니다.
• 노드 값을 찾을 때 get 함수를 사용한다.
• 노드가 찾지 못했을 경우 false 반환
• 노드가 찾았을 경우, 해당 노드 값을 인자로 받아들인 값으로 업데이트하고 “true”로 반환한다.

솔루션

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList {
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    get(index) {
        if(index < 0 || index >= this.lenght) return null;
        var counter = 0;
        var current = this.head;
        while(counter !== index) {
            current = current.next;
            counter++;
        }
        return current;
    }
    set(index, val) {
        var foundNode = this.get(this);
        if(foundNode) {
            foundNode.val = val;
            return true;
        }
        return false;
    }
}

let list = new SinglyLinkedList();

단일 연결 리스트 : insert 메소드 소개

Insert

set과 비슷하지만 이미 존재하는 노드를 업데이트하는 대신 주어진 노드를 그곳이 어디든 주어진 위치에 새롭게 삽입한다.

의사코드

• 인자로 인덱스와 값 두 개를 받는다
• 범위를 벗어날 경우 삽입이 가능하지 않기 때문에 만일 인덱스가 “0”보다 작거나 혹은 리스트 길이보다 클 경우 “false”를 반환한다.
• 이때 “길이보다 크거나 같을 경우”가 아니라 “길이보다 클 경우”라는 점에 주목해야 한다.
• 인덱스가 길이와 같을 경우는 리스트의 맨 마지막에 삽입하면 안되기 때문이며, 이미 정의되 있는 경우 push() 메소드를 호출할 수 있습니다.
• 마찬가지로 리스트 맨 앞에 새로운 노드를 삽입하기 원한다면 unshift() 를 이용할 수 있다.
• 마찬가지로 get() 메서드를 사용해서 인텍스에 접근할 수 있다.
• 이전 노드의 next가 새롭게 생성된 후 삽입되는 노드를 가리키도록 설정한다.
• 길이 증가
• true 반환

솔루션

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList {
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val)
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    unshift(val) {
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }
    get(index) {
        if(index < 0 || index >= this.lenght) return null;
        var counter = 0;
        var current = this.head;
        while(counter !== index) {
            current = current.next;
            counter++;
        }
        return current;
    }
    insert(index, val) {
        if(index < 0 || index > this.length) return false;
        if(index === this.length) return this.push(val);
        if(index === 0) return !!this.unshift(val);

        var newNode = new Node(val);
        var prev = this.get(index - 1);
        var temp = prev.next;
        prev.next = newNode;
        newNode.next = temp;
        this.length++;
        return true;
    }
}

let list = new SinglyLinkedList();

단일 연결 리스트 : remove 메소드 소개

Remove

특정 위치의 단일 리스트의 노드를 제거한다.

의사코드

• 인덱스가 0보다 작거나 길이보다 크면 undefined 반환
• 만약 인덱스가 length -1 과 같다면 pop() 메서드 사용
• 만약 인덱스가 0이면, shift
• 마찬가지로 get 메서드로 index -1 노드에 접근한다

솔루션

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList {
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    remove(index){
        if(index < 0 || index >= this.length) return undefined;
        if(index === 0) return this.shift();
        if(index === this.length - 1) return this.pop();

        var prevNode = this.get(index - 1);
        var removed = prevNode.next;
        prevNode.next = removed.next;
        this.length--;
        return removed;
    }
}

let list = new SinglyLinkedList();

단일 연결 리스트 : reverse 메소드 소개

Reverse

연결 리스트를 제자리에서 뒤집는다.

의사코드

• head와 tail을 뒤집는다.
• next 변수를 생성한다.
• prev 변수를 생성한다.
• node 변수를 생성하고 현재 head 값으로 초기화 시킨다.

솔루션

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    reverse(){
        var node = this.head;
        this.head = this.tail;
        this.tail = node;
        var next;
        var prev = null;

        for(var i = 0; i < this.length; i++){
            next =node.next;
            node.next = prev;
            prev = node;
            node = next;
        }
        return this;
    }
}

var list = new SinglyLinkedList()
list.push("HELLO") 
list.push("GOODBYE")
list.push("!")

단일 연결 리스트 : 빅오 복잡도

• Insertion = O(1)
• Removal : It depends… O(1) or O(n)
• Searching : O(N)
• Access - O(N)

단방향 연결 리스트가 삽입과 삭제의 경우 어레이에 비해 우수하다.

따라서 삽입 혹은 삭제를 주로 해야한다거나, 임의 접근 작업이 필요없다거나, 그냥 주이진 순서대로 데이터를 관리할 필요가 있다거나, 50번째 혹은 백만번 째 노드에 접근할 필요가 없다거나 하는 경우 단방향 연결 리스트가 적절하다.

💡 요약

단방향 연결 리스트는 삽입과 제거가 빈번한 작업에서 어레이의 훌륭한 대안이다.

어레이는 내장된 인덱스를 가지고 있는 반면 단방향 연결 리스트는 그렇지않다.

이걸 배우는 이유 : 향후 스택 혹은 큐 등과 같이 단방향 연결 리스트를 기반으로 작성된 특수 목적의 자료구저에 대해서 배우게 될 때 필요하다.