Data Structure

Linked List 와 Hashtable

Linked List

1. node는 value와 next 값을 가진다. doubly linked list의 경우 before까지 추가된다
2. value는 현재 node가 갖고있는 값이며 next 는 현재 node가 가르키는 다음 node가 할당된다
3. doubly linked list의 경우 before에는 현재 node가 가르키는 앞의 node가 할당된다

• linkedList 의 메소드
  • addToTail(value) : 주어진 값을 연결 리스트의 끝에 추가
  • remove(value) : 삭제, 주어진 값을 찾아서 노드 연결 해제
  • getNodeAt(index) : 주어진 인덱스의 노드를 찾아 반환 (값이 아니라 노드를 반환, 해당 인덱스에 노드가 없다면 undefined 반환)
  • contains(value) : 연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환
  • indexOf(value) : 주어진 값의 인덱스를 반환 (해당 노드 없을 경우 -1 반환)
  • size() : 연결리스트의 노드 개수 반환
• Application of linkedList
  • Used in switching between programs using Alt + Tab (implemented using Circular Linked List)
  • 운영체제 상의 파일시스템, 웹브라우저 상의 방문 페이지 목록(자료의 추가 삭제가 빈번히 일어나는 경우에 사용하며 스택과 큐를 발전시켜서 사용)
  • undo, redo
  • 음악 재생목록관리

HashTable (= HashMap)

1. 자바스크립트의 객체 구조와 매우 유사
2. key와 value를 쌍으로 저장하지만 HashFunction(해시함수)를 통해 key를 index라는 주소값으로 변환
3. 변환된 index에 value를 저장
4. 서로 다른 key가 입력되어도 HashFunction(해시함수)의 알고리즘으로 인해 같은 index가 출력될 수 있음
5. 이때 같은 index에 value가 여러개 저장되는 Collisions(충돌)가 발생
6. Collisions를 핸들링하기 위해서는 Chaining(체이닝)기법을 사용할 수 있음
7. Chaining(체이닝) 기법은 value가 입력되는 index에 linked list의 형태로 value를 이어 붙이는 것
8. 이 외에도 Open Addressing(개방주소법)이라고 Collisions(충돌)이 일어나면 다른 index에 데이터를 삽입하는 방식이 있음
9. 위에서 말한 해시 테이블의 데이터를 모두 갖고 있는 것을 storage라고 하며 index는 bucket, index 안에 들어가는 각각의 value들의 방을 tuple이라고 함

• hashTable 의 메소드

  • insert(key, value) : 주어진 key와 value을 저장. 이미 해당 키가 저장되어 있다면 값을 덮어씌움
  • retrieve(key) : 주어진 key에 해당하는 value을 반환. 없다면 undefined 반환
  • remove(key) : 주어진 key에 해당하는 value을 삭제하고 삭제된 value을 반환. 없다면 undefined 반환
  • resize(newLimit) : 해시 테이블의 스토리지 배열을 newLimit으로 리사이징

• Application of hashTable

  • Used to implement associative arrays(PHP), map(javascript), dictionary(python).
  • P2P시스템의 노드 주소 관리
  • 암호학적 해시함수를 사용함으로써 사용자들의 id, password 저장할 때 사용되기도 함