Linked List
1) 개념
자료구조 중 여러개의 변수를 저장하는 방법으로 배열(Array)와 링크드리스트(linked list)가 있다.
배열은 변수의 나열로,
장점은 i번째 원소를 바로 알 수 있다는 것이지만 단점은 원소의 추가, 삭제가 까다롭다.
반면 링크드 리스트는
각 원소가 node에 들어있고 이 Node는 값이 들어있는 data와 다음 원소를 가리키는 link로 구성되어 있으며
장점은 원소의 추가, 삭제가 쉽고, 단점은 i번째 원소를 알기 어렵고, 처음(head)부터 차근차근 따라 가야한다.
2) 구현
다음과 같은 method를 구현하세요 :
- addToTail(value) - 주어진 값을 연결 리스트의 끝에 추가한다.
- remove(value) - 주어진 값을 찾아서 연결을 해제(삭제)합니다
- getNodeAt(index) - 주어진 인덱스의 노드를 찾아서 반환한다. 값이 아니라 노드를 반환해야 하는 것에 주의. 해당 인덱스에 노드가 없다면 undefined를 반환한다.
- contains(value) - 연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환한다.
- indexOf(value) - 주어진 값의 인덱스를 반환한다. 없을 경우 -1을 반환한다.
class Node{ //linked list Node한개 정의 = data field + link field
constructor(value){
this.value = value;
this.next = null;
}
}
class LinkedList{//본격적으로 LinkedList class 구현
constructor(){
this.head = null; //첫 번째 node를 가리키는 것
this.tail = null; //마지막 node를 가리키는 것
this._size = 0; //총 LinkedList node개수
}
//addToTail(value): 주어진 값을 연결 리스트의 끝에 추가한다.
addToTail(value){
let newNode = new Node(value); //1. 주어진 값으로 새 Node만들고
if(this._size === 0){ //2. LinkedList에 아무것도 없으면 head와 tail에 newNode추가(이땐 head가 곧 tail이니까)
this.head = newNode;
this.tail = newNode;
}
else{//3. 있으면
this.tail.next = newNode; //3-1.먼저 기존 tail의 next를 newNode로,
this.tail = newNode; //3-2. newNode가 이제 tail이 된다.
}
this._size++; //4. size 증가
}
//remove(value) - 주어진 값을 찾아서 연결을 해제(삭제)한다.
//value가 있는 node를 한번에 찾을 수 없기 때문에 head부터 시작해서 값 일치여부 하나씩 비교해가면서 어느 node인지 찾아야한다.
remove(value){
let currNode = this.head; //1. head부터 시작해서
for(let i=0; i<this._size; i++){//2. 하나씩 살펴볼건데,
let PreNode = currNode; //3. 해당 value가 있는 node를 currNode로 찾으면, 그 전Node(PreNode)의 link를 삭제 후 연결해줘야하기때문에 필요하다
if(currNode.value === value){ // 4.해당 value가 있는 node를 currNode로 찾으면
if(currNode === this.head){//4-1. 딱 하나밖에 없는걸 삭제하는거라면
this.head = this.tail = null;
this._size = 0;
}
else{//4-2. 아니면
PreNode.next = currNode.next;
this._size--;
}
}
else{ //5. 옆으로 넘어가려면
currNode = currNode.next;
}
}
}
//getNodeAt(index) - 주어진 인덱스의 노드를 찾아서 반환한다. 값이 아니라 노드를 반환해야 하는 것에 주의.
// 해당 인덱스에 노드가 없다면 undefined를 반환합니다.
// 1. 먼저 해당 index 노드가 있는지 없는지 확인
// 1-1. 없으면 undefined return
// 2. 있으면 index까지 가서 그때의 node 찾고 (이때, i<index라는 것 주의!)
// 3. return node
getNodeAt(index){
let currNode = this.head;
if(this._size < index){
return undefined;
}
for(let i=0; i<index; i++){
currNode = currNode.next;
}
return currNode;
}
// contains(value) - 연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환한다.
//1. head부터 tail까지 next로 쭉 이어지면서
//2. now의 value확인
//2-1. value가 맞으면 return true
//2-2. 아니면 앞의 과정 반복
//3. 끝까지 왔는데도 value 못찾고 반복문 빠져나왔다면 없다는 거니까 return false
contains(value) {
let currNode = this.head;
for(let i=0; i<this._size; i++){
if(currNode.value === value){
return true;
}
currNode = currNode.next;
}
return false;
}
// indexOf(value) - 주어진 값의 인덱스를 반환한다. 없을 경우 -1을 반환한다.
//1. head부터 tail까지 next로 쭉 이어지면서 (이때 index도 함께 증가시킴)
//2. now의 value확인
//2-1. value가 맞으면 return index
//2-2. 아니면 앞의 과정 반복
//3. 끝까지 왔는데도 value 못찾고 반복문 빠져나왔다면 없다는 거니까 return -1
indexOf(value){
let currNode = this.head;
for(let index=0; index<this._size; index++){
if(currNode.value === value){
return index;
}
currNode = currNode.next;
}
return -1;
}
size(){
return this._size;
}
}Hash Table
※ Hash Table에 대해서는 libertegrace.tistory.com/entry/HashTable 에 다시 정리해 두었습니다.
1) 개념
Hashing이란 데이터 관리및 유지를 위해 다양한 길이의 데이터를 고정된 형태의 데이터로 mapping시키는 작업을 뜻한다.
그리고 이러한 기능을 구현한 함수를 Hash Function이라고 한다.
아래 그림에서 맨 왼쪽에 이런 데이터가 있고, 이를 Hash 자료구조를 이용해서 정리를 하고싶다고 합시다.
데이터를 Hash Table에 정리를 하고싶은데, 같은 데이터를 같이 곳에 정리할 수 있도록 규칙을 정해놓는 것이 좋겠다! 그래서 위의 정의에서도 잠깐 말했지만 이렇게 비 정형적인 키를 해시함수에 넣으면 정형화된 Hashed Value로 바꿔주는 것이 Hash Function의 역할이다!
2) Hash Function의 특징
주어진 저장소(Hash Table)의 크기 만큼의 값(0~저장소.length-1)을 Hashed Value로 반환해야한다.
특정한 키를 받으면 항상 같은 값을 반환해야 한다. (같은 데이터를 같이 곳에 정리할 수 있도록 규칙을 정해놓는 것!)
해시 함수 자체는 어떠한 값도 저장하지 않는다. 호출 되었을 때, 해시값을 반환하는 역할만 한다.
Hash의 단점
Hash Collision이 발생할 수도 있다. 즉, 서로 다른 키를 Hash Function에서 같은 Hashed Value로 반환하여 같은 Hashed Value에 대응시키게 되는 것이다.
아무리 잘 짜여진 Hash Function을 사용했다하더라도 Hash Collision이 발생할 수 있으므로 이러한 충돌을 처리할 방법이 꼭 필요하다.
3) Hash Collision에 대체하는 대표적인 두가지 방법
1. Chaining
해당 Hashed Value에 이미 값이 있으면 그 뒤에 chain으로 연결시키는 것이다.
2. Linear Probing
chaining을 하다보니 테이블을 써야지 Hash Table의 장점이 사는데, 계속 chaining으로 이어버리기만 한다면 비효율적이다.
그래서 Linear Probing방법은 이미 만들어 놓은 bucket을 먼저 쓰자라는 idea이다.
그래서 충돌이 발생하면 그 다음 (비어있는) Hashed value로 넣어버린다.
Hash Table이 다 차면?
3. Table Resizing
테이블의 크기를 늘려준뒤 기존의 데이터들을 다시 Hash Fucntion에 보낸다. 그리고 테이블을 다시 정리할 수 있다.
4) 구현
const LimitedArray = require('./helpers/limitedArray');
const hashFunction = require('./helpers/hashFunction');
// limitedArray.set(3, 'hi')
// limitedArray.get(3) // returns 'hi'
class HashTable {
constructor() {
this._size = 0;
this._limit = 8;
this._storage = LimitedArray(this._limit);
}
//insert(key, value) - 주어진 키와 값을 저장한다. 이미 해당 키가 저장되어 있다면 값을 덮어씌운다.
insert(key, value) {
const index = hashFunction(key, this._limit);
const bucket = this._storage.get(index) || [];
for (let i = 0; i < bucket.length; i += 1) {
const tuple = bucket[i];
if (tuple[0] === key) {
const oldValue = tuple[1];
tuple[1] = value;
return oldValue;
}
}
bucket.push([key, value]);
this._storage.set(index, bucket);
this._size += 1;
if (this._size > this._limit * 0.75) {
this._resize(this._limit * 2);
}
return undefined;
}
//retrieve(key) - 주어진 키에 해당하는 값을 반환한다. 없다면 undefined를 반환한다.
retrieve(key) {
const index = hashFunction(key, this._limit);
const bucket = this._storage.get(index) || [];
for (let i = 0; i < bucket.length; i += 1) {
const tuple = bucket[i];
if (tuple[0] === key) {
return tuple[1];
}
}
return undefined;
}
//remove(key) - 주어진 키에 해당하는 값을 삭제하고 값을 반환한다. 없다면 undefined를 반환한다.
remove(key) {
const index = hashFunction(key, this._limit);
const bucket = this._storage.get(index) || [];
for (let i = 0; i < bucket.length; i += 1) {
const tuple = bucket[i];
if (tuple[0] === key) {
bucket.splice(i, 1);
this._size -= 1;
if (this._size < this._limit * 0.25) {
this._resize(Math.floor(this._limit / 2));
}
return tuple[1];
}
}
return undefined;
}
//resize: limit값이 바뀔 때마다 size를 변경
//1. newLimit으로 갱신해주고
//2. 원래 저장 되어있던 것을 재저장(재배치)
_resize(newLimit) {
const oldStorage = this._storage;
// min size of 8, return if nothing to do!
newLimit = Math.max(newLimit, 8);
if (newLimit === this._limit) {
return;
}
this._limit = newLimit;
this._storage = LimitedArray(this._limit);
this._size = 0;
oldStorage.each(bucket => {
if (!bucket) {
return;
}
for (let i = 0; i < bucket.length; i += 1) {
const tuple = bucket[i];
this.insert(tuple[0], tuple[1]);
}
});
}
}
module.exports = HashTable;
reference
'Dev > SW Engineering' 카테고리의 다른 글
| 6. Inheritance Patterns - Object Oriented Programming (0) | 2020.05.24 |
|---|---|
| 5. Data Structure - Time Complexity (0) | 2020.05.24 |
| 5. Data Structure - Graph, Tree, BST (0) | 2020.05.24 |
| 3. Data Structure - Stack, Queue (0) | 2020.05.24 |
| 0. Bootcamp Roadmap (0) | 2020.05.01 |