with JavaScripts Study Days 14-15

210606 일요일 13~14일차

# 12~13일차 복습

CH6 연결 리스트

• 배열의 단점 : 대부분 프로그래밍 언어에서는 배열이 꽉 차면 데이터를 입력하기가 어렵다. 데이터를 추가하거나 삭제할 때도 나머지 요소를 이동해야 하므로 어려움이 따른다. 자바스크립트는 배열의 split()을 이용하면 간단하다. 하지만 자바스크립트의 배열은 객체라서 C++이나 자바보다 배열의 효율이 떨어진다. 따라서 배열이 너무 느리다고 판단되면 사용할 수 있다. 다만 임의의 요소에 접근해야 할 때는 연결리스트보다 배열이 낫다.

• 연결 리스트 정의 : node라 불리는 객체가 모여 연결 리스트를 구성한다. 각 노드는 객체 레퍼런스를 통해 리스트의 다른 노드와 연결된다. 다른 노드를 참조하는 레퍼런스를 Link라고 한다.

• 연결 리스트의 요소는 다른 요소와의 관계를 통해 원하는 요소를 참조할 수 있다. 예를 들어, Bread가 두 번째 위치에 있다라고 표현하는 것이 아니라 "Milk" 다음에 "Bread"가 있다라고 표현한다.

• 연결 리스트에서는 첫 번째 노드에서 마지막 노드로 이동하는 방식으로 전체 요소를 확인할 수 있다.

• 새 노드를 추가하려면 삽입하려는 노드의 이전 노드 링크가 새 노드를 가리키도록 바꿔야 하고 새 노드의 링크는 이전 노드가 가리키던 노드를 가리키도록 설정해야 한다.

• 항목을 삭제할 때는 삭제하려는 노드의 이전에 있는 노드 링크를 삭제하려는 노드가 가리키는 노드로 바꾼 다음, 삭제하려는 노드의 링크를 NULL로 설정하면 노드가 삭제된다.

• Node 클래스

// # : 노드 클래스function Node(element) {
    this.element = element;
    this.next = null;
}

• 연결 리스트 클래스

// # : 연결 리스트 클래스function LList() {
    this.head = new Node("head");
    this.find = find;
    this.insert = insert;
    this.findPrevious = findPrevious;
    this.remove = remove;
    this.display = display;
}

• 새로운 노드 삽입하기

// # : 새로운 노드 추가하기 : 기존 노드 뒤라고 가정, 기존 노드를 찾아야 한다.(find) 찾으면 해당 노드를 반환한다.function find(item) {
    let currNode = this.head;
// ! : 우선 새 노드를 만들고 head 노드로 설정while (currNode.element !== item) {
// ! : 다음 노드로 반복 이동하면서 현재 노드의 element 프로퍼티가 탐색하려는 값과 같은 값을 포함하는지 확인한다.// ! : 기존 노드를 찾으면 새 노드의 next 프로퍼티를 기존 노드의 next 프로퍼티의 값으로 설정한다.
        currNode = currNode.next;
    }
    return currNode;
}

function insert(newElement, item) {
    let newNode = new Node(newElement);
    let current = this.find(item);
    newNode.next = current.next;
    newNode.previous = current;
    current.next = newNode;
}

• 연결 리스트의 요소를 출력하는 함수

function display() {
    let currNode = this.head;
    while (!(currNode.next === null)) {
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
}

• 연결 리스트에서 노드 삭제하기

// # : 연결리스트에서 노드 삭제하려면 삭제하려는 바로 이전 노드를 찾아야 한다. 이전 노드를 찾았으면 이전 노드의 next를 삭제하려는 노드의 다음 노드로 설정해야 한다.function findPrevious(item) {
    let currNode = this.head;
    while (!(currNode.next === null) && currNode.next.element !== item) {
        currNode = currNode.next;
    }
    return currNode;
}
function remove(item) {
    let prevNode = this.findPrevious(item);
    if (!(prevNode.next === null)) {
        prevNode.next = prevNode.next.next;
    }
}

• 양방향 연결 리스트

 function Node(element) {
    this.element = element;
    this.next = null;
    this.previous = null;
}

• insert() :

