[CS] TypeScript를 이해하기 위한 JavaScript 고찰(양방향 리스트를 이용하여 Stack, Queue를 Typescript로 구현하기)

nkm 2024. 12. 19. 18:09

728x90

JS Undefined 고찰
표현식과 문의 대하여
심벌 테이블(JS에서의 컴파일러, 인터프리터의 키로 바인딩 된 값의 메모리 주소, 데이터 타입, 스코프 관리의 용이한 자료구조)
Garbage Collection : mark and sweep (자료구조 수업 중 remove의 범위를 메모리 상으로 생각하여 GC를 이용한 프로그래밍이 가능한 것인지에 대해)
DoublyLinkedList 구현체
stack (제네릭 클래스 형태의 Stack을 DoublyLinkedList를 이용하여 구현)
Queue (Stack과 마찬가지로 DoublyLinkedList를 이용하여 구현)
피드백(method 반환값의 대한 처리 중 undefined, throw 등 타입가드 및 유니온 타입의 처리의 대한 고찰)
Hash Function -> 이카운트는 어떻게 서비스 로직에서 처리 했을까?

해당 목차로 구성한 이유는 JS의 기본적인 부분을 확실하게 알지 못한 상태로 typescript를 진행해봤자 문법만 익숙해질 뿐 원리에 대해 더욱 멀어질거라고 생각하여 포괄적으로 JS에서 이정도는 설명할 줄 안다면 Node, 브라우저 상의 내가 작성한 Typescript, JS를 이해하고 머리속으로 그림을 그려가며 코딩을 할 수 있겠다 생각이 들었습니다.

해당 부분보다 더 많은 부분을 찾아보고 공부했지만 해당 목차에 대해서 설명할 줄 아는 실력이 된다면 이번주에 배운내용들에 대해서 내가 어떤 코드를 어떤 동작 원리로 작성했는지를 확실히 깨달을 수 있을 거라고 생각하고 작성했습니다.

1. JS Undefined 고찰

1. JavaScript에서 `undefined` 사용 이유

JavaScript는 동적 타이핑(Dynamic Typing)을 지원하는 언어로, 변수의 데이터 타입을 컴파일 시점에 결정하는 것이 아니라 실행 시점에 결정합니다. 이러한 특성 덕분에, JavaScript는 변수에 초기값을 할당하지 않거나, 객체에서 값을 찾을 수 없는 경우에 undefined를 반환하여 코드의 상태를 명확하게 나타낼 수 있습니다. undefined는 JS에서 다음과 같은 이유로 중요한 역할을 합니다.

2. JavaScript의 객체 기반 모델과 `undefined`

JavaScript는 객체 기반 언어이며, 원시 타입(primitive type) 외에는 모두 객체로 취급됩니다. 객체는 프로퍼티의 집합으로 이루어져 있으며, 이 프로퍼티는 key-value 쌍이나 함수일 수 있습니다. 이때, 프로퍼티가 값을 가지지 않는 경우에 undefined는 객체의 프로퍼티가 초기화되지 않았다는 것을 나타냅니다.

예시:


let person = {

  name: "John",

  age: 30

};



console.log(person.address);  // undefined

여기서 address 프로퍼티는 person 객체에 존재하지 않기 때문에 undefined를 반환합니다. 이는 "값이 존재하지 않는다"는 의미로, undefined는 객체에서 프로퍼티가 없거나 초기화되지 않은 상태를 표현합니다.

3. JavaScript의 메모리 관리와 `undefined`

JavaScript는 자동 메모리 관리를 위해 가비지 컬렉션(GC) 을 사용합니다. C와 같은 저수준 언어에서는 메모리를 직접 할당하고 해제해야 하지만, JavaScript에서는 변수와 객체의 생애 주기를 추적하며 더 이상 사용되지 않는 객체를 자동으로 메모리에서 해제합니다. 이 과정에서 undefined는 메모리 상에서 값이 초기화되지 않았거나 존재하지 않는 변수를 명확하게 구분짓는 데 중요한 역할을 합니다.

`undefined`와 변수 할당


let x;

console.log(x);  // undefined

위 코드에서 x는 선언만 되었고 값이 할당되지 않았기 때문에 undefined로 초기화됩니다. 이때 undefined는 변수의 상태를 명확하게 나타내며, 메모리 관리 상에서는 이 변수를 사용할 수 없는 상태로 처리합니다.

4. `undefined`와 값의 부재

JavaScript에서는 값이 없는 상태를 표현할 때 undefined를 사용합니다. 예를 들어, 함수가 반환값이 없을 때나, 배열이나 객체에서 존재하지 않는 값을 찾을 때 undefined가 반환됩니다.

함수 반환값이 없는 경우:


function test() {}

console.log(test());  // undefined

배열에서 존재하지 않는 인덱스에 접근할 경우:


let arr = [1, 2];

console.log(arr[5]);  // undefined

5. 정리: `undefined`의 역할

JavaScript에서 undefined는 값이 없는 상태를 명확히 표현하는 중요한 특수 값입니다. 이 값은 다음과 같은 경우에 사용됩니다:

변수 선언 후 값이 할당되지 않았을 때
객체에서 존재하지 않는 프로퍼티에 접근했을 때
함수에서 명시적인 반환값 없이 호출했을 때
배열에서 존재하지 않는 인덱스를 참조했을 때

undefined는 JavaScript가 메모리와 값을 효율적으로 관리할 수 있도록 도와주는 중요한 역할을 하며, 특히 동적 타이핑과 가비지 컬렉션을 지원하는 언어 특성상 필수적인 개념입니다.

2. 표현식과 문의 대하여

표현식은 값의 계산과 반환을 담당하며, 메모리 상에서 값을 생성하고 이를 다른 코드에서 활용할 수 있게 합니다. 표현식은 코드에서 값이 필요한 모든 곳에 사용할 수 있으며, 그 값은 메모리에서 생성되고 참조됩니다.

문은 값이 필요한 곳에서 사용되는 것이 아니라, 동작을 정의하고 수행하는 역할을 합니다. 문은 코드의 흐름을 제어하거나 상태를 변경하며, 값 자체를 생성하지 않습니다.

따라서 메모리 관점에서 보면, 표현식은 메모리에 값을 생성하고 그 값을 참조할 수 있게 만드는 반면, 문은 메모리에서 값을 생성하거나 반환하는 역할을 하지 않습니다.

