[JavaScript] Data Structure - Linked List, Hash Table

Reference - 코드 스테이츠 이머시브 코스 - Data Structure 강의, Wikipedia

연결 리스트 (Linked List)

Linked List는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되는 방식으로 데이터를 저장하는 자료구조이다. 

 

실생활에 쓰이는 연결 리스트의 예

 

• 유튜브의 플레이리스트
• 포토샵의 Undo, Redo
• 웹의 되돌아가기 버튼

 

연결 리스트(Linked List)의 세 가지 종류

 

• 단일 연결 리스트 (Singly Linked List)
  
  각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

• 이중 연결리스트 (Doubly Linked List)
  
  단일 연결 리스트와 비슷하지만 각 노드에 두 개의 포인터가 존재하고 각각의 포인터는 해당 노드의 앞의 노드와 뒤의 노드를 가리킨다.

• 원형 연결리스트 (Circular Linked List)
  
  일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다. 

단일 연결리스트 (Singly Linked List) 구현하기

노드와 연결 리스트 틀 구현

 

class Node {
  constructor(value) {
    this.value = value; 
    this.next = null; // 다음노드를 저장하는 변수
  }
}

class LinkedList {
  constructor() {
    this.head = null; 
    this.tail = null;
    this._size = 0; // 리스트안의 노드 갯수를 나타냄.
  }
}

 

LinkedList 클래스 안에 메소드들 구현

 

1. addToTail(value) - 주어진 값을 연결 리스트의 끝에 추가함.

 

addToTail(value) {
    let addValue = new Node(value)
    if (this.head === null && this.tail === null) {
      this.head = addValue; 
      this.tail = addValue;
    }
    if (this.head !== null) {
      this.tail.next = addValue;
      this.tail = addValue;
    }
    this._size++
  }

 

 

2. remove(value) - 주어진 값을 찾아서 연결을 해제(삭제).

 

remove(value) {
	// 데이터가 비어있으므로 undefined 반환
    if (this.head === null) {
      return undefined;
    }
    // 리스트의 처음의 값이 찾는 값과 같다면
    if (this.head.value === value) {
    // this. head를 다음 노드로 지정하여 아무도 가리키지 않게 만들어 가비지콜렉터에 추가
      this.head = this.head.next;
      this._size--
    }
    let preNode = this.head;
    let curNode = this.head.next;
    // 리스트의 중간에 찾는 값이 존재하는지 확인
    // 찾는 값이 리스트에 없다면 curNode가 tail.next가 되면 null이므로 루프 종료됨.
    while (curNode) {
      if (curNode.value === value) {
        preNode.next = curNode.next
        this._size--
        break
      }
      else {
      // 찾는 값이 나올때까지 다음노드로 초기화됨.
        preNode = curNode;
        curNode = curNode.next;
      }
    }
  }

 

 

3. getNodeAt(index) - 주어진 인덱스의 노드를 찾아서 반환. 해당 인덱스에 노드가 없다면 undefined를 반환.

 

getNodeAt(index) {
    // 리스트의 처음부터 탐색함
    let headNode = this.head;
    // 인덱스 넘버가 리스트의 크기를 초과한다면 undefined.
    if (index > this._size) {
      return undefined
    }
    else {
    // 인덱스 넘버에 도달할때까지 루프함.
      for (let i = 0; i < index; i++) {
      	// 다음 노드로 계속 초기화됨.
        headNode = headNode.next
      }
      return headNode;
    }
  }

 

 

4. contains(value) - 연결 리스트에 주어진 값을 가지는 노드의 존재 여부를 반환

 

contains(value) {
    // 리스트의 처음부터 탐색함.
    let curNode = this.head;
    // 리스트에 값이 존재하지 않는다면 curNode는 null이 되므로 while루프는 종료되고 false가 리턴됨.
    while (curNode) {
      if (curNode.value === value) {
        return true
      }
      else {
      // 값을 찾을때까지 다음 노드로 초기화.
        curNode = curNode.next
      }
    }
    return false
  }

 

 

5. indexOf(value) - 주어진 값의 인덱스를 반환함. 없을 경우 -1을 반환함.

 

indexOf(value) {
    // 리스트의 처음부터 탐색.
    let curNode = this.head;
    let count = 0
    while (curNode) {
    // 값을 찾는다면 count 횟수를 리턴.
      if (curNode.value === value) {
        return count
      }
      else {
        curNode = curNode.next
      }
      // 값을 찾을때까지 count는 누적됨. 
      count++
    }
    return -1
  }

 

 

6. size() - 연결 리스트의 크기를 반환

 

  size() {
    return this._size
  }

 

 

해시 테이블 (Hash Table)

해시함수를 이용한 전화번호부, John Smith'라는 스트링이 해싱되어 02가 됨

