TIL. 2020–09-06(Linked list, HashTable)

Paul Harvey
3 min readSep 6, 2020

--

원리와 구조는 이해했지만 구현해 내는 것이 정말 쉽지 않았던 시간이었다.

1.Linked list

하나의 노드가 존재하고 노드에는 데이터 값과 다음 노드로 연결되는 데이터, 총 2가지의 정보를 가지고 있다. Linked list에는 단일 연결 리스트(single linked list)와 이중 연결 리스트(double linked list)가 존재한다. 우리가 구현하고자 했던 것은 단일 연결 리스트이다. 구현하고자 했던 메소드는 아래와 같다.

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

2. HashTable

해쉬테이블은 키와 값을 가지고 있는 데이터 구조이다. 키와 limited storage가 해쉬 함수를 통과하게 입력하고 length를 벗어나지 않는 범위의 숫자를 뱉어내면 그 숫자와 값을 연결하여 키를 가지고 값을 찾아내는 데이터 구조이다. 해쉬테이블의 강점은 필요할 때만 메모리를 늘리고, 가능한 작은 메모리를 유지한다는 것이 장점이다.

  • insert(key, value) - 주어진 키와 값을 저장합니다. 이미 해당 키가 저장되어 있다면 값을 덮어씌웁니다.
  • retrieve(key) - 주어진 키에 해당하는 값을 반환합니다. 없다면 undefined를 반환합니다.
  • remove(key) - 주어진 키에 해당하는 값을 삭제하고 값을 반환합니다. 없다면 undefined를 반환합니다.
  • _resize(newLimit) - 해시 테이블의 스토리지 배열을 newLimit으로 리사이징하는 함수입니다. 리사이징 후 저장되어 있던 값을 전부 다시 해싱을 해주어야 합니다. 구현 후 HashTable 내부에서 사용하시면 됩니다.

--

--

Paul Harvey
Paul Harvey

No responses yet