function insert(newElement, item) {
    let newNode = new Node(newElement);
    let current = this.find(item);
    newNode.next = current.next;
    newNode.previous = current;
    current.next = newNode;
}

• remove() : 먼저 삭제하려는 데이터를 포함하는 노드를 찾는다. 그리고 삭제하려는 노드 이전 노드의 next 프로퍼티를 삭제하려는 노드의 next 값으로 하고, 삭제하려는 노드 다음 노드의 previous 프로퍼티를 삭제하려는 노드의 previous 값으로 각각 설정한다.

function remove(item) {
    let currNode = this.find(item);
    if (!(currNode.next === null)) {
        currNode.previous.next = currNode.next;
        currNode.next.previous = currNode.previous;
        currNode.next = null;
        currNode.previous = null;
    }
}

• findLast() : 양방향 연결 리스트의 마지막 노드로 이동하는 유틸리티 함수를 이용해 역순으로 연결 리스트를 출력할 수 있다.

// # : 양방향 연결 리스트의 "마지막 노드로 이동하는 유틸리티 함수"를 이용해 역순으로 연결 리스트를 출력하는 동작을 수행할 수 있다.function findLast() {
    let currNode = this.head;
    while (!(currNode.next === null)) {
        currNode = currNode.next;
    }
    return currNode;
}

• dispReverse() : 역순으로 양방향 연결 리스트의 요소 출력

// # : 역순으로 양방향 연결리스트의 요소 출력function dispReverse() {
    let currNode = this.findLast();
    while (!(currNode.previous === null)) {
        console.log(currNode.element);
        currNode = currNode.previous;
    }
}

• 순환형 연결 리스트

• 복잡한 양방향 연결 리스트를 만들지 않고 간단하게 역방향으로 탐색할 수 있다는 것이 강점이다. 노드의 끝을 지나 계속 탐색하면 결국 역방향에 있는 노드로 이동할 수 있다.

function LList() {
    this.head = new Node("head");
    this.head.next = this.head;
    this.find = find;
    this.insert = insert;
    this.display = display;
    this.findPrevious = findPrevious;
    this.remove = remove;
}

• display() : display() 함수는 순환형 연결 리스트에 사용하려면 while 루프 실행 조건을 헤드에서 멈추도록 바꿔야 한다.

function display() {
    let currNode = this.head;
    while (!(currNode.next === null) && !(currNode.next.element == "head")) {
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
}

# 14~15일차 학습

CH7 딕셔너리

7.1 Dictionary 클래스

function Dictionary() {
    this.datastore = new Array();
    this.add = add;
    this.find = find;
    this.remove = remove;
    this.showAll = showAll;
}

function add(key, value) {
    this.datastore[key] = value;
}

function find(key) {
    return this.datastore[key];
}

function remove(key) {
    delete this.datastore[key];
}

function showAll() {
// console.log(Object.keys(this.datastore));for (let key in this.datastore) {
        console.log(key + " -> " + this.datastore[key]);
    }
}

let pbook = new Dictionary();
pbook.add("Mike", "123");
pbook.add("David", "345");
pbook.add("Cynthia", "456");
console.log("David's extension: " + pbook.find("David"));
pbook.remove("David");
pbook.showAll();

7.2 Dictionary 클래스의 부가 함수

function Dictionary() {
    this.add = add;
    this.datastore = new Array();
    this.find = find;
    this.remove = remove;
    this.showAll = showAll;
    this.count = count;
    this.clear = clear;
}

function add(key, value) {
    this.datastore[key] = value;
}

function find(key) {
    return this.datastore[key];
}

function remove(key) {
    delete this.datastore[key];
}

function showAll() {
// console.log(Object.keys(this.datastore));for (let key in this.datastore) {
        console.log(key + " -> " + this.datastore[key]);
    }
}
// # : Count elements in dictionary, length 프로퍼티 사용하지 않는 이유는 문자열 키에서는 제대로 동작하지 않기 때문function count() {
    let n = 0;
    for (let key in this.datastore) {
        ++n;
    }
    return n;
}

let nums = new Array();
nums[0] = 1;
nums[1] = 2;
console.log(nums.length);
let pbook = new Array();
pbook["David"] = 1;
pbook["Jennifer"] = 2;
console.log(pbook.length);

