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;
}LList 클래스는 연결 리스트의 기능을 제공한다. LList 클래스는 새 노드의 삽입, 기존 노드의 삭제, 리스트의 특정 데이터 검색 등의 기능을 제공한다. 새 연결 리스트를 만드는 데 사용할 생성자 함수도 제공한다. 초기에는 head의 next 프로퍼티를 null로 설정한다. 리스트에 노드가 추가되면 next 프로퍼티 값을 바꾼다.
- 새로운 노드 삽입하기
새 노드를 추가하려면 기존 노드를 찾아야 한다. 따라서 연결 리스트에서 특정 데이터를 포함하는 노드를 검색하는 헬퍼 함수 find()를 구현한다.
// # : 새로운 노드 추가하기 : 기존 노드 뒤라고 가정, 기존 노드를 찾아야 한다.(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 프로퍼티를 삭제하려는 노드의 다음 노드로 설정해야 한다. findPrevious()는 다음 노드에서 삭제하려는 데이터를 포함하고 있으면 탐색을 멈춘다. 삭제하려는 데이터를 포함하는 노드의 이전 노드를 반환한다. 그래야만 이전 노드의 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;
}
}prevNode.next = prevNode.next.next
- 양방향 연결 리스트
연결 리스트는 역방향으로 노드를 탐색하는 것이 쉽지 않다. 노드에 이전 노드의 링크를 저장하는 프로퍼티를 추가하면 이 문제를 쉽게 해결할 수 있다. 하지만 링크를 추가하면 노드를 추가할 때 더 많은 작업을 해야 한다. 대신 노드를 삭제할 때는 더이상 이전 노드를 찾을 필요가 없어 좀더 간단해진다.
function Node(element) {
this.element = element;
this.next = null;
this.previous = null;
}
- insert() :
새 노드의 previous 프로퍼티를 이전 노드로 설정해야 한다.
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;
}
}
- 순환형 연결 리스트
순환형은 단방향과 같은 종류의 노드를 포함한다. 유일하게 다른 점은 순환형은 헤드의 next 프로퍼티가 자신을 가리킨다는 것이다. head.next = head;는 전체 리스트에 적용되어 항상 마지막 노드의 next 프로퍼티는 head를 가리킨다.
- 복잡한 양방향 연결 리스트를 만들지 않고 간단하게 역방향으로 탐색할 수 있다는 것이 강점이다. 노드의 끝을 지나 계속 탐색하면 결국 역방향에 있는 노드로 이동할 수 있다.
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 딕셔너리
딕셔너리는 전화번호부에 이름과 전화번호로 데이터를 저장하는 것처럼 데이터를 키(key)와 값(value) 쌍으로 저장하는 자료구조다. 누군가의 전화번호를 검색하려면 먼저 그 사람의 이름을 검색해야 한다. 이름을 찾으면 그 옆에 표시된 전화번호를 확인할 수 있다. 키로 검색을 수행하고 검색 결과로 값을 반환한다.
자바스크립트의 Object 클래스는 딕셔너리 형식으로 동작하게 설계되었다. []보다는 ()를 이용해 키를 참조하는 편이 훨씬 쉽고 딕셔너리의 모든 항목을 출력시키는 유용한 함수를 만들어 놓으면 편하므로 Dictionary 클래스를 만들도록 한다.
7.1 Dictionary 클래스
내부적으로 Object 클래스가 아닌 Array 클래스를 이용한다. 딕셔너리의 키를 정렬해야 하는데 자바스크립트는 Object 클래스의 프로퍼티를 정렬하지 못한다. 하지만 자바스크립트의 모든 것은 객체(Object)이므로 배열 역시 객체임을 기억하자.
function Dictionary() {
this.datastore = new Array();
this.add = add;
this.find = find;
this.remove = remove;
this.showAll = showAll;
}
add()는 키와 값을 받는다. 키는 값을 찾는 데 사용하는 인덱스다.
function add(key, value) {
this.datastore[key] = value;
}
find()는 키를 인자로 받아 키와 관련된 값을 반환한다
function find(key) {
return this.datastore[key];
}
딕셔너리의 키와 값 쌍을 지울 떄는 내장 함수 delete를 이용한다. 이는 Object클래스의 일부며 인자로 키 레퍼런스를 받는다.
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]);
}
}
책에서는 for each ( var key in Object.keys(this.datastore)) {
로 선언하여 사용했는데 실제로 Object.keys(this.datastore)를 콘솔에 찍어보니 [ "Mike", "Cynthia" ] 로 되어 있어 아래의 콘솔 출력문에는 적합하지 않았다. key가 "0", "1"로 나오고 this.datastore[key]도 undefined로 출력되었다. 그래서 원하는 출력값을 얻기 위해서 for in 문을 이용하였다.
for( let key in this.datastore){ 로 선언한 결과 this.datastore에 존재하는 키와 값 쌍의 키 값들이 하나씩 튀어나오고 이에 해당하는 인덱스를 찾아 그 값을 출력시켜주었다.
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 클래스의 부가 함수
딕셔너리에 몇 개의 항목이 저장되어 있는지 알기 위한 count() 함수,( length 프로퍼티는 문자열 키에서는 제대로 작동하지 않아 사용하지 않았다.) 또한 모든 항목을 삭제하는 clear() 함수를 추가했다.
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 클래스에 정렬 기능 추가하기
키를 이용해 값을 얻는 것이 딕셔너리의 핵심 기능이다. 저장된 항목의 순서는 중요하지 않다. 하지만 정렬된 순서로 확인해야 할 경우가 있다. sort() 함수가 있으나 문자열 키에서는 안된다. 따라서 다시 한번 Object.keys()를 사용해야 한다는데 다시 한번 제대로 작동하지 않으므로 위에서 key들만 뽑아서 배열을 구성한 다음 for문에서 이 key들을 뽑아 출력시키도록 구현하였다.
// 하지만 문자열 키는 이 방식이 불가능하다. 아무 결과도 출력되지 않는다. 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]);
}
}
위 showAll() 메서드를 다시 출력해보면서 잘못 구현했다는 것을 알고 key를 가져오는 게 아니라 해당하는 인덱스의 값을 가져오는 방법이 있을 것으로 보아서 for of 문을 시도해본 결과 key 값에 0, 1, 2,,,,와 같은 인덱스 값들이 들어오는 것이 아니라 해당하는 인덱스의 key값이 제대로 들어오고 원하는 출력을 얻을 수 있었다. Object.keys와 Object.values의 문제인줄 알았는데 책에서 나온 for each 문이 for of문으로 대체된다는 사실을 알게 되었고 for of문에 대해서 잘 숙지하고 있어야 겠다.
7.4 연습문제
#1. 텍스트 파일에서 이름과 전화번호를 읽어 Dictionary 객체에 저장하는 프로그램을 구현하시오. 또한 특정 전화번호 출력 기능, 모든 전화번호 출력 기능, 새로운 전화번호 추가 기능, 기존 전화번호 삭제 기능, 모든 전화번호 삭제 기능을 추가하시오.
#2. Dictionary 클래스를 이용해 어떤 텍스트에서 단어가 몇 번 나오는지를 저장하는 프로그램을 구현하시오. 프로그램은 텍스트에서 각 단어가 몇 회 나오는지 표시해야 한다. 예를 들어 'the brown fox jumped over the blue fox.'를 입력했을 때 다음과 같은 결과가 출력돼야 한다.
the : 2
brown: 1
fox : 2
jumped : 1
over : 1
blue : 1
// #2. Dictionary 클래스를 이용해 어떤 텍스트에서 단어가 몇 번 나오는지를 저장하는 프로그램을 구현하시오.
// 프로그램은 텍스트에서 각 단어가 몇 회 나오는지 표시해야 한다.
// 예를 들어 'the brown fox jumped over the blue fox.'를 입력했을 때 다음과 같은 결과가 출력돼야 한다.
// the : 2
// brown: 1
// fox : 2
// jumped : 1
// over : 1
// blue : 1
function 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번 예제의 결과를 정렬해서 출력하도록 프로그램을 고치시오.
// #3. 2번 예제의 결과를 정렬해서 출력하도록 프로그램을 고치시오.
// #2. Dictionary 클래스를 이용해 어떤 텍스트에서 단어가 몇 번 나오는지를 저장하는 프로그램을 구현하시오.
// 프로그램은 텍스트에서 각 단어가 몇 회 나오는지 표시해야 한다.
// 예를 들어 'the brown fox jumped over the blue fox.'를 입력했을 때 다음과 같은 결과가 출력돼야 한다.
// the : 2
// brown: 1
// fox : 2
// jumped : 1
// over : 1
// blue : 1
function 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();
'Web > Javascript' 카테고리의 다른 글
| js sort 메서드 숫자 정렬 이해하기(compareFunction), 프로그래머스 정렬-레벨1-가장 큰 수 (0) | 2021.07.03 |
|---|---|
| Data structures & Algorithms with JavaScripts 스터디 9~11일차 (0) | 2021.05.20 |
| [Javascript] for 문, for in 문, for of 문 (0) | 2021.05.17 |
| Data structures & Algorithms with JavaScripts 스터디 8일차 (0) | 2021.05.08 |
| Data structures & Algorithms with JavaScripts 스터디 5~7일차 (0) | 2021.05.05 |
댓글