값 생성

표현식은 메모리에서 값을 생성하고 그 값을 반환합니다. 예를 들어, 5 + 3은 메모리에서 두 값을 더하여 결과를 생성하고, 그 결과를 반환합니다.

문은 값을 생성하지 않으며 코드 흐름을 제어하거나 특정 작업을 수행합니다. 예를 들어, let a = 5;는 값을 할당하는 문으로, a 변수에 값을 설정하는 작업을 하지만, 그 자체로 값은 반환하지 않습니다.

메모리 관리

표현식에서 값은 메모리에 할당됩니다. 메모리 상에서 계산된 값은 참조되거나 변수에 저장됩니다. 예를 들어, let result = 5 + 3;에서 5 + 3 표현식의 결과는 result라는 변수에 할당됩니다.

문은 메모리 상에서 값을 할당하는 역할을 할 수 있지만, 그 자체로 값을 생성하지 않습니다. 예를 들어, let a = 5;에서 a는 메모리에 5라는 값을 가지지만, let a = 5; 자체는 단지 변수에 값을 설정하는 작업을 하는 문입니다.

값의 흐름

표현식은 그 자체로 값을 반환하므로, 그 값을 다른 표현식에 전달하거나 변수에 할당할 수 있습니다.

문은 값의 흐름을 제어하며, 결과를 다른 코드로 전달하지 않고 작업을 수행합니다. 예를 들어, if문이나 while문은 코드의 흐름을 제어하며 값을 반환하지 않습니다.

3. 심볼 테이블

기본 심볼 테이블과 JavaScript의 심볼 테이블 고찰

심볼 테이블(Symbol Table)은 컴파일러나 인터프리터가 프로그램에서 사용하는 변수, 함수, 클래스 등의 심볼(symbol)에 대한 정보를 관리하기 위해 사용하는 중요한 자료구조입니다. 기본적으로 심볼 테이블은 프로그램 코드가 실행되거나 변환될 때, 각 심볼의 메모리 주소, 데이터 타입, 스코프, 상태 등의 정보를 효율적으로 추적하고 관리할 수 있도록 돕습니다. 이러한 테이블은 코드의 구문 분석 과정에서 변수나 함수가 올바르게 선언되었는지, 타입이 일치하는지, 스코프 내에서만 유효한지 등을 확인하는 데 중요한 역할을 합니다.

1. 기본 심볼 테이블의 역할과 구성

기본적으로 심볼 테이블은 컴파일러와 인터프리터가 코드 분석 및 실행을 위한 필수적인 정보를 저장하는 구조입니다. 이 테이블은 변수나 함수, 클래스의 이름(심볼)과 함께 메모리 주소, 데이터 타입, 스코프 등의 속성을 기록합니다. 또한, 변수가 선언된 위치, 초기화 여부 등도 함께 관리하여, 프로그램에서 각 심볼이 어떻게 다루어지는지를 추적합니다.

컴파일러의 경우, 소스 코드가 구문 분석을 거치고 세멘틱 분석을 통해 오류를 확인하는 과정에서 심볼 테이블이 사용됩니다. 예를 들어, 변수의 타입이 잘못되었거나, 특정 스코프에서 정의되지 않은 변수를 참조하려 할 때, 컴파일러는 심벌 테이블을 참조하여 오류를 발생시킵니다. 심볼 테이블은 메모리 최적화, 타입 검사, 스코프 관리 등 다양한 목적으로 사용되며, 프로그램의 실행 전에 모든 정보가 추적되고 검증되도록 돕습니다.

2. JavaScript에서의 심볼 테이블

JavaScript는 동적 타이핑 언어로, 변수의 타입을 실행 중에 결정하며, 변수 선언과 할당이 런타임에 이루어집니다. 이러한 특성 때문에, JavaScript는 컴파일 과정에서 발생하는 여러 단계 중 심볼 테이블의 관리 방식이 동적입니다. JavaScript 엔진은 프로그램 실행 중에 심볼 테이블을 실시간으로 업데이트하고, 코드가 실행되는 동안 변수를 추적하고 관리합니다.

JavaScript에서 심볼 테이블은 변수, 함수, 객체 프로퍼티 등의 심볼에 대한 정보를 관리하는 데 중요한 역할을 합니다. 예를 들어, 코드에서 변수를 선언하고 할당하면, JavaScript 엔진은 해당 변수가 어떤 데이터 타입을 갖는지, 어떤 스코프에 속하는지 등을 추적하고 이를 심볼 테이블에 기록합니다. 또한, JavaScript는 스코프 체인(Scope Chain)을 통해 변수의 유효 범위를 관리하는데, 이는 심볼 테이블이 스코프별로 관리되는 방식으로 구현됩니다.


let x = 10;



function foo() {

  let y = 20;

  console.log(x + y); // 여기서 x와 y는 각각의 스코프에서 참조됩니다.

}



foo();

위의 예제에서, 변수 x는 전역 스코프에 선언되었고, 변수 y는 foo 함수의 지역 스코프에 선언되었습니다. JavaScript 엔진은 foo() 함수가 실행될 때 x와 y를 각각의 스코프에 맞게 심볼 테이블에 기록하고, 함수 실행 후에 지역 변수 y는 더 이상 참조되지 않게 됩니다.

3. 동적 타이핑과 런타임에서의 심볼 테이블 관리

JavaScript의 심볼 테이블은 동적 타이핑 특성에 맞춰 런타임 동안 실시간으로 관리됩니다. 변수가 처음 선언될 때는 타입 정보가 초기화되지 않은 상태로 존재하며, 값이 할당될 때 그 값의 타입에 맞춰 업데이트됩니다. 예를 들어, 아래 코드에서 x는 undefined로 초기화되었고, 그 후 값이 할당됩니다.


let x; // x는 선언만 되고 값은 할당되지 않음

console.log(x); // undefined 출력

x = 5; // x에 값 할당

console.log(x); // 5 출력

이 경우, 심볼 테이블은 x를 초기화되지 않은 상태로 등록하며, x에 값이 할당되면 그 타입과 값을 업데이트합니다. 동적 타이핑 덕분에, JavaScript는 변수의 타입을 런타임에 결정하고, 심볼 테이블에서 이를 실시간으로 추적합니다.

4. 스코프 관리와 클로저(Closure)