Hash Table는 해시 함수를 사용하여 원하는 값을 찾을 수 있는 인덱스를 만든다. 조회를 할 때도 키가 해시 함수를 통하여 해시화 되고 해시화된 키는 해당 값이 저장된 위치를 나타낸다.

Hash, Hashing, Hash Table(해시, 해싱 해시테이블) 자료구조의 이해

위 링크에 해시 테이블에 대해 잘 설명되어 있다.

 

 

해시 테이블 (Hash Table) 구현하기

자바스크립트에는 이미 크기가 동적인 배열이 존재하나 이를 사용하지 않고

배열의 인덱스가 한정적인 LimitedArray를 사용함.

 

구현할 때 주의해야 할 점

• 해시테이블에 데이터가 25% ~ 75% 차 있을 때 가장 효율이 좋으므로 데이터의 사이즈가 75%를 넘는다면 배열의 크기를 늘리고, 테이블의 데이터를 지웠을 때 데이터의 사이즈가 25% 미만이라면 배열의 크기를 줄여야 함.
• 키를 해싱했을 때 중복 값이 나타나는 충돌되는 경우가 있다.(collision) 이를 어떤 방법으로 해결할 것인가.

 

limitedArray의 구현

 

/*
 ********** NOTE: **********
 * Do not edit this code unless you see a bug!
 */

// This class represents an array with limited functionality and a maximum size.
// It will ensure that you don't accidentally try to use up too much space.
//
// Usage:
//   limitedArray.set(3, 'hi')
//   limitedArray.get(3) // returns 'hi'

const LimitedArray = function(limit) {
  const storage = [];

  const limitedArray = {};
  limitedArray.get = function(index) {
    checkLimit(index);
    return storage[index];
  };
  limitedArray.set = function(index, value) {
    checkLimit(index);
    storage[index] = value;
  };
  limitedArray.each = function(callback) {
    for (let i = 0; i < storage.length; i++) {
      callback(storage[i], i, storage);
    }
  };

  var checkLimit = function(index) {
    if (typeof index !== 'number') {
      throw new Error('setter requires a numeric index for its first argument');
    }
    if (limit <= index) {
      throw new Error('Error trying to access an over-the-limit index');
    }
  };

  return limitedArray;
};

 

 

해시 테이블의 생성자

 

class HashTable {
  constructor() {
    this._size = 0;
    this._limit = 8;
    this._storage = LimitedArray(this._limit);
  }
}

 

 

해시 테이블의 메소드 구현

 

1. insert(key, value) - 주어진 키와 값을 저장. 이미 해당 키가 저장되어 있다면 값을 덮어 씌움.

 

insert(key, value) {
    // 데이터의 용량이 75%가 넘는다면 배열의 크기를 두배로 리사이징.
    if (this._size >= (this._limit * 0.75)) {
      this._resize(this._limit * 2);
    }
    // index는 해싱된 key
    const index = hashFunction(key, this._limit);
    let bucket = [];
    // 중복값이 나타났을 때를 대비해 해싱되기 전 키를 넣어줌.
    let tuple = [key, value];

    if (!this._storage[index]) {
      // 새로 넣어주는 부분
      bucket.push(tuple);
      this._storage[index] = bucket;
    } else {
      for (let t of this._storage[index]) {
        if (t[0] === key) {
          // key까지 같으면 overwrite
          t[1] = value;
        } else {
          // collision이 일어났을 때 push
          this._storage[index].push(tuple);
        }
      }
    }
    this._size++;
  }

 

 

2. retrieve(key) - 주어진 키에 해당하는 값을 반환함. 없다면 undefined를 반환.

 

retrieve(key) {
    const index = hashFunction(key, this._limit);
    for (let t of this._storage[index]) {
      if (t[0] === key) {
        return t[1];
      }
    }
  }

 

 

3. remove(key) - 주어진 키에 해당하는 값을 삭제하고 값을 반환함. 없다면 undefined를 반환.

 

remove(key) {
    // 데이터 용량이 25%미만이라면 배열 크기를 줄임.
    if (this._size <= (this._limit * 0.25)) {
      this._resize(this._limit / 2);
    }
    
    let result = undefined
    const index = hashFunction(key, this._limit);
    let bucket = this._storage[index];
    
    if (bucket) {
      for (let t of bucket) {
        if (t[0] === key) {
        // 해당 키를 제거하고 결과에 값을 담아줌. 
          result = bucket.splice(bucket.indexOf(t), 1);
        }
      }
    }
    this._size--;
    return result;
  }

 

 

4. _resize(newLimit) - 해시 테이블의 스토리지 배열을 newLimit으로 리사 이징하는 함수. 리사이징 후 저장되어 있던 값을 전부 다시 해싱을 해주어야 함.

 

_resize(newLimit) {
    let prevStorage = this._storage;
    this._limit = newLimit;
    this._storage = LimitedArray(newLimit);

    for (let i in prevStorage) {
      this._storage[i] = prevStorage[i];
    }
  }