[자료구조]단방향(단일) 연결 리스트(2)

👉 1편 선행

✅ 단방향 연결 리스트란?

연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 인덴스가 존재하지 않으며, 리스트에서 어딘가 접근하고 싶다면 첫 번째 노드부터 살펴봐야 한다.

 

지난 시간 단반향 연결 리스트 메서드인 Push(맨 뒤 추가), Pop(맨 뒤 제거), Shift(맨 앞 제거), Unshift(맨 앞 추가)를 구현하였다. 2편에서는 Get, Set, Insert, Remove, Reverse 메서드를 구현해 보고 Big O 복잡도를 알아보자.

 

🟢 5. Get

주어진 숫자(인덱스)만큼 리스트를 따라간 후 해당 위치의 노드를 반환한다. 

• 인자로 찾으려는 노드의 index 값을 받는다.
• 인덱스가 음수이거나 리스트의 길이와 같거나 클 경우 null을 반환한다.
• 리스트의 해당 인덱스에 도달할 때까지 반복하고 해당 인덱스의 노드를 반환한다.

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

get 메서드를 살펴보면 index를 받고 예외 상황을 미리 방지해 두었다. counter와 index가 같아지면 반복을 멈춘다. current는 계속 다음 값으로 업데이트되면 counter가 증가하게 된다. 반복이 종료되면 내가 찾던 노드가 current가 된다.  

🟢 6. Set

주어진 숫자(인덱스)에 해당하는 노드의 값을 업데이트한다.

• value와 index를 받아들인다.
• get 메서드를 이용하여 특정 노드를 찾을 수 있다.
• 노드를 찾지 못했을 경우 false를 반환한다.
• 노드를 찾았다면, 인자로 받은 value를 해당 노드의 value로 업데이트하고 true를 반환한다.

class SinglyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    set(index, val) {
        let foundNode = this.get(index);
        if(foundNode) {
            foundNode.val = val;
            return true;
        }
        return false; 
    }
}
let list = new SinglyLinkedList()

🟢 7. Insert

특정 위치(인덱스)에 노드를 추가한다.

• 인덱스가 음수이거나 리스트의 길이보다 클 경우 false를 반환한다.
• 인덱스가 리스트의 길이과 같을 경우, push 호출
• 인덱스가 0일 경우, unshift 호출
• 만약 인덱스 3에 insert 하려고 하면, 인덱스 2의 노드를 찾아야 하고 그러려면 get(index -1)을 호출하면 된다.
• 해당 노드의 next 속성을 새로운 노드로 설정한다.
• 새로운 노드의 next 속성을 이전 노드의 next 노드로 연결한다. 
• 길이를 1만큼 증가시킨다.
• true를 반환한다.

class SinglyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    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);
        
        let prev = this.get(index - 1);
        let temp = prev.next;
        let newNode = new Node(val);
        prev.next = newNode;
        newNode.next = temp;
        this.length++;
        return true;
    }
}
let list = new SinglyLinkedList()

🟢 7. Remove

특정 위치(인덱스)에 있는 노드를 제거한다.

• 인덱스가 음수이거나 리스트의 길이와 같거나 클 경우 undefined을 반환한다.
• 인덱스가 리스트의 length - 1일 경우, pop 호출
• 인덱스가 0, shift 호출
• get(index - 1)을 이용하여 해당 인덱스(인자)의 이전 노드를 찾는다.
• 이전 노드의 next를 이전 노드의 next의 next로 설정한다. (prev.next = prev.next.next) 
• 길이를 1 감소
• 제거된 노드를 반환한다.

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();
        
        let previousNode = this.get(index - 1);
        let removed = previousNode.next;
        previousNode.next = removed.next;
        this.length--;

        return removed;
    }
}
let list = new SinglyLinkedList()

🟢 8. Reverse

리스트를 역방향으로 만든다. 글로 설명하는 것은 어렵기에 코드를 보고 이해하는 편이 빠르다. 

print() {
    let arr = [];
    let current = this.head;
    while (current) {
        arr.push(current.val)
        current = current.next
    }
    console.log(arr);
}

먼저 list의 값을 간단하게 print 해줄 메서드를 만들어 두었다. Reverse를 구현해 보자.

reverse() {
    let node = this.head;
    this.head = this.tail;
    this.tail = node;

    // tail의 next가 null이기 때문에
    let prev = null;
    let next;

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

list.print() = [100, 201, 250, 350, 999] 

100이 tail이 되고, 999가 head가 된다.

 

한 번의 루프 node(100), prev(null), next(undefined)로 시작

1. next는 node(100)의 next(201)이 된다. next(201)
2. node.next = prev(null); 즉, tail인 node는 next값이 null이 된다.
3. prev(null) = node(100)이 된다. prev(100)
4. node(100) = next(201)이 된다. node(201)

100은 null을 기리 키고, 이 과정을 반복하기에

 

두 번의 루프  node(201), prev(100), next(201)로 시작

1. next 변수는 node(201)의 next(250)이 된다. next(250)
2. node.next = prev(100);  node.next(100)
3. prev(100) = node(201)이 된다. prev(201)
4. node(100) = next(250)이 된다. node(250)

201은 이전 값인 100을 가리킨다. 201 -> 100 -> null

이 과정을 리스트 길이만큼 반복한다. 한 번에 이해하는 것은 쉽지 않기에 과정을 그리면서 이해하자.

 

🤔 Big O of Singly Linked Lists

Insertion - O(1)

Removal - O(1) or O(N)

Searching - O(N)

Access - O(N)

 

삽입과 삭제 작업이 주로 이용될 경우 단방향 연결 리스트는 배열의 훌륭한 대안이 될 수 있으며 스택과 큐 자료구조를 구현하기 위해 단방향 연결 리스트에 대한 이해가 있어야 한다.