JavaScript에서는 스코프 관리가 매우 중요한데, 이는 스코프 체인을 통해 이루어집니다. 심볼 테이블은 각각의 함수와 블록에서 선언된 변수들이 해당 스코프 내에서만 유효하도록 관리합니다. 클로저(closure)와 같은 고급 개념에서도 심볼 테이블이 중요한 역할을 합니다. 클로저는 함수가 자신의 외부 함수 변수에 접근할 수 있도록 하는 특성을 가집니다. 이때, 외부 함수의 변수는 해당 함수의 스코프 체인 내에서 심볼 테이블을 통해 추적됩니다.


function outer() {

  let x = 10;



  return function inner() {

    console.log(x); // inner 함수가 outer 함수의 변수 x에 접근

  }

}



let closure = outer();

closure(); // 10 출력

위의 예제에서 inner() 함수는 outer() 함수의 지역 변수 x에 접근할 수 있습니다. 이는 outer() 함수의 스코프가 심볼 테이블에 기록되어 있고, inner() 함수가 이 스코프 체인에 접근할 수 있기 때문입니다.

기본 심볼 테이블은 컴파일러와 인터프리터가 프로그램의 변수, 함수, 타입, 스코프 등을 효율적으로 관리하기 위한 중요한 도구입니다. 기본적으로 심볼 이름, 메모리 주소, 데이터 타입, 스코프 등을 추적하여 프로그램의 실행을 지원합니다. JavaScript에서는 동적 타이핑과 런타임 평가를 통해 심볼 테이블을 실시간으로 관리하며, 이를 통해 스코프 관리와 타입 추적이 이루어집니다. JavaScript의 심볼 테이블은 프로그램 실행 중에 동적으로 변수를 관리하고, 이를 통해 효율적인 메모리 관리와 오류 검출을 가능하게 만듭니다.

4. Garbage Collection의 Mark and Sweep 알고리즘

자바스크립트에서 메모리 관리는 Garbage Collection (GC)을 통해 자동으로 처리됩니다. GC는 더 이상 사용되지 않는 객체를 메모리에서 제거하여 메모리 누수를 방지하는 역할을 합니다. 그 중 Mark and Sweep은 대표적인 GC 알고리즘입니다.

Mark and Sweep의 동작 과정

Mark and Sweep 알고리즘은 두 단계로 구성됩니다: Marking과 Sweeping.

Marking (표시 단계):
- 루트 객체(root objects)에서 시작하여, 참조 가능한 객체들을 찾고 이를 "마크"합니다.
- 루트 객체란 전역 객체나 스택, 레지스터 등에 직접적으로 참조되는 객체들입니다.
- 마킹 과정에서, GC는 루트 객체부터 시작하여, 각 객체가 다른 객체를 참조하는지 확인하고, 참조되는 객체들을 모두 마크합니다.
- 이 과정을 통해, 현재 프로그램에서 여전히 사용 중인 객체들을 식별할 수 있습니다.

Sweeping (청소 단계):
- 마킹된 객체들을 제외한 남은 객체들을 모두 삭제합니다. 마킹되지 않은 객체들은 더 이상 참조되지 않으며, 쓰레기(garbage)로 간주되어 메모리에서 해제됩니다.
- 이 단계에서는 마킹되지 않은 객체들이 메모리에서 제거되고, GC가 메모리를 다시 사용할 수 있도록 합니다.

Mark and Sweep의 동작 예시

예를 들어, 자바스크립트에서 객체 간에 참조가 있을 때, GC가 Mark and Sweep을 어떻게 적용하는지 보겠습니다.

Marking 단계:
- 루트 객체(전역 객체 또는 변수 등)부터 시작해서, 객체들이 서로 참조하는 관계를 따라가며 객체들을 마킹합니다. 예를 들어, 변수 a가 객체 A를 참조하고, 객체 A가 객체 B를 참조한다고 가정합시다.
- 루트 객체에서 시작하여, a를 통해 A를 마크하고, A에서 B를 마크합니다.

Sweeping 단계:
- 마킹된 객체들(A와 B)을 제외하고, 마킹되지 않은 객체들은 모두 메모리에서 해제됩니다.
- 예를 들어, 객체 C가 더 이상 a, A, B 등에서 참조되지 않는다면, C는 마킹되지 않으며, 메모리에서 제거됩니다.

Mark and Sweep에서의 메모리 관리와 `clear` 메서드

clear 메서드에서 리스트를 순회하며 노드를 비우는 작업을 했던 것처럼, Mark and Sweep 알고리즘에서도 객체들 간의 참조를 끊는 작업이 중요합니다. 객체가 다른 객체를 참조하고 있으면, 해당 객체는 "마크"되고, 메모리에서 해제되지 않도록 보호됩니다.


// 예시: clear 메서드에서의 참조 끊기

public clear(): void {

  while (this._head !== null) {

    const nextNode = this._head.next;

    this._head.next = null;  // 참조 끊기

    this._head = nextNode;   // 다음 노드로 이동

  }

  this._tail = null;

  this._count = 0;

}

위의 clear 메서드에서 각 노드의 next 참조를 null로 설정하는 것은 참조를 끊는 작업입니다. 이 작업은 GC가 메모리에서 해당 노드를 안전하게 해제할 수 있도록 돕습니다.

GC의 Mark and Sweep과 자바스크립트 메모리 관리

자바스크립트에서 Garbage Collection은 자동으로 일어나지만, GC의 정확한 시점은 예측할 수 없습니다. clear 메서드에서 참조를 명확히 끊는 작업을 함으로써 GC가 보다 효율적으로 불필요한 객체들을 메모리에서 제거할 수 있도록 할 수 있습니다.

GC가 메모리에서 객체를 회수할 수 있도록 돕는 방법:

명시적인 참조 해제: 객체들이 더 이상 사용되지 않을 때, null로 설정하여 참조를 끊어줍니다. 이렇게 하면 GC가 해당 객체들을 회수할 수 있습니다.
불필요한 참조 끊기: 예를 들어, 리스트의 next 참조를 null로 설정하는 작업은 객체 간의 연결을 끊어 GC가 불필요한 객체를 회수하게 하는 중요한 역할을 합니다.

Mark and Sweep 알고리즘은 두 가지 주요 단계(마킹과 청소)로 이루어져 있으며, 자바스크립트의 Garbage Collection에서도 이를 사용하여 더 이상 참조되지 않는 객체를 메모리에서 해제합니다. clear 메서드처럼 명시적으로 참조를 끊는 작업을 통해 GC가 효율적으로 작동할 수 있도록 돕습니다.

