오늘도 오지게 달려보자....짧아져 가는 나의 intro..
😩😩😩
단일연결리스트
- 단일 연결 리스트는 각 노드에 data 공간과 한 개의 포인터(주소값) 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.
이중연결리스트
- 이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터(주소값) 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.
원형연결리스트
- 원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.
class Node { constructor(value) { this.value = value; this.next = null; } } class LinkedList { constructor() { this.head = null; this.tail = null; this._size = 0; } addToTail(value) { let node = new Node(value); if (this.head === null) { this.head = node; this.tail = node; } else { this.tail.next = node; this.tail = node; } } remove(value) { let currNodeIdx = this.indexOf(value); let currNode = this.getNodeAt(currNodeIdx); let prevNodeIdx = currNodeIdx - 1; let prevNode = this.getNodeAt(prevNodeIdx); if (currNode === this.head) { this.head = currNode.next; } else { prevNode.next = currNode.next; } currNode.next = null; this.tail = this.getNodeAt(this.size() - 1); } // index 위치에 노드를 출력한다. getNodeAt(index) { let tmp = this.head; for (let i = 0; i < index; i++) { if (tmp === null) { return undefined; } tmp = tmp.next; } return tmp; } // 매개변수 value와 같은 값을 지닌 node가 있는지 확인한다. contains(value) { if (this.indexOf(value) === -1) { return false; } else { return true; } } // indexOf indexOf(value) { let tmp = this.head; let count = 0; while (tmp !== null) { if (tmp.value === value) { return count; } count++; tmp = tmp.next; } return -1; } size() { let tmp = this.head; let length = 0; while (tmp !== null) { length++; tmp = tmp.next; } return length; } }
key : 고유한 값이며, 해시 함수의 input이 된다.
hash function : 키(key)를 해시(hash)로 바꿔주는 역할을 한다. 서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.
hash : 해시 함수(Hash Function)의 결과물이며, 저장소(bucket)의 index이다.
value : 저장소(bucket, slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 한다.
해시테이블의 시간복잡도는 충돌이 났을때와 나지 않았을때를 나누어 생각할 수 있다.
input으로 들어가는 keys의 hash(bucket의 인덱스)가 전부 다를 경우 삽입, 삭제, 조회가 한번에 가능하다.
위에 그림처럼 buckets의 152번에서 John Smith와 Sandra Dee의 hash가 겹쳐 충돌이 일어나면, 처음 들어간 value의 뒷 노드로 다음 value를 저장한다. (buckets에 연결리스트를 사용한거임)
정리하자면 충돌이 일어나면 -> 리스트로 value를 저장하고 -> key와 매치되는 value를 삽입, 삭제, 조회할 때 리스트를 순회하기 때문에 최대 n번의 작업을 하게 될 수 있음.
충돌이 나지 않았을 경우
충돌이 생겼을 경우
class HashTable { constructor() { this._size = 0; // size = input의 개수 , storage의 크기를 나타내는 변수가 아니다. this._limit = 8; this._storage = LimitedArray(this._limit); } insert(key, value) { const index = hashFunction(key, this._limit); let hasValue = this._storage.get(index); let obj = hasValue ? hasValue : {} obj[key] = value; this._storage.set(index, obj) this._size++; if (this._size > this._limit * 0.75) { this._resize(this._limit * 2); } } retrieve(key) { const index = hashFunction(key, this._limit); if (this._storage.get(index) && this._storage.get(index)[key]) { return this._storage.get(index)[key]; } else { return undefined; } } remove(key) { const index = hashFunction(key, this._limit); delete this._storage.get(index)[key]; if (this._size < this._limit * 0.25) { this._resize(this._limit / 2); } this._size--; } _resize(newLimit) { const originStorage = this._storage; this._limit = newLimit; this._storage = LimitedArray(this._limit); this._size = 0; // originStorage가 each 내부의 this로 바인딩 되지 않게 하기 위해서, 화살표 함수를 사용한다. originStorage.each(obj => { for (let key in obj) { this.insert(key, obj[key]) } }); } }
흐물흐물....그래도 생각보다 할만하네...ㅎㅎ😭