[JavaScript]TWIl:データ構造2/3リンクリスト,hashTable(20/10.22-0.27)

Data Structure Sprintを行っています.
2/3まで行い,今回実施した資料構成は2種類であった.
今回も自ら描いた資料構造と一緒に.(ああ)
1. linkedList
2. hashTable

1. linked List

LikedListは要素からなる、サイズがダイナミックなデータ構造である.
nodeにはvalue(data)とnext(pointer)という属性があり、各nodeはnext属性で接続されている.
上図は、データの一方向接続のSige-linkedListです.
また、双方向ポインタを持つデータの二重リンクリストもあります.2つのポインタprev,nextがあり,双方向にループすることができる.
LinkedListが使用する代表的な機能は音楽プレイリストです.歌をスキップしたり、前/次などを実現できます.
今回は単一の接続リストを体現しています.この点を見てみましょう.

Property

value(data)

次ノードへのnext

Method

addToTail(データ)

リスト末尾にデータを追加

データのremove(data)

の検索と削除
getNodeAt(index)、インデックスを取得するためのノード.

データを返すcontains(data)

このデータのインデックスOf(data)

を検索する.

のデータ総数を提供するsize()

以外の実装の程度による.

Psuedo Code

addToTail(data) {
  // 1. 입력받은 data를 가진 node를 생성
  // 2. 만약, 리스트가 비어있다면 해당 node를 head이자 tail로 할당
  // 3. 아니라면, 리스트의 tail의 next에 해당 node를 할당하고, 이를 tail로 지정
}

remove(data) {
  // 1. data가 head일 경우 : head를 다음 node로 지정 (연결이 자동으로 끊길 것)
  // 2. data가 tail일 경우 : 그 이전의 노드를 tail로 지정
  // 3. 그 외 : data node의 이전 node와 다음 node를 연결(.next.next)
}

getNodeAt(index) {
  // 해당 index만큼 node를 이동해 해당 node를 return
}

contains(data) {
  // 리스트를 순회하여 해당 data를 찾으면 true를, 찾지 못하면 false를 return
}

indexOf(data) {
  // 리스트를 순회하여 도중에 일치하는 값을 찾으면 해당 index를, 찾지 못하면 -1을 return
}

size() {
  // 리스트를 순회하여 tail에서의 i(index)를 return
}

2. hashTable

hashTableは、データがキー値ペアからなる、サイズがダイナミックなデータ構造である.
入力データのキー値をハッシュ関数で特定のインデックスに変換し、キー値をインデックスに格納します.ストレージスペースの効率を向上させるために、スペースが75%以上25%以下の場合、スペースサイズを調整します.(double sizing, half sizing)
ハッシュ関数でインデックスを一度にクエリーできるので、keyの値が頻繁に変化する場合に役立ちます.
また、鍵は特定のインデックスで暗号化されるため、データセキュリティが重要な場合にも暗号化されます.
代表的なのはメンバーシップDB構成,ゲームユーザのスコアDB構成などである.

Property

size

は、格納されたデータの数を示す

容量制限

storage

Method

新しいキー、値のinsert(key,value)

を挿入する
検索(key),入力鍵の値を取得する

入力鍵のデータを削除するremove(鍵)

ストレージ容量のサイズ変更(newLimit)

Psuedo Code

// hashFunction과 LimitedArray는 이미 구현되어 있는 것으로 한다.

insert(key, value) {
  // hashFunction(key) -> 특정 index 받음
  // 1. 해당 index가 비어있는 경우
  // --> 그대로 키값 쌍을 삽입
  // 2. 해당 index에 이미 다른 data 1개가 존재 할 경우
  // --> bucket을 만들어 기존의 data를 담고, 입력받은 키값 쌍을 삽입
  // --> 만들어진 bucket을 해당 index에 삽입
  // 3. 해당 index에 bucket이 존재할 경우
  // --> bucket에 접근해 입력받은 키값 쌍을 삽입
  
  // +) 삽입 후 storage 사용정도가 75% 이상 넘어가면 resize메소드를 이용해 double sizing
}

retrieve(key) {
  // 1. 해당 key를 가진 data가 존재하지 않을 경우
  // --> undefined를 return
  // 2. 해당 key의 index에 유일한 data로 존재할 경우
  // --> 바로 value 접근 가능
  // 3. 해당 key의 index가 bucket일 경우
  // --> bucket을 순회하며 일치하는 key 검색, 존재한다면 value를 return
}

remove(key) {
  // 1. 해당 key의 index에 유일한 data로 존재할 경우
  // --> 해당 index의 값을 undefined 처리
  // 2. 해당 key의 index가 bucket일 경우
  // --> bucket을 순회하며 일치하는 key 검색, 존재시 해당 bucket의 index를 undefined로 처리
  
  // +) 제거 후 storage 사용정도가 25% 이하로 떨어지면 resize메소드를 이용해 half sizing
}

resize(newLimit) {
  // 1. 현재 storage를 변수에 백업
  // 2. size, limit, LimitedArray(double or half)로 초기화
  // 3. 백업해둔 storage를 순회하며 data들을 rehashing하여 다시 삽입
}