5. DoublyLinkedList

양방향 연결 리스트(Doubly Linked List)는 각 노드가 이전 노드와 다음 노드를 참조할 수 있도록 하여, 단방향 연결 리스트(Singly Linked List)의 한계를 극복합니다. 단방향 연결 리스트에서는 노드를 한 방향으로만 탐색할 수 있는 반면, 양방향 연결 리스트는 양쪽 방향 모두에서 탐색할 수 있어 효율적인 연산이 가능합니다.

Doubly Linked List의 구조

DoublyLinkedList는 기본적으로 두 개의 클래스로 구성됩니다. 첫 번째 클래스는 LinkedNode로, 이 클래스는 리스트 내의 개별 노드를 표현합니다. 두 번째 클래스는 DoublyLinkedList로, 이는 연결 리스트를 관리하고 탐색, 삽입, 삭제 등의 기능을 제공합니다.

1. LinkedNode Class

LinkedNode 클래스는 리스트 내의 개별 노드를 나타냅니다. 각 노드는 data, prev, next의 세 가지 속성을 가집니다. data는 노드의 실제 데이터를 담고 있으며, prev는 이전 노드를, next는 다음 노드를 가리킵니다.


class LinkedNode<TValue> {

  prev: LinkedNode<TValue> | null = null;

  next: LinkedNode<TValue> | null = null;

  data: TValue;



  constructor(data: TValue, prevNode: LinkedNode<TValue> | null = null, nextNode: LinkedNode<TValue> | null = null) {

    this.data = data;

    this.prev = prevNode;

    this.next = nextNode;

  }

}

2. DoublyLinkedList Class

DoublyLinkedList 클래스는 전체 리스트를 관리하며, 노드의 삽입, 삭제, 탐색 기능을 제공합니다. 이 클래스는 head, tail, 그리고 리스트의 크기를 나타내는 count와 같은 기본 속성을 유지합니다.


export class DoublyLinkedList<TValue> {

  private _count: number = 0;

  private _head: LinkedNode<TValue> | null = null;

  private _tail: LinkedNode<TValue> | null = null;



  public addFirst(data: TValue): void {

    const newNode = new LinkedNode(data);

    if (this._head) {

      newNode.next = this._head;

      this._head.prev = newNode;

    } else {

      this._tail = newNode;

    }

    this._head = newNode;

    this._count++;

  }



  public addLast(data: TValue): void {

    const newNode = new LinkedNode(data);

    if (this._tail) {

      this._tail.next = newNode;

      newNode.prev = this._tail;

    } else {

      this._head = newNode;

    }

    this._tail = newNode;

    this._count++;

  }



  public removeFirst(): TValue | null {

    if (!this._head) return null;

    const data = this._head.data;

    this._head = this._head.next;

    if (this._head) this._head.prev = null;

    else this._tail = null; // 리스트가 비었을 경우

    this._count--;

    return data;

  }



  public removeLast(): TValue | null {

    if (!this._tail) return null;

    const data = this._tail.data;

    this._tail = this._tail.prev;

    if (this._tail) this._tail.next = null;

    else this._head = null; // 리스트가 비었을 경우

    this._count--;

    return data;

  }



  public find(data: TValue): LinkedNode<TValue> | null {

    let currentNode = this._head;

    while (currentNode) {

      if (currentNode.data === data) return currentNode;

      currentNode = currentNode.next;

    }

    return null;

  }

}

제네릭(Generic)을 통한 유연성

DoublyLinkedList 클래스에서 제네릭 타입 TValue를 사용하여, 다양한 타입의 데이터를 저장할 수 있도록 설계했습니다. 이를 통해 정수, 문자열, 객체 등 어떤 형태의 데이터도 연결 리스트에 저장할 수 있습니다.


const stringList = new DoublyLinkedList<string>();

stringList.addFirst("Hello");

stringList.addLast("World");



const numberList = new DoublyLinkedList<number>();

numberList.addFirst(10);

numberList.addLast(20);

전체코드


// LinkedNode 클래스는 Doubly Linked List에서 각 노드를 나타냅니다.

class LinkedNode<TValue> {

  prev: LinkedNode<TValue> | null = null;  // 이전 노드를 가리키는 포인터

  next: LinkedNode<TValue> | null = null;  // 다음 노드를 가리키는 포인터

  data: TValue; // 노드에 저장될 데이터



  // 생성자: data, prevNode(이전 노드), nextNode(다음 노드)로 초기화

  constructor(data: TValue);



  constructor(data: TValue, prevNode: LinkedNode<TValue>, nextNode: LinkedNode<TValue>);



  constructor(data: TValue, prevNode: LinkedNode<TValue> | null = null, nextNode: LinkedNode<TValue> | null = null) {

    this.data = data;  // 데이터 설정

    this.next = nextNode;  // 다음 노드 연결

    this.prev = prevNode;  // 이전 노드 연결

  }

}



// DoublyLinkedList 클래스는 양방향 연결 리스트를 구현합니다.

export class DoublyLinkedList<TValue> implements Iterable<TValue> {

  private _count: number;  // 리스트의 노드 개수를 추적

  private _head: LinkedNode<TValue> | null;  // 리스트의 첫 번째 노드 (head)

  private _tail: LinkedNode<TValue> | null;  // 리스트의 마지막 노드 (tail)

  private _comparer: IEqualityComparer<TValue>;  // 데이터 비교를 위한 comparer



  // 생성자: comparer가 제공되지 않으면 기본 comparer(DefaultGenericComparer)를 사용

  public constructor(comparer: IEqualityComparer<TValue> | null = null) {

    this._count = 0;  // 노드 개수 초기화

    this._head = null;  // head 초기화

    this._tail = null;  // tail 초기화

    this._comparer = comparer ?? DefaultGenericComparer;  // comparer 설정

  }



  // 리스트의 노드 개수를 반환

  public get count(): number {

    return this._count;

  }



  // 리스트의 첫 번째 노드를 반환

  public get first(): LinkedNode<TValue> | null {

    return this._head;

  }



  // 리스트의 마지막 노드를 반환

  public get last(): LinkedNode<TValue> | null {

    return this._tail;

  }



  // 첫 번째 위치에 노드를 추가

