Linked List

그 크기가 동적인 자료구조로, Node(자료구조를 구성하는 요소)의 연결로 이루어진 Data Structure 입니다.

ArrayList와 다르게 element간의 연결을 이용해서 List를 구현한 것입니다.
Node는 실제 정보를 담고 있는 하나의 단위이며, Link는 노드간의 위치정보를 저장하여 서로 연결해줄 수 있는 연결고리입니다.

연결 리스트의 어떠한 임의의 지점에 데이터의 추가와 삭제를 할 경우, O(1) (상수 시간)의 시간 복잡도를 갖습니다. 다만 이 추가와 삭제 속도에 대한 대가로, 연결 리스트의 각 노드는 인덱스를 갖지 않습니다.

연결 리스트 Property

• head, size

연결 리스트 메소드

• find()
  head노드부터 차례로 해당 item을 검색하면서 찾고 찾으면 해당 노드 반환합니다.
• insert()
  find()메서드로 찾은 노드 뒤에 새로운 노드를 연결합니다.
• first()
  head노드부터 차례로 해당 item을 검색하면서 찾고 찾으면 해당 노드 반환합니다.
• append()
  맨 뒤에 노드를 추가합니다.
• next()
  다음에 연결할 노드 검색합니다.
• delete()
  현재 해당 노드를 삭제합니다.
• remove()
  주어진 값을 찾아서 연결을 해제하는 것으로 삭제처리 합니다.
• getNodeAt(index)
  주어진 인덱스의 노드를 찾아서 반환합니다. 값이 아니라 노드를 반환해야 하는 것에 주의하세요. 해당 인덱스에 노드가 없다면 undefined를 반환합니다.
• contains()
  연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환합니다.
• indexOf()
  주어진 값의 인덱스를 반환합니다. 없을 경우 -1을 반환합니다.

연결 리스트 구현

Hash Table

연관배열 구조를 이용하여 키, 값 쌍을 저장하고 있는 Data Structure 입니다.
연관배열 구조(associative array)란,
키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조입니다. 따라서 키(key)를 이용하여 값(value)을 도출할 수 있습니다.

해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키를 "해시 함수"(Hash function)라는 함수를 통해 특정 숫자값의 인덱스로 변환합니다. 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지합니다.

해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생하게 됩니다.

해시 테이블 Property

• key (매핑 전 원래 데이터의 값), hash value (매핑후 데이터의 값), hashing (매핑하는 과정 자체)
• storage , bucket, tuple
• size, limit

해시 테이블 메소드

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

해시 테이블 충돌

해시 테이블 구현