function clear() {
    for (let key in this.datastore) {
        delete this.datastore[key];
    }
}

let pbook = new Dictionary();
pbook.add("Raymond", "123");
pbook.add("David", "345");
pbook.add("Cynthia", "456");
console.log("Number of entries: " + pbook.count());
console.log("David's extension: " + pbook.find("David"));
pbook.showAll();
pbook.clear();
console.log("Number of entries : " + pbook.count());

7.3 Dictionary 클래스에 정렬 기능 추가하기

// 하지만 문자열 키는 이 방식이 불가능하다. 아무 결과도 출력되지 않는다. Object.keys()를 이용해야 한다.function showAll() {
    this.datastore = Object.keys(this.datastore).sort();// for문 안에서 바로 key를 빼면 sort가 적용되지 않아 위에서 할당for (let key in this.datastore) {
        console.log(key + " -> " + this.datastore[key]);
    }
}

7.4 연습문제

// #2. Dictionary 클래스를 이용해 어떤 텍스트에서 단어가 몇 번 나오는지를 저장하는 프로그램을 구현하시오.// 프로그램은 텍스트에서 각 단어가 몇 회 나오는지 표시해야 한다.// 예를 들어 'the brown fox jumped over the blue fox.'를 입력했을 때 다음과 같은 결과가 출력돼야 한다.// the : 2// brown: 1// fox : 2// jumped : 1// over : 1// blue : 1function Dictionary() {
    this.add = add;
    this.datastore = new Array();
    this.find = find;
    this.remove = remove;
    this.showAll = showAll;
}

function add(text) {
    textArr = text.substr(0, text.length - 1).split(" ");// 마침표 제거 후 단어 단위로 자름

    textArr.forEach((word) => {
// 처음에 들어있는 값은 0으로 초기화할 때 인덱스에 숫자를 넣어야 되므로// if문으로 초깃값 undefined일 경우 0으로 초기화한 다음 개수를 추가시켜준다.if (this.datastore[word] === undefined) {
            this.datastore[word] = 0;
        }
        this.datastore[word] = this.datastore[word] + 1;//value;
    });
}

function find(key) {
    return this.datastore[key];
}

function remove(key) {
    delete this.datastore[key];
}

function showAll() {
    for (let key of Object.keys(this.datastore)) {
        console.log(key + " -> " + this.datastore[key]);
    }
}

let pbook = new Dictionary();
pbook.add("the brown fox jumped over the blue fox.");
pbook.showAll();

// #3. 2번 예제의 결과를 정렬해서 출력하도록 프로그램을 고치시오.// #2. Dictionary 클래스를 이용해 어떤 텍스트에서 단어가 몇 번 나오는지를 저장하는 프로그램을 구현하시오.// 프로그램은 텍스트에서 각 단어가 몇 회 나오는지 표시해야 한다.// 예를 들어 'the brown fox jumped over the blue fox.'를 입력했을 때 다음과 같은 결과가 출력돼야 한다.// the : 2// brown: 1// fox : 2// jumped : 1// over : 1// blue : 1function Dictionary() {
    this.add = add;
    this.datastore = new Array();
    this.find = find;
    this.remove = remove;
    this.showAll = showAll;
}

function add(text) {
    textArr = text.substr(0, text.length - 1).split(" ");// 마침표 제거 후 단어 단위로 자름

    textArr.forEach((word) => {
// 처음에 들어있는 값은 0으로 초기화할 때 인덱스에 숫자를 넣어야 되므로// if문으로 초깃값 undefined일 경우 0으로 초기화한 다음 개수를 추가시켜준다.if (this.datastore[word] === undefined) {
            this.datastore[word] = 0;
        }
        this.datastore[word] = this.datastore[word] + 1;//value;
    });
}

function find(key) {
    return this.datastore[key];
}

function remove(key) {
    delete this.datastore[key];
}

function showAll() {
    for (let key of Object.keys(this.datastore).sort()) {
        console.log(key + " -> " + this.datastore[key]);
    }
}

let pbook = new Dictionary();
pbook.add("the brown fox jumped over the blue fox.");
pbook.showAll();