  public addFirst(data: TValue): void {

    const newNode = new LinkedNode(data);



    if (this._head !== null) {

      newNode.next = this._head;  // 기존 head와 새 노드를 연결

      this._head.prev = newNode;  // 새 노드를 기존 head의 prev로 연결

    } else {

      this._tail = newNode;  // 리스트가 비어있으면 tail도 새 노드로 설정

    }



    this._head = newNode;  // 새 노드를 head로 설정

    this._count++;  // 노드 개수 증가

  }



  // 마지막 위치에 노드를 추가

  public addLast(data: TValue): void {

    const newNode = new LinkedNode(data);



    if (this._tail !== null) {

      this._tail.next = newNode;  // 기존 tail과 새 노드를 연결

      newNode.prev = this._tail;  // 새 노드를 기존 tail의 prev로 연결

    } else {

      this._head = newNode;  // 리스트가 비어있으면 head도 새 노드로 설정

    }



    this._tail = newNode;  // 새 노드를 tail로 설정

    this._count++;  // 노드 개수 증가

  }



  // 첫 번째 노드를 제거하고 그 값을 반환

  public removeFirst(): TValue | null {

    let result: TValue | null = null;



    if (this._head !== null) {

      result = this._head.data;  // head의 데이터를 result에 저장

      this.remove(this._head);  // head 노드를 삭제

    }



    return result;  // 삭제된 노드의 데이터 반환

  }



  // 마지막 노드를 제거하고 그 값을 반환

  public removeLast(): TValue | null {

    let result: TValue | null = null;



    if (this._tail !== null) {

      result = this._tail.data;  // tail의 데이터를 result에 저장

      this.remove(this._tail);  // tail 노드를 삭제

    }



    return result;  // 삭제된 노드의 데이터 반환

  }



  // 주어진 노드나 데이터를 리스트에서 삭제

  public remove(value: TValue | LinkedNode<TValue>): void {

    if (value instanceof LinkedNode) {

      this.removeNode(value);  // LinkedNode 타입이면 removeNode 호출

    } else {

      this.removeData(value);  // TValue 타입이면 removeData 호출

    }

  }



  // 데이터를 가진 노드를 삭제

  private removeData(data: TValue): void {

    let currentNode = this._head;



    while (currentNode !== null) {

      if (this._comparer.equals(currentNode.data, data)) {

        this.removeNode(currentNode);  // 데이터가 일치하는 노드 삭제

        return;  // 첫 번째 일치하는 노드만 삭제

      }



      currentNode = currentNode.next;  // 다음 노드로 이동

    }



    throw new Error("Data not found in the list.");  // 데이터가 없으면 오류 발생

  }



  // 노드를 삭제

  private removeNode(node: LinkedNode<TValue>): void {

    if (node === this._head) {

      this._head = node.next;  // 삭제된 노드가 head이면 head를 갱신

      if (this._head !== null) {

        this._head.prev = null;  // 새로운 head의 prev를 null로 설정

      }

    } else {

      if (node.prev) {

        node.prev.next = node.next;  // 이전 노드의 next를 삭제된 노드의 next로 설정

      }

    }



    if (node === this._tail) {

      this._tail = node.prev;  // 삭제된 노드가 tail이면 tail을 갱신

      if (this._tail !== null) {

        this._tail.next = null;  // 새로운 tail의 next를 null로 설정

      }

    } else {

      if (node.next) {

        node.next.prev = node.prev;  // 다음 노드의 prev를 삭제된 노드의 prev로 설정

      }

    }



    node.prev = null;

    node.next = null;  // 삭제된 노드의 연결 해제



    this._count--;  // 노드가 삭제되었으므로 리스트의 크기 감소

  }



  // 앞에서부터 데이터를 찾음

  public find(data: TValue): LinkedNode<TValue> | null {

    let node = this._head;

    while (node !== null) {

      if (this._comparer.equals(node.data, data)) {

        return node;  // 일치하는 노드를 반환

      }

      node = node.next;  // 다음 노드로 이동

    }

    return null;  // 찾지 못한 경우 null 반환

  }



  // 뒤에서부터 데이터를 찾음

  public findLast(data: TValue): LinkedNode<TValue> | null {

    for (let node = this._tail; node !== null; node = node.prev) {

      if (this._comparer.equals(node.data, data)) {

        return node;  // 일치하는 노드를 반환

      }

    }

    return null;  // 찾지 못한 경우 null 반환

  }



  // 데이터가 리스트에 포함되어 있는지 확인

  public contains(data: TValue): boolean {

    for (let node = this._head; node !== null; node = node.next) {

      if (this._comparer.equals(node.data, data)) {

        return true;  // 일치하는 데이터를 찾으면 true 반환

      }

    }

    return false;  // 데이터가 없으면 false 반환

  }



  // 리스트의 모든 데이터를 비우고 count를 0으로 설정

  public clear(): void {

    while (this._head !== null) {

      const nextNode = this._head.next;

      this._head.next = null;  // 노드의 next 참조를 해제

      this._head = nextNode;   // head를 다음 노드로 갱신

    }



    this._tail = null;  // tail을 null로 설정

    this._count = 0;    // 리스트의 크기를 0으로 설정

  }



  // 리스트의 데이터를 배열로 반환

  public toArray(): TValue[] {

    const arr: TValue[] = [];

    let current = this._head;



    while (current !== null) {

      arr.push(current.data);  // 데이터를 배열에 추가

      current = current.next;  // 다음 노드로 이동

    }

    return arr;  // 배열 반환

  }



  // 반복자를 제공하여 리스트를 순회할 수 있게 함

  [Symbol.iterator](): Iterator<TValue> {

    let currentNode = this._head;



    return {

      next(): IteratorResult<TValue> {

        if (currentNode !== null) {

          const value = currentNode.data;

          currentNode = currentNode.next;  // 다음 노드로 이동

          return { value, done: false };  // 값과 done 상태 반환

        }

        return { value: undefined, done: true };  // 리스트 끝에 도달하면 done을 true로 설정

      }

    };

  }

}

6. Stack 구현

위 DoublyLinkedList를 이용하여 stack을 만들려고 합니다. 배열로 stack을 만들지 않는 이유는 이미 내장함수로 구현되어 있기 때문입니다.

arr.pop()

위 코드는 node_module에서 new elements to add to the array를 하는 목적으로 이미 있기 때문에, 그보다 더 유연한 양방향연결리스트를 이용하여 구현하고자 합니다.


