*이 내용은 인프런 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)을 수강하며 정리한 내용입니다.

덱

데이터의 삽입과 제거를 head와 tail 두군데서 자유롭게 할 수 있어.

덱의 추상자료형

printAll - 모든 데이터 출력

addFirst - head에 데이터 삽입

removeFirst - head에서 데이터 제거

addLast - tail에 데이터 삽입

removeLast - tail에서 데이터 제거

isEmpty - 리스트 비었는지 체크

구현

DoublyLinkedList.mjs를 import 해줘.

class Deque{
    constructor(){
        this.list = new DoublyLinkedList();
    }

    printAll(){
        this.list.printAll();
    }

    addFirst(data){
        this.list.insertAt(0, data);
    }

    removeFirst(){
        return this.list.deleteAt(0);
    }

    addLast(data){
        this.list.insertAt(this.list.count, data);
    }

    removeLast(){
        return this.list.deleteLast();
    }

    isEmpty(){
        return (this.list.count == 0);
    }
}

해시테이블

해시(Hash), 맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary)라고도 불려.

해시 테이블은 이름에서도 알 수 있듯이 해시와 테이블이 합쳐진 자료구조야.

해시 함수

Key만 알면 Value에 O(1)의 성능으로 읽기가 가능하다!

하지만 동일한 Key에 많은 Value를 집어넣는다면 많은 연결리스트를 뒤져야해.

그러므로 데이터를 골고루 분배하는 것이 중요해!!

장점 : 빠른 데이터 읽기, 삽입, 삭제

단점 : 메모리를 많이 차지함, 좋은 해시 함수의 구현이 필수적!

추상자료형

set - 데이터 삽입

get - 데이터 읽기

remove - 데이터 제거

구현

구현하기 전 hash 함수를 어떻게 만들거냐면~위와같은 형식으로 10으로 나눈 나머지의 인덱스에 값을 삽입할거야!

• HashData

class HashData{
    constructor(key, value){
        this.key = key;
        this.value = value;
    }
}

• HashTable

class HashTable{
    constructor(){
        this.arr = [];
        for(let i = 0; i < 10; i++){ // 0~9까지 연결리스트 초기화
            this.arr[i] = new DoublyLinkedList();
        }
    }

    hashFunction(number){
        return number % 10;
    }

    set(key, value){
        this.arr[this.hashFunction(key)].insertAt(0, new HashData(key, value));
    }

    get(key){
        let currentNode = this.arr[this.hashFunction(key)].head;
        while(currentNode != null){
            if(currentNode.data.key == key){
                return currentNode.data.value;
            }
            currentNode = currentNode.next;
        }
        return null;
    }

    remove(key){
        let list = this.arr[this.hashFunction(key)];
        let currentNode = list.head;
        let deletedIndex = 0;
        while(currentNode != null){
            if(currentNode.data.key == key){
                return list.deleteAt(deletedIndex);
            }
            currentNode = currentNode.next;
            deletedIndex++;
        }
        return null;
    }
}

Set

데이터의 중복을 허용하지 않는 자료구조야. 셋은 해시 테이블을 이용해.

해시 테이블의 value 값은 사용하지 않고 key만 사용해서 구현해!!

추상자료형

add(data) - 데이터 삽입

isContain(data) - 데이터 체크

remove(data) - 데이터 제거

clear() - 셋 비우기

isEmpty() - 셋이 비었는지 체크

printAll() - 모든 데이터 출력

구현

class HashSet{
    constructor(){
        this.hashTable = new HashTable();
    }

    add(data){
        if(this.hashTable.get(data) == null){
            this.hashTable.set(data, -1); // value는 쓰이지 않기때문에 그냥 -1값 넣어줌
        }
    }

    isContain(data){
        return this.hashTable.get(data) != null;
    }

    remove(data){
        this.hashTable.remove(data);
    }

    clear(){
        for(let i = 0; i < this.hashTable.arr.length; i++){
            this.hashTable.arr[i].clear();
        }
    }

    isEmpty(){
        let empty = true;
        for(let i = 0; i < this.hashTable.arr.length; i++){
            if(this.hashTable.arr[i].count > 0){
                empty = false;
                break;
            }
        }

        return empty;
    }

    printAll(){
        for(let i = 0; i < this.hashTable.arr.length; i++){
            let currentNode = this.hashTable.arr[i].head;
            while(currentNode != null){
                console.log(currentNode.data.key);
                currentNode = currentNode.next;
            }
        }
    }
}

참조 : 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

• 3주차 회고

  • 칭찬하고 싶은 점 : 기한을 지켰다 😅

  • 아쉬웠던 점 : 권장 커리큘럼을 지키지 못했다.