Dog foot print

어제 선형탐사 방식을 통하여 해시값 충돌시 해시값을 유효범위까지 늘려 충돌을 우회했다. 그러나 open adress방식을 사용하면 유효범위가 유한하기 때문에 언젠가 충돌이 일어날 수 있었다. 그렇기에 이번에는 chaining 방식을 통해 조금 더 유연한 hash table을 만들어 보겠다. Seperate Chaining Seperate chaining 은 배열에 연결리스트를 넣어서 유한하던 저장공간문제를 해결하는 방식이다. 다만 메모리문제와 탐색시 최악의 시간 복잡도가 O(n)이 된다는 단점도 가지고 있다. Double Linked List function Dictionary(key,value){ return { llink : null, key : key, value : value, rlink : nu..

hash table에 대한 포스팅을 조금 더 찾아봤는데 충돌이 일어날 경우 open adress 방식이나, seperate Chaining 방식으로 해당 충돌을 우회 해야한다고 다들 적어놓았지만 충돌이 일어나 다른 곳에 저장한 후 해당 key로 어떻게 data를 찾는지는 나오지 않았다. 그래서 해시테이블을 직접 만들어 보면 어떨까 싶어 해시테이블 2부를 만들게 되었다. 원시적인 해시테이블 function HashTable(){ let array = []; let size = 20; return { hashFunc(key){ let hashValue = key.length % size; return hashValue; }, add(key,item){ if(array[this.hashFunc(key)] !=..

자바스크립트 이외에 언어에서 연결리스트가 가지는 이점은 배열처럼 고정된 크기를 가지는게 아니라 동적으로 크기를 조정 할 수 있는 것이 장점이다. 그렇다면 단순연결리스트와 원형연결리스트 보다 이중연결리스트가 가지는 이점은 무엇일까 ? 이중연결리스트란 ? 기존에 만들었던 연결리스트들은 모두 한 방향으로 이루어져 있다. 그런데 이중연결리스트는 L link 와 R link를 가지고 있어 해당 노드에서 전, 후 노드에 접근 하는 것이 가능케 된다. 이로인해서 헤드가 마지막에 연결되어있는 노드를 O(1) 의 복잡도를 가지고 찾을 수 있다. 멤버변수 class nodeType{ constructor(item){ this.data = item; this.lLink = null; this.rLink = null; } 이..

지난번 만들어 보았던 단순연결리스트는 마지막 node 가 null을 가리키고 있는 형태를 하고 있는데 오늘 만들어볼 원형 연결리스트는 마지막 노드가 항상 Head 노드를 가리키고 있어 노드의 링크를 타고 다시 처음으로 갈 수 있다는 이점이 있다. // 아직 원형연결리스트가 단순연결리스트보다 더 좋은 이점을 찾지를 못 찾겠다. 루프를 만들어 내부에 뭐가 있는지 순차적으로 감시하기에는 좋을 듯 하다. 원형연결리스트 필요한 멤버 변수 처음 만들어지는 head는 data로 head가 들어간다. constructor(item){ this.data = item; this.link = null; } 필요한 메서드 insertFirstNode(item) // node를 생성하고 head바로 앞에 넣는다. insertL..

javascript의 배열은 array-list라는 것의 형태를 띄고 있어 배열의 크기 존재하지 않는다. 그런데 c 같은 언어들은 배열의 크기가 존재하기에 한 배열을 유한하게 밖에 사용 할 수 없다. 그래서 개발자들은 노드리스트라는 개념을 만들어 각각의 구조체들로 서로를 연결하는 것을 만들었다. 연결리스트에는 단순 연결리스트, 이중연결리스트, 원형연결리스트가 있으며 이 연결리스트들을 이용하여 스택, 큐, 트리등 다양한 자료구조를 만들 수 있다. node 란 node란 data필드와 link필드를 가지고 있는 일종의 구조체로 link를 통해서는 다음 연결된 노드에 접근 할 수 있다. simple linked-list는 처음 노드를 header라고 하며 마지막 노드의 link는 항상 null이다. 연결리스트..

이전까지 stack, sicle queue, queue 를 만들었지만 전부 다 단방향에서 아이템을 꺼내와야 하는 불편함이 있었다. 그러나 원형 큐의 아종인 덱이라는 녀석은 앞과 뒤 모든 방향에서 데이터를 추가 및 삭제 할 수 있는데 오늘은 이 녀석을 만들어 볼 예정이다. 덱 Deck 덱은 원형 큐와 마찬가지로 배열에 빈 공간이 있다면 데이터를 추가 할 수 있는 구조를 하고 있어 원형 큐와 마찬가지로 덱 또한 원형 구조를 하고 있다. 덱의 멤버변수 constructor(size){ this.maxQueueSize = size; this.array = []; this.front = 0; this.rear = 0; } 원형 큐와 동일한 front , rear를 가지고 있다. 덱의 메서드 __주의__ addRe..

어제 만들어본 stack은 가장 늦게 넣은 것이 가장 빨리 나오는 LIFO(후입선출) 의 형태를 취하고 있다. 오늘 만들어볼 queue는 FIFO(선입선출)의 형태를 하고 있으며 원시적인 선형큐를 만들어 볼 것이다. Queue 란 ? 큐는 데이터를 선입선출을 하는 자료구조이다. queue는 우리 주변에서도 많이 보이는데 카운터에서 줄을 서고 있는 손님들이나 print의 출력에서도 queue의 형태를 볼 수 있다. 선형 큐란 ? 선형큐는 재사용이 되지 않는 형태의 큐이다. 배열에 공간이 남았더라도 rear가 max_size 까지 도달 했다면 배열 전체를 초기화 하지 않으면 item을 넣지 못한다. queue의 멤버변수 max_size // queue에 저장 가능한 공간을 뜻 한다. front // queu..