//stack.ts

  // 스택에 값을 추가

  public push(item: TValue): void {

    this._linkedList.addLast(item);

  }

이미 구현되어 있는 DoublyLinkedList.addLast(item)은 항상 tail을 이용해서 값을 접근하여 링크드리스트의 마지막에 데이터를 넣는 함수로 코드는 아래와 같습니다. 새로운 노드를 추가할 때,


//doublyLinkedList.ts

  public addLast(data: TValue): void {

    const newNode = new LinkedNode(data);



    if (this._tail !== null) {

      // 기존 _tail과 새 노드를 연결

      this._tail.next = newNode;

      newNode.prev = this._tail;

    } else {

      // 리스트가 비어 있는 경우 _head도 새 노드로 설정

      this._head = newNode;

    }



    // 새 노드를 _tail로 설정

    this._tail = newNode;

    this._count++;

  }

새 노드 생성: 새 노드를 만들어 데이터 값을 설정합니다.

리스트 비었는지 확인: 현재 tail이 null인지 확인하여 리스트가 비었는지 판단합니다.

기존 Tail과 새 노드 연결: 리스트가 비어 있지 않다면, 기존 tail 노드의 next 포인터를 새 노드로 설정하고, 새 노드의 prev 포인터를 기존 tail로 설정합니다.

리스트 비었으면 새 노드를 Head로 설정: 만약 리스트가 비어 있었다면, 새 노드를 head로 설정합니다.

새 노드를 Tail로 설정: 새 노드를 tail로 설정합니다.

리스트 크기 증가: 노드를 추가했으므로 리스트의 크기를 증가시킵니다.

이런 방식으로 데이터가 추가되는 리스트를 스택으로 push로 사용하게 되면 pop 같은 경우에는 가장 마지막에 있는 tail 값을 이용하여 맨 뒤에 값이 먼저 호출이 되어야합니다. 그렇기때문에


// stack.ts

  // 스택에서 값을 제거하고 반환

  public pop(): TValue {

    const removedItem = this._linkedList.removeLast();

    if (removedItem === null) {

      throw new Error("Stack is empty");

    }

    return removedItem;

  }

이렇게 구현할 수 있는데, this._linkedList.removeLast()를 조금 살펴보자면


//doublyLinkedList.ts

  public removeLast(): TValue | null {

    let result: TValue | null = null;



    if (this._tail !== null) {

      //TODO: tail이 가지고 있는 값을 result에 설정한 후 tail 노드를 삭제.

      result = this._tail.data

      this.remove(this._tail)

    }



    return result;

  }

this.remove(this._tail)은 remove 메소드를 호출하여 tail 노드를 삭제합니다.

remove는 LinkedNode 또는 TValue에 따라 다른 방식으로 동작하며, 주로 removeNode 메소드 또는 removeData 메소드를 호출하여 실제로 노드를 삭제합니다.

stack.ts 및 테스트 코드


import { DoublyLinkedList } from "./DoublyLinkedList.js";



export class Stack<TValue> implements Iterable<TValue> {

  private _linkedList: DoublyLinkedList<TValue>;



  public constructor() {

    this._linkedList = new DoublyLinkedList();

  }



  public get count(): number {

    return this._linkedList.count;

  }



  // 데이터를 꺼내지 않고 가장 마지막에 들어간 값을 반환

  public peek(): TValue {

    if (this._linkedList.last === null) {

      throw new Error("Stack is empty");

    }

    return this._linkedList.last.data;

  }



  // 스택에 값을 추가

  public push(item: TValue): void {

    this._linkedList.addLast(item);

  }



  // 스택에서 값을 제거하고 반환

  public pop(): TValue {

    const removedItem = this._linkedList.removeLast();

    if (removedItem === null) {

      throw new Error("Stack is empty");

    }

    return removedItem;

  }



  // 스택을 배열로 변환

  public toArray(): TValue[] {

    return this._linkedList.toArray();

  }



  // 스택을 비움

  public clear(): void {

    this._linkedList.clear();

  }



  // 반복자(iterator) 구현

  [Symbol.iterator](): Iterator<TValue> {

    return this._linkedList[Symbol.iterator]();

  }

}



/*------------------------jest를 활용한 테스트 코드--------------------*/

// stack 자체의 push, pop, peek(LastIndexValue return) 테스트

// stack.method()는 비동기 처리이기때문에, stack.pop()와 peek() 처리 조심심

/*--------------------------------------------------------------------*/



describe("Stack_test", () => {

  const stack = new Stack<number>();

  stack.push(10);

  stack.push(20);

  stack.push(30);



  it("Stack push Test", () => expect(stack.toArray()).toEqual([10, 20, 30]));



  it("Stack peek test", () => expect(stack.peek()).toEqual(30));



  it("Stack pop Test", () => {

    stack.pop();

    return  expect(stack.toArray()).toEqual([10, 20]);

  });



});

7. Queue 구현

Queue도 Stack 처럼 마찬가지로 DoublyLinkedList를 이용하여 코드 재사용성을 높이고자 했습니다.

전체코드


import { DoublyLinkedList } from "./DoublyLinkedList.js";



export class Queue<TValue> implements Iterable<TValue> {

  private _linkedList: DoublyLinkedList<TValue>;



  public constructor() {

    this._linkedList = new DoublyLinkedList();

  }



  // 큐의 크기를 반환

  public get count(): number {

    return this._linkedList.count;

  }



  // 큐에 데이터를 추가

  public enqueue(item: TValue): void {

    this._linkedList.addLast(item);

  }



  // 큐에서 데이터를 제거하고 반환

  public dequeue(): TValue {

    const removedItem = this._linkedList.removeFirst(); // FIFO이므로 첫 번째 데이터 제거

    if (removedItem === null) {

      throw new Error("Queue is empty"); // 큐가 비어 있으면 예외 발생

    }

    return removedItem;

  }



  // 큐의 첫 번째 데이터를 반환 (제거하지 않음)

  public peek(): TValue {

    if (this._linkedList.first === null) {

      throw new Error("Queue is empty"); // 큐가 비어 있으면 예외 발생

    }

    return this._linkedList.first.data;

  }



  // 큐를 배열로 변환

  public toArray(): TValue[] {

    return this._linkedList.toArray();

  }



  // 큐를 비움

