13장 연결 리스트

  • 연결 리스트란 각 노드가 달느 노드를 가리키는 자료구조이다
  • 고정된 크기를 갖는 배열과는 달리 실행 시간에 메모리를 할당하거나 해제할 수 있는 동적 자료구조
  • 연결 리스트 자료구조는 각 노드가 다음 노드에 대한 참조를 갖는 자료구조로 data와 next속성이 있다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class SinglyLinkedListNode {
      constructor (data) {
        this.data = data;
        this.next = null; // 노드 마지막 연결지점은 null값임
      }
    }

    class SinglyLinkedList {
      constructor () {
        this.head = null;
        this.size = 0;
      }

      isEmpty() {
        return this.size === 0;
      }
    }
  • 연결 리스트의 시작을 헤드라고 부르고 이 값은 아무 항목도 삽입되지 않으면 null이다
  • 연결 리스트의 헤드가 비어있는 경우엔 신규 노드로 설정되고 비어있지 않다면 예전 헤드가 temp에 저장된 후에 새로운 헤드가 신규로 추가된 노드가 된다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // 위에서 이어짐
      insert(value) {
        if (this.head === null) this.head = new SinglyLinkedListNode(value);
        else {
          let temp = this.head;
          this.head = new SinglyLinkedListNode(value);
          this.head.next = temp;
        }
        this. size++;
      }
  • 단일 연결 리스트에서 노드를 삭제하는 것은 해당 노드의 참조를 제거함으로써 구현할 수 있다
  • next가 가리키는 노드를 찾고 해당 노드의 next 주소값을 이전 노드의 next값으로 할당하면 노드를 삭제할 수 있다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    remove(value) {
      let currHead = this.head;
      if (currHead.data === value) {
        // 삭제하고자 하는 노드가 지금 데이터와 같다면 헤드를 다음 노드로 변경하고 사이즈를 줄임
        this.head = currHead.next;
        this.size--;
      } else {
        // 헤드를 prv로 저장하고
        let prev = currHead;
        while (currHead.next) {
          // next 주소값이 null이 아닐때까지 순회한다
          if (currHead.data === value) {
            // 해당 값을 찾았다면 이전 값의 next를 현재 값의 next로 변경 (중간 잘라냄)
            prev.next = currHead.next;
            // prev값을 지금 head로 변경
            prev = currHead;
            currHead = currHead.next;
            break;
          }
          prev = currHead;
          currHead = currHead.next;
        }

        if (currHead.data === value) {
          // 삭제하는 노드의 next 주소값은 null로 변경하여 잘라내기
          prev.next = null;
        }

        this.size--;
      }
    }
  • 연결 리스트의 헤드에 있는 항목을 삭제하는 것은 O(1)만에 가능한데 맨 처음에 있는 값이기 때문
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    deleteHead() {
      let toReturn = null;

      if (this.head !== null) {
        toReturn = this.head.data;
        this.head = this.head.next;
        this.size--;
      }
      return toReturn;
    }
  • 연결 리스트 내의 값을 검색하려면 모든 next 포인터를 반복순회해야한다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    find (value) {
      let currHead = this.head;
      while(currHead.next) {
        if (currHead.data === value) {
          return true;
        }
        currHead = currHead.next;
      }
      return false;
    }
  • 이중 연결 리스트는 양방향 단일 연결 리스트 같은 것이다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class DoubleLinkedListNode {
      constructor (data) {
        this.data = data;
        this.next = null;
        this.prev = null;
      }
    }

    class DoubleLinkedList {
      constructor () {
        this.head = null;
        this.tail = null;
        this.size = 0;
      }

      isEmpty () {
        return this.size === 0;
      }
    }
  • 양방향으로 연결되어 있으므로 노드들은 next와 prev 둘 다 갖는다
  • 헤드에 항목을 삽입하는 것은 prev 포인터를 갱신해야 한다는 점 빼고는 단일 연결 리스트와 같다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    insertHead (value) {
      if (this.head === null) {
        // 헤드가 비어있다면 이 헤드에 새로운 값을 갖는 노드를 추가
        this.head = new DoublyLinkedListNode(value);
        this.tail = this.head;
        // 단 하나만 있을 경우에 이 노드가 헤드이자 테일이기 때문
      } else {
        // 이미 헤드가 있다면 임시로 노드를 만들고
        let temp = new DoublyLinkedListNode(value);
        // 만든 노드의 next값을 현재 헤드값으로 변경하고
        temp.next = this.head;
        // 현재 헤드값의 prev값을 새로 만든 노드로 설정한다 (양방향이므로)
        this.head.prev = temp;
        // 새로 만든 노드가 새 헤드가 된다 (있었던 헤드가 밀려남)
        this.head = temp;
      }
      this.size++;
    }
  • 헤드를 삭제할 때 연결 리스트가 하나의 노드라면 prev와 next 모두 null로 설정해야 하며 여러개 존재하는 경우 삭제하는 헤드의 next값을 헤드로 설정한다
  • 신규 헤드의 prev값을 null로 설정하여 참조를 제거한다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    deleteHead () {
      let toReturn = null;
      if (this.head !== null) {
        toReturn = this.head.data;

        if (this.tail === this.head) {
          this.head = null;
          this.tail = null;
        } else {
          this.head = this.head.next;
          this.head.prev = null;
        }
      }
      this.size--;
      return toReturn; // dequeue와 같은 방식임 
    }
  • 테일 항목 삭제도 헤드 삭제와 같은 방식으로 제거한다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    deleteTail() {
      let toReturn = null;

      if(this.tail !== null) {
        toReturn = this.tail.data;

        if (this.tail === this.head) {
          this.head = null;
          this.tail = null;
        } else {
          this.tail = this.tail.prev;
          this.tail.next = null;
        }
      } 
    this.size--;
    return toReturn;
    }
  • 양항향 연결 리스트에서는 헤드에서 헤드의 next 포인터를 사용할 수 있다 (반대로도 가능)
    1
    2
    3
    4
    5
    6
    7
    8
    findFromHead (value) {
      let currHead = this.head;
      while (currHead.next) {
        if (currHead.data === value) return true;
        currHead = currHead.next;
      }
      return false;
    }
  • 단일 연결 리스트 뒤집기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    const reverseSinglyLinkedList = sll => {
      let node = sll.head;
      let prev = null;
      // 방향성을 반대로 바꾸는 과정
      while (node) {
        let temp = node.next;
        node.next = prev;
        prev = node;
        if (!temp) break;
        node = temp;
      }
      return node;
    }
  • 연결 리스트에서 중복된 항목 제거하기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    const deleteDuplicateDataInSLL = sll => {
      let track = [];

      let temp = sll.head;
      let prev = null;
      while (temp) {
        if (track.indexOf(temp.data) >= 0) {
          prev.next = temp.next;
          sll.size--;
        } else {
          track.push(temp.data);
          prev = temp;
        }
        temp = temp.next;
      }
      console.log(temp);
    }
  • 개선하기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    const deleteDuplicateDataInSLL = sll => {
      let track = {};
      let temp = sll.head;
      let prev = null;
      while (temp) {
        if(track[temp.data]) {
          prev.next = temp.next;
          sll.size--;
        } else {
          track[temp.data] = true;
          prev = temp;
        }
        temp = temp.next;
      }
      console.log(temp);
    }

    14장 캐싱

  • 캐싱은 자료를 임시 메모리에 저장하는 과정으로 대표적인 캐싱 방법에는 LFU(Least Frequently Used) 캐싱과 LRU(Least Recently Used) 캐싱이 있다
  • 최근에 접근한 메모리 위치를 다시 접근할 가능성이 높고(시간적 지역성), 최근에 접근한 메모리 위치 주변의 위치를 다시 접근할 가능성이 높다(공간적 지역성)
  • LFU 캐싱은 운영체제가 메모리를 관리하기 위해 사용하는 캐싱 알고리즘으로 가장 참조 빈도가 낮은 항목을 삭제한다
  • LFU 캐시는 이중 연결 리스트를 사용해 O(1)시간에 항목을 제거한다
  • LFU의 노드에는 freqCount 속성이 있다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    class LFUNode {
      constructor (key, value) {
        this.prev = null;
        this.next = null;
        this.key = key;
        this.data = data;
        this.freqCount = 1;
      }
    }

    class LFUDoublyLinkedList {
      constructor () {
        this.head = new LFUNODE('buffer head', null);
        this.tail = new LFUNODE('buffer tail', null);
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.size = 0;
      }

      insertHead (node) {
        node.next = this.head.next;
        this.head.next.prev = node;
        this.head.next = node;
        node.prev = this.head;
        this.size++;
      }

      removeTail () {
        let oldTail = this.tail.prev;
        let prev = this.tail.prev;
        prev.prev.next = this.tail; // 전 전 노드의 next를 테일로 지정
        this.tail.prev = prev.prev; // 테일을 제거하면 테일 앞 값을 테일로 지정해주어야 함
        this.size--;
        return oldTail;
      }

      removeNode(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        this.size--;
      }
      /*
        LFU의 set을 구현하기 위해서는 신규 항목의 삽입과 예전 항목의 교체가 필요함
        신규 항목을 삽입할 때 신규 노드가 생성되고 캐시 capacity가 꽉차지 않았다면 freq의 빈도 이중 연결 리스트에 삽입할 수 있다
        캐시가 꽉 찬 경우 빈도 이중 연결 리스트의 테일 항목이 삭제된 다음 삽입된다
      */
      set(key, value) {
        let node = this.keys[key];
        if (node === undefined) {
          node = new LFUNode(key, value);

          this.keys[key] = node;
          
          if (this.size !== this.capacity) {
            if (this.freq[1] === undefined) {
              this.freq[1] = new LFUDoublyLinkedList();
            }
            this.freq[1].insertHead(node);
            this.size++
          } else {
            let oldTail = this.freq[this.minFreq].removeTail();
            delete this.keys[oldTail.key];

            if (this.freq[1] === undefined) {
              this.req[1] = new LFUDoublyLinkedList();
            }

            this.freq[1].insertHead(node);
            this.minFreq = 1;
          } else {
            let oldFreqCount = node.freqCount;
            node.data = value;
            node.freqCount++;

            this.freq[oldFreqCount].removeNode(node);

            if (this.freq[node.freqCount] === undefined) {
              this.freq[node.freqCount] = new LFUDoublyLinkedList();
            } 

            this.freq[node.freqCount].insertHead(node);

            if (oldFreqCount === this.minFreq 
                && Object.keys(this.freq[oldFreqCount]).size === 0) {
                  this.minFreq++;
            }
          }
        }
      }

      get (key) {
        let node = this.keys[key];

        if (node === undefined) return null;
        else {
          let oldFreqCount = node.freqCount;
          node.freqCount++;
          this.freq[oldFreqCount].removeNode(node);

          if (this.freq[node.freqCount] === undefined) {
            this.freq[node.freqCount] = new LFUDoublyLinkedList();
          }

          this.freq[node.freqCount].insertHead(node);

          if (oldFreqCount === this.minFreq 
              && Object.keys(this.freq[oldFreqCount]).length === 0) {
                this.minFreq++;
          }
          return node.data;
        }
      }
    }

    class LFUCache {
      constructor (capacity) {
        this.key = {}; // LFUNode를 저장하는 공간
        this.freq = {};// LFUDoublyLinkedList를 저장하는 공간
        this.capacity = capacity;
        this.minFreq = 0;
        this.size = 0;
      }
    }
  • LRU 캐싱은 가장 오래된 항목을 먼저 제거하는 캐싱 알고리즘이다
  • 캐시의 항목에 접근하면 해당 항목은 리스트의 뒤(가장 최신)로 이동하고 가장 앞에 있는 항목이 제거되며 새 항목은 가장 뒤에 추가된다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    class DLLNode {
      constructor (key, data) {
        this.key = key;
        this.data = data;
        this.next = null;
        this.prev = null;
      }
    }

    class LRUCache {
      constructor (capacity) {
        this.keys = {};
        this.capacity = capacity;
        this.head = new DLLNode('', null);
        this.tail = new DLLNode('', null);
        this.head.next = this.tail
        this.tail.prev = this.head;
      }

      removeNode (node) {
        let prev = node.prev,
            next = node.next;
        prev.next = next;
        next.prev = prev;
      }

      addNode (node) {
        let realTail = this.tail.prev;
        realTail.next = node;

        this.tail.prev = node;
        node.prev = realTail;
        node.next = this.tail;
      }

      get (key) {
        let node = this.keys[key];
        if (node === undefined) return null;
        else {
          this.removeNode(node);
          this.addNode(node);
          return node.data;
        }
      }

      set (key, value) {
        let node = this.keys[key];
        if (node) this.removeNode(node);

        let newNode = new DLLNode(key, value);

        this.addNode(newNode);
        this.keys[key] = newNode;

        if (Object.keys(this.keys).length > this.capacity) {
          let realHead = this.head.next;
          this.removeNode(realHead);
          delete this.keys[realHead.key];
        }
      }
    }
  • 대부분의 경우 LFU는 LRU보다 성능이 떨어진다 LFU는 특정 시점에 한해 자주 사용된 경우를 배제할 수 없기 때문