[Data Structure] 자바스크립트로 Linked List & Hash Table 구현하기

Linked List(연결 리스트)

연결리스트란 데이터를 저장된 데이터의 메모리가 연결되어있는 자료구조적 형태를 뜻한다. 연결 방식에 따라 단일 연결리스트와 이중 연결리스트로 나뉘어지지만, 이 포스팅에서는 단일 연결 리스트를 다룰것이며, 단일 연결리스트란 전체 리스트의 각 데이터마다 다음번째에 위치한 데이터의 정보를 갖고있는 형태이다.

위의 이미지를 예시로 들자면 리스트에 10, 20, 30, 40 이란 데이터가 들어있고, 각 데이터는 다음 요소를 가리키는 Next와 자신의 정보를 갖고있다. 즉 10의 next요소는 20을 가리킬것이며, 20의 next는 30이 될것이다. 이런식으로 서로 연결되어있기에 연결 리스트라 하는것이다. 또한 마지막 요소같은 경우엔 다음 요소가 없기때문에 null로 처리해준다. 또한 배열과는 다르게 연결리스트에서 데이터를 중간에 삽입하거나 삭제하는경우엔 원하는 위치를 next를 바라보고있는 데이터의 next를 삽입할 데이터 요소로 바꿔주고 삽입한 데이터의 next를 기존에 그 자리에 있던 데이터의 요소로 바꿔주면 된다.

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

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this._size = 0;
    this.list = {};
  }

  addToTail(value) {
    let newNode = new Node(value);
    if (this._size === 0) {
      this.list[newNode.value] = newNode.next;
      this.tail = newNode;
      this.head = newNode;
    } else {
      this.list[this.tail.value] = newNode.value;
      this.list[newNode.value] = newNode.next;
      this.tail = newNode;
      this.head.next = newNode;
    }
    this._size++;
  }

  remove(value) {
    for (let node in this.list) {
      if (this.head.value === value) {
        this.head = this.getNodeAt(this.indexOf(value) + 1);
        this.head.next = this.getNodeAt(this.indexOf(value) + 2);
      }
      if (this.list[node] === value) {
        this.list[node] = null;
      }
      delete this.list[value];
    }
    this._size--;
  }

  getNodeAt(index) {
    let keys = Object.keys(this.list);
    if (index > keys.length) {
      return;
    } else {
      let result = keys[index];
      let node = new Node(Number(result));
      return node;
    }
  }

  contains(value) {
    let values = Object.keys(this.list);
    return values.includes(String(value));
  }

  indexOf(value) {
    let values = Object.keys(this.list);
    return values.indexOf(String(value));
  }

  size() {
    return this._size;
  }
}

module.exports = LinkedList;

• addToTail(value) - 주어진 값을 연결 리스트의 끝에 추가한다.
• remove(value) - 주어진 값을 찾아서 연결을 해제한다.
• getNodeAt(index) - 주어진 인덱스의 노드를 찾아서 반환한다.노드가 없다면 undefined를 반환한다.
• contains(value) - 연결리스트에 주어진 값을 가지는 노드의 존재 여부를 리턴한다.
• indexOf(value) - 주어진 값의 인덱스를 리턴한다. 없을 경우 -1을 리턴한다.

Hash Table

해시 테이블은 키, 값 쌍을 저장하고 있는 자료 구조이다. 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키를 "해시 함수"를 통해 특정 숫자값의 인덱스로 변환하며, 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지하는 특성을 갖고있다.

위 이미지를 예시로 들자면, 이름을 키로, 전화 번호를 저장하는 해쉬 테이블 구조를 만들때 전체 데이터의 크기 (총 인원)를 16명이라고 하면 John Smith를 저장할때, John Smith를 키로 지정한뒤 해당 키를 해시 함수를 통해 고유한 인덱스값으로 변환한 뒤 해당 인덱스에 John Smith의 전화번호를 저장한다.

해시 함수는 다음과 같이, key(string)과 전체 크기를 인자로 받으며, 항상 동일한 결과가 나와야한다.

그러나 해시 함수를 이용해서 데이터를 저장 시 발생할 수 있는 근본적인 문제가
있다. 바로 해시 충돌이다. 예를들어 '1'과 '9'는 해시 함수 결과가 동일하게 1이다. 즉 키가 다름에도 불구하고 동일한 결과가 나오기에 저장 시 충돌이 발생할 수 있다는것이다.

Separate chaining

Separate chaining 방식은 위에서 설명했던 Linked List를 이용하는 방식이다. 각 index에 데이타를 저장하는 Linked list 에 대한 포인터를 가지는 방식이다. 그렇기 때문에 인덱스가 중복 되더라도 먼저 저장된 데이터가 중복될 데이터의 값을 참조하기때문에 같은 인덱스에 여러 데이터를 저장시킬 수 있다. 하단의 구현 코드는 충돌 시 Separate chaining 방식을 처리해서 해결해 주었다.

Open addressing

Open addressing(개방 주소) 방식은 충돌 시 Linked List와 같은 추가적인 메모리 공간을 사용하지 않고, 해시 테이블의 빈 공간을 사용하는 방법으로, 예를들어 해당 인덱스에서 충돌 발생 시 전체 리스트를 탐색 후 비여있는 공간에 해당 값을 저장한다.

• insert(key, value) - 주어진 키와 값을 저장한다.
• retrieve(key) - 주어진 키에 해당하는 값을 반환한다. 없다면 undefined를 반환한다..
• remove(key) - 주어진 키에 해당하는 값을 삭제하고 값을 반환한다. 없다면 undefined를 반환한다.
• _resize(newLimit) - 해시 테이블의 스토리지 배열을 newLimit으로 리사이징한다. 리사이징 후 저장되어 있던 값을 전부 다시 해싱처리를 해준다.