  public clear(): void {

    this._linkedList.clear();

  }



  // 반복자(iterator) 구현

  [Symbol.iterator](): Iterator<TValue> {

    return this._linkedList[Symbol.iterator]();

  }

}



/*-------------------------------------test code-------------------------------------------------*/

//////////////////////////////////////////////////////////////////////////////////////////////////

// describe를 하나로 통일해서 beforEach를 통해 새로운 Queue instance를 만들고 Queue 테스트 코드작성///

//////////////////////////////////////////////////////////////////////////////////////////////////

/*----------------------------------------------------------------------------------------------*/

import { Queue } from "../data_structure/Queue.js";

describe("Queue Tests", () => {

    let queue;

    // 각 테스트 전에 새로운 Queue 인스턴스 생성

    beforeEach(() => {

        queue = new Queue();

    });

    it("should enqueue elements correctly", () => {

        queue.enqueue(10);

        queue.enqueue(20);

        queue.enqueue(30);

        expect(queue.toArray()).toEqual([10, 20, 30]); // 큐에 추가된 요소 확인

    });

    it("should dequeue elements in FIFO order", () => {

        queue.enqueue(10);

        queue.enqueue(20);

        queue.enqueue(30);

        expect(queue.dequeue()).toBe(10); // 가장 먼저 추가된 10이 제거

        expect(queue.toArray()).toEqual([20, 30]); // 나머지 요소 확인

        expect(queue.dequeue()).toBe(20); // 다음 요소 제거

        expect(queue.toArray()).toEqual([30]);

        expect(queue.dequeue()).toBe(30); // 마지막 요소 제거

        expect(queue.count).toBe(0); // 큐가 비어 있음

    });

    it("should peek the first element without removing it", () => {

        queue.enqueue(10);

        queue.enqueue(20);

        queue.enqueue(30);

        expect(queue.peek()).toBe(10); // 첫 번째 요소 확인

        expect(queue.toArray()).toEqual([10, 20, 30]); // 요소가 제거되지 않음

    });

    it("should clear all elements", () => {

        queue.enqueue(10);

        queue.enqueue(20);

        queue.enqueue(30);

        queue.clear();

        expect(queue.count).toBe(0); // 큐가 비어 있음

        expect(queue.toArray()).toEqual([]); // 요소가 없음

    });

    it("should throw an error when dequeuing from an empty queue", () => {

        expect(() => queue.dequeue()).toThrow("Queue is empty"); // 비어 있는 큐에서 제거 시 예외 발생

    });

    it("should throw an error when peeking into an empty queue", () => {

        expect(() => queue.peek()).toThrow("Queue is empty"); // 비어 있는 큐에서 조회 시 예외 발생

    });

    it("should be iterable", () => {

        queue.enqueue(10);

        queue.enqueue(20);

        queue.enqueue(30);

        const result = [];

        for (const value of queue) {

            result.push(value);

        }

        expect(result).toEqual([10, 20, 30]); // 반복자를 통해 모든 요소를 순회

    });

});

8. 피드백(method 반환값의 대한 처리 중 undefined, throw 등 타입가드 및 유니온 타입의 처리의 대한 고찰)


type FindResult = { success: true; value: string } | { success: false; error: string };



class ItemFinder {

  private items: string[];



  constructor(items: string[]) {

    this.items = items;

  }



  // 1. `undefined`를 반환

  findOrUndefined(target: string): string | undefined {

    return this.items.find(item => item === target);

  }



  // 2. 예외를 던짐

  findOrThrow(target: string): string {

    const item = this.items.find(item => item === target);

    if (!item) throw new Error(`Item "${target}" not found`);

    return item;

  }



  // 3. 유니온 타입 반환

  findWithResult(target: string): FindResult {

    const item = this.items.find(item => item === target);

    if (!item) {

      return { success: false, error: `Item "${target}" not found` };

    }

    return { success: true, value: item };

  }



  // 4. 타입 가드를 이용한 안전 처리

  static isSuccess(result: FindResult): result is { success: true; value: string } {

    return result.success;

  }

}



// 사용 예

const finder = new ItemFinder(['apple', 'banana', 'cherry']);



// 1. `undefined` 반환

const result1 = finder.findOrUndefined('banana');

if (result1 !== undefined) {

  console.log(`Found: ${result1}`);

} else {

  console.log('Item not found');

}



// 2. 예외 처리

try {

  const result2 = finder.findOrThrow('grape');

  console.log(`Found: ${result2}`);

} catch (error) {

  console.error(error.message);

}



// 3. 유니온 타입 처리

const result3 = finder.findWithResult('cherry');

if (ItemFinder.isSuccess(result3)) {

  console.log(`Found: ${result3.value}`);

} else {

  console.error(`Error: ${result3.error}`);

}

undefined 반환 방식

간단한 데이터 탐색에서 직관적으로 사용할 수 있지만, 호출자가 반드시 undefined를 확인해야 한다는 부담이 있다.

예외를 던지지 않으므로 호출자 입장에서 안전한 선택이나, 반환값의 의미가 명확하지 않아 디버깅 시 혼란을 줄 수 있다.

예외(throw) 방식

오류 상황을 강력하게 표현할 수 있지만, try-catch를 통해 모든 호출에서 예외 처리를 강제해야 하므로 코드가 복잡해질 가능성이 있다.

흐름 제어가 예외로 끊어지기 때문에 일반적인 탐색보다는 치명적 오류 상황에서 적합하다.

유니온 타입과 타입 가드

success와 error를 분리해 결과를 명확히 표현하므로, 호출자가 상황에 맞는 처리를 쉽게 할 수 있다.

타입 가드를 통해 안전하게 동작하지만, 구조가 복잡해질 수 있으므로 간단한 메서드에는 과도한 설계가 될 가능성도 있다.

9. JavaScript Array 특징, Hash 및 Array-like 개념

1. JavaScript Array 특징

JavaScript에서 배열은 동적 배열(Dynamic Array)로 취급되며, 다양한 데이터 유형을 담을 수 있는 자료구조입니다. 배열은 사실 객체의 일종이며, 배열의 인덱스가 문자열 키로 자동 변환되어 저장됩니다.

특징

