0606 - 0612

0606

링크드 리스트

연결 리스트라고도 불리는 링크드 리스트에 대해 학습하고자 한다.
최근에 모의 면접을 진행하면서 나온 라이브 코딩 주제가 바로 이 링크드 리스트였다. 이때 문제를 잘 해결하기는 했지만, 배운지 오래된 내용이다보니 복습 차원에서 다시 공부해보고자 한다.

연결리스트는 여러 노드들이 연결되어있는 구조이다.
여기서 노드란 데이터와 링크로 구성되어있는 구조체이다. 노드는 링크를 통해 다음 노드에 접근할 수 있으며, 노드들은 다음에 올 노드의 정보를 갖고 있다.
이런 연결 리스트 구조에서 맨 앞을 Head라 하며, 맨 마지막을 Tail이라 한다.

시간 복잡도

삽입 - O(1)
삭제 - O(1)
검색 - O(n)

삽입의 경우, 기존 링크를 끊은 다음 추가할 위치의 이전 요소의 링크와 삽입할 자료를 연결한다.
그리고 추가할 요소의 링크와 다음 요소를 연결해주면 된다.
이와 같이, 삽입과 삭제의 경우 연결시켜주는 동작만 수행되므로 시간 복잡도는 O(1)이다.

연결 리스트에서 특정 자료를 검색하고 싶다면, 맨 앞의 head에서부터 순차적으로 자료를 찾아야 한다.
연결 리스트의 각 노드들은 다음 요소들의 정보를 갖고 있기 때문에 맨 앞의 요소에서부터 노드들을 순차적으로 검색한다. 이때의 시간 복잡도는 O(n)이다.

연결 리스트의 종류

위에서 살펴본 연결 리스트는 단방향 연결 리스트이다.
이 외에도 다양한 종류가 존재하는데, 이는 단방향 연결 리스트에서 개선된 자료구조들이다.

이중 연결 리스트

연결 리스트에서 탐색을 할 때, 뒤 쪽의 원소를 검색하면 루프를 돌아야 하기 때문에 탐색 속도가 많이 느려지게 된다.
이 문제를 해결하려면 뒤쪽 원소들도 빠르게 검색할 수 있는 이중 연결 리스트 구조를 활용하면 된다.

단일 연결 리스트와 다르게 2개의 주소 칸을 갖는다.
추가된 주소 칸은 이전 원소의 주소를 기억하고, Head 뿐만 아니라 가장 끝 원소인 Tail의 주소도 기억한다.
특정 인덱스의 탐색을 요청하면 해당 인덱스가 중앙보다 앞인지 뒤인지를 판단하여, 앞 쪽이라면 Head를 이용하고 뒤 쪽이라면 Tail을 이용하여 탐색한다.
그러나 주소를 2개 저장해야 해서 저장공간이 추가로 필요하다는 단점이 있다.

원형 연결 리스트

연결 리스트는 앞 혹은 뒤에서만 탐색을 수행할 수 있다.
어떤 순간에는 작업하던 곳에서 이어서 탐색을 진행하고 싶을 수 있다. 이러한 문제를 해결하기 위해 앞과 뒤가 연결되어 있고, 마지막 작업한 위치를 Head이자 Tail로 설정된 원형 연결 리스트를 사용할 수 있다.

굳이 Head가 어디인지, Tail이 어디인지 신경 쓸 필요가 없다. 마지막 작업하던 위치에서 이어서 연산을 수행할 수 있다는 장점이 있다.
데이터 순서의 개념이 모호해지고, 인덱스를 이용한 탐색이 어렵다는 단점이 있다.

배열 vs 연결 리스트

배열은 메모리를 연속적으로 저장한다는 특징을 가지고 있다.
또한 배열은 n번째 원소를 접근할 때 바로 접근할 수 있다. 하지만 메모리 사용이 비효율적이며, 배열 내의 데이터 추가 및 삭제의 시간 복잡도가 O(n)이라는 단점이 있다.
반대로 연결 리스트는 메모리를 효율적으로 사용할 수 있고 삽입, 삭제에 대해 효율적으로 할 수 있지만, 특정 위치 데이터를 검색할 때 느리다는 단점이 있다.

이 외에도 몇 가지 단점이 존재한다.

캐싱에 적합하지 않은 구조 - 배열은 데이터들이 연속된 메모리 공간에 저장되어 있어 캐시로 데이터를 넘기기 쉽지만, 연결 리스트는 처리속도가 매우 느려지게 됨
복잡한 연산에 따른 오버헤드 발생 - 일반적으로 연결리스트의 연산들이 훨씬 복잡
주소 저장으로 인한 공간 낭비 - 데이터 이외에도 주소에 대한 정보를 가지고 있어야 함

JS로 Linked List 구현

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

class LinkedList {
  constructor() {
    this.head = new Node("head");
  }

  append(newData) {
    const newNode = new Node(newData);
    let current = this.head;

    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }

  insert(newData, target) {
    const newNode = new Node(newData);
    const current = this.find(target);

    newNode.next = current.next;
    current.next = newNode;
  }

  find(data) {
    let currentNode = this.head;
    while (currentNode.data !== data) {
      currentNode = currentNode.next;
    }

    return currentNode;
  }

  remove(data) {
    const preNode = this.findPrevious(data);
    preNode.next = preNode.next.next;
  }

