190727 TIL 자료구조 - Linked List

Jul 27, 2019 » 1막, TIL (Today I Learned)

자료구조 - Linked List

Linked List에 대해 스터디했다. (예전에 알고리즘 스터디에서 발표한걸 들었었지만 잘 기억이 나지 않았다..)
leedCode에서 linked list 관련 문제를 풀었다.

1. Delete Node in a Linked List

var deleteNode = function(node) {
    node.val = node.next.val;
    node.next = node.next.next;
};

2. Remove Linked List Elements

var removeElements = function(head, val) {
    if (head === [] || head === null) return head;
    if (head.val === val && head.next === null) {
        return null;
    }
    while(head.val === val && head.next) {
        head = head.next;
    }
    if (head.val === val && !head.next) {
        head = null;
        return head;
    }
    let current = head;
    while (current.next) {
        while (current.next.val === val && current.next.next) {
            current.next = current.next.next;
        } if (current.next.val === val && !current.next.next) {
            current.next = null;
            return head;
        } current = current.next; 
    }
    return head;
};

~~리팩토링이 심각해보인다~~

배운점

array는 메모리에 연속된 일정 공간을 차지하기 때문에 원소를 추가/삭제해도 차지하는 공간은 그대로이다.
반면 linked list는 연속된 일정 공간을 차지할 필요가 없기 때문에 메모리 효율이 array보다 좋다. 만약 원소를 추가/삭제 한다면 그 요소의 공간은 남아있겠지만 언젠가 garbage collector가 청소한다.
array의 시간복잡도는 탐색은 O(1)이지만 원소 추가/삭제는 O(n)이며, linked list의 시간복잡도는 탐색은 O(n)이지만 원소 추가/삭제는 O(1)이다.