인덱싱 (Indexing): JavaScript 배열은 0부터 시작하는 정수 인덱스를 통해 접근합니다.
동적 크기 조정: JavaScript 배열은 동적 크기를 가지며, 배열의 크기는 자동으로 조정됩니다. 즉, 배열의 길이를 신경 쓸 필요 없이 push(), pop(), shift(), unshift()와 같은 메서드를 통해 요소를 추가하거나 제거할 수 있습니다.
다양한 타입 저장: JavaScript 배열은 다른 언어에서와 달리 다양한 데이터 타입을 같은 배열에 저장할 수 있습니다. 예를 들어, 숫자, 문자열, 객체, 함수 등을 동일한 배열에 담을 수 있습니다.
객체 기반: 배열은 사실 객체입니다. 배열의 인덱스는 키로 취급되며, 배열 메서드는 배열 객체의 메서드로 정의됩니다.
배열 메서드: JavaScript 배열은 map(), filter(), reduce()와 같은 고차 함수(Higher-order Function)를 제공하며, 이는 함수형 프로그래밍 스타일의 코드 작성을 가능하게 합니다.
배열의 최적화: 배열에 요소가 추가되거나 삭제되면 내부적으로 리사이징이 발생할 수 있습니다. 배열의 크기가 커지거나 작아질 때 성능에 영향을 미칠 수 있습니다.

예시


let arr = [1, 2, 3];  // 동적 배열

arr.push(4);           // 배열 크기 자동 증가

console.log(arr);      // [1, 2, 3, 4]

2. JavaScript의 Hash

JavaScript에서 Hash 또는 Hash Table은 키-값 쌍을 관리하는 자료구조입니다. 각 키는 고유해야 하며, 해당 키에 연결된 값을 효율적으로 찾고, 추가하고, 삭제할 수 있습니다. Hash는 기본적으로 JavaScript 객체에서 구현되어 있으며, ES6부터 Map 객체가 도입되어, 더 강력하고 효율적인 Hash 기능을 제공합니다.

특징

키-값 쌍: Hash는 키(key)와 값(value)의 쌍으로 이루어진 자료구조입니다. 키는 고유해야 하며, 값을 빠르게 조회할 수 있습니다.
해시 함수: Hash 구조는 내부적으로 해시 함수를 사용하여 키를 특정 값으로 변환하고, 이 값으로 빠른 검색을 지원합니다.
중복 불가: 키는 유일해야 하며, 같은 키를 두 번 사용할 수 없습니다. 만약 같은 키로 값을 추가하면 기존 값이 덮어씌워집니다.
객체와의 차이: Map은 JavaScript 객체와 비슷하지만, 더 많은 유용한 기능을 제공합니다. 예를 들어, 객체의 키는 항상 문자열이지만, Map의 키는 다양한 데이터 타입을 가질 수 있습니다.
순서 보장: Map은 삽입 순서를 보장하는 반면, 객체는 삽입 순서를 보장하지 않습니다(단, ES6 이후에는 객체도 삽입 순서를 보장합니다).

HashTable 예시


// 객체 기반의 Hash

let hash = {};

hash["key1"] = "value1";

hash["key2"] = "value2";

console.log(hash["key1"]);  // value1



// ES6 Map을 사용한 Hash

let map = new Map();

map.set("key1", "value1");

map.set("key2", "value2");

console.log(map.get("key1"));  // value1

3. Array-like 객체

Array-like 객체는 배열처럼 인덱스를 통해 값에 접근하고, 길이(length) 속성을 가지고 있지만, 실제 배열이 아닌 객체를 의미합니다. 이 객체는 배열과 유사하게 동작할 수 있지만 배열 메서드(예: map(), filter(), forEach() 등)는 제공하지 않습니다.

특징

인덱스와 length 속성: Array-like 객체는 배열과 마찬가지로 숫자 인덱스를 사용하여 요소에 접근할 수 있으며, length 속성을 가집니다.
배열 메서드 없음: Array-like 객체는 배열 메서드를 지원하지 않기 때문에, 배열 메서드를 사용하려면 Array.prototype을 활용하거나 명시적으로 배열로 변환해야 합니다.
배열처럼 사용할 수 있으나 진짜 배열은 아님: Array-like 객체는 배열처럼 동작할 수 있지만, 실제로는 일반 객체로 취급됩니다.

예시


// Arguments 객체 (Array-like)

function example() {

  console.log(arguments);  // Arguments 객체는 Array-like

  console.log(arguments[0]);  // 1

  console.log(arguments.length);  // 3

}

example(1, 2, 3);



// NodeList (Array-like)

let divs = document.querySelectorAll('div');

console.log(divs instanceof NodeList);  // true

console.log(divs[0]);  // 첫 번째 div 요소

console.log(divs.length);  // NodeList의 길이

배열처럼 사용하기

Array-like 객체는 배열 메서드를 사용할 수 없으므로, Array.from() 또는 스프레드 연산자(...)를 사용하여 배열로 변환할 수 있습니다.


// Array-like 객체를 배열로 변환

let arrayLike = {0: "apple", 1: "banana", length: 2};

let arr = Array.from(arrayLike);

console.log(arr);  // ["apple", "banana"]

4. JavaScript의 Hash와 Array의 차이점

특성	Array	Hash (Object or Map)	Array-like
구조	순차적 인덱스로 접근	키-값 쌍으로 접근	숫자 인덱스와 `length` 속성 가진 객체
인덱스/키	숫자 인덱스 (0부터 시작)	문자열, 숫자, 객체 등 다양한 키	숫자 인덱스 (배열처럼 접근)
검색 시간	인덱스를 통한 빠른 접근	해시값을 통한 빠른 키 검색	배열처럼 인덱스로 접근 가능하지만 배열 메서드 없음
순서 보장	삽입 순서대로 저장	`Map`은 삽입 순서를 보장, 객체는 보장되지 않음	인덱스 순서대로 저장
변경 가능성	요소를 동적으로 추가/삭제 가능	키-값 쌍을 동적으로 추가/삭제 가능	변경은 가능하지만 배열 메서드는 없음
메모리 효율성	고정된 크기 및 동적 크기 확장 가능	키-값 쌍 저장, 고정 크기 없음	배열처럼 크기 동적 조정, 메서드 없음
사용 예	리스트, 큐, 스택 등	객체 기반 데이터 저장, 키 기반 검색	DOM 노드 리스트, Arguments 객체 등

참고링크

가비지 컬렉션의 관하여

심볼 테이블에 관하여

회사에서 사용하는 해시 로직에 대하여

728x90