  findPrevious(data) {
    let currentNode = this.head;

    while (currentNode.next && currentNode.next.data !== data) {
      currentNode = currentNode.next;
    }

    return currentNode;
  }
}

const linkedList = new LinkedList();
linkedList.insert("A", "head");
linkedList.insert("B", "A");
linkedList.insert("C", "B");
linkedList.remove("B");
linkedList.append("D");
linkedList.append("E");

양방향 연결리스트의 경우 prev 프로퍼티를 추가해주면 된다.
원형 연결 리스트의 경우 constructor에서 head의 next가 head를 가리키게 하고, 이후 데이터가 추가되면 순환참조하도록 구현하면 된다.
단방향 연결리스트가 자바스크립트에서 대표적으로 쓰이는 예는 프로토타입이 있다.

reference
자료구조 연결리스트 with JavaScript

0608

이터레이터와 제너레이터

이터레이터 동작 방법

자바스크립트의 순회를 이해하려면 세 가지를 이해해야 한다.

이터러블 객체 - 배열, Set, Map 같은 순회할 수 있는 타입의 객체
이터레이터 객체 - 순회를 수행하는 객체
순회 단계의 결과를 담은 이터레이션 리절트 객체

이터레이터 객체를 반환하는 특별한 이터레이터 메서드를 가진 객체는 모두 이터러블 객체이다.
순회 결과 객체를 반환하는 next() 메서드가 있는 객체는 모두 이터레이터 객체이다.
순회 결과 객체는 value와 done 프로퍼티가 있는 객체이다.

이터러블 객체를 순회할 때는 먼저 이터레이터의 메서드를 호출해 이터레이터 객체를 얻는다. 그리고 이터레이터 객체의 next() 메서드를 반복적으로 호출하며 반환 값의 done 프로퍼티가 true일 때까지 반복한다.
여기서 이터러블 객체의 이터레이터 메서드는 일반적인 이름을 사용하는 것이 아니라 Symbol.iterator를 이름으로 사용한다.
내장된 이터러블 데이터 타입의 이터레이터 객체는 그 자체가 이터러블이다. 즉, 자기 자신을 반환하는 Symbol.iterator 메서드를 갖는다. 부분적으로 사용된 이터레이터를 순회할 때 이런 특징이 유용할 때가 간혹 있다.

제너레이터

제너레이터의 일차적인 설계 목적은 이터레이터를 쉽게 생성하는 것이다.
제너레이터는 코드 블록의 실행을 일시 중지했다가 필요한 시점에 재개할 수 있는 특수한 함수다.

제너레이터 함수는 함수 호출자에게 함수 실행의 제어권을 양도할 수 있고, 함수의 호출자와 함수의 상태를 주고받을 수 있다. 제너레이터 함수를 호출하면 제너레이터 객체를 반환하는데, 이는 이터러블이면서 동시에 이터레이터다.

제너레이터랑 이터레이터 객체의 차이

제너레이터 객체는 next 메서드를 갖는 이터레이터이지만 이터레이터에 없는 return, throw 메서드를 갖는다. 제너레이터 객체의 세 개의 메서드를 호출하면 다음과 같이 동작한다.

next 메서드를 호출하면 제너레이터 함수의 yield 표현식까지 코드 블록을 실행하고, yield된 값을 value 프로퍼티 값으로, false를 done 프로퍼티 값으로 갖는 이터레이터 리절트 객체를 갖는다.
return 메서드를 호출하면 인수로 전달받은 값을 value 프로퍼티 값으로, true를 done 프로퍼티 값으로 갖는 이터레이터 리절트 객체를 반환한다.
throw 메서드를 호출하면 인수로 전달받은 에러를 발생시키고 undefined를 value 프로퍼티 값으로, true를 done 프로퍼티 값으로 갖는 이터레이터 리절트 객체를 반환한다.

제너레이터 일시 중지와 재개

제너레이터는 yield 키워드와 next 메서드를 통해 실행을 일시 중지했다가 필요한 시점에 다시 재개할 수 있다.
일반 함수는 호출 이후 제어권을 함수가 독점하지만 제너레이터는 함수 호출자를 제어권에게 양도하여 필요한 시점에 함수 실행을 재개할 수 있다.
제너레이터 객체의 next 메서드를 호출하면 yield 표현식까지 실행되고 일시 중지된다. 이때 함수의 제어권이 호출자로 양도된다.
이때 제너레이터 객체의 next 메서드는 value, done 프로퍼티를 갖는 이터레이터 리절트 객체를 반환한다.

async 함수를 어떻게 구현할 수 있는가

자바스크립트의 제너레이터를 활용하여 구현할 수 있다고 생각한다.
제너레이터 함수를 인수로 받는 async 함수를 만든 뒤, async 함수 내부에서 인수로 받은 제너레이터 함수를 실행하여 변수에 제너레이터 객체를 저장한다.

그리고 제너레이터를 참조하여 next메서드를 실행하고 done 프로퍼티가 true라면 value를 false라면 제네레이터 함수가 끝까지 실행되지 않았으므로 value의 후속처리 메서드를 실행하여 다시 resolve한 결과를 인수로 재귀 호출하는 클로저를 반환한다.
사용할 때는 yield 키워드를 마치 await처럼 사용하면 async, await처럼 동작하게 구현할 수 있다.

Twitter Facebook LinkedIn

이정훈