인프런의 그림으로 쉽게 배우는 자료구조와 알고리즘(기본편)을 수강하고 정리한 글입니다.
자료구조
- 데이터가 어떤 구조로 저장되고 사용되는지를 나타낸다.
- 자료구조에 따라 처리 방법이 다르고 더 단순해질 수도 있다.
1. Array(배열)
- 일반적인 프로그래밍 언어에서 배열은 선언할 때, 배열의 크기를 알려준다.
ex)int arr[10] = {1,2,3,4,5}; - 할당되지 않은 부분은 쓰레기 값이 저장되며 운영체제는 배열의 시작주소를 기억하고 활용하여 인덱스에 접근한다.
- 삽입, 삭제의 성능은 좋지 못하다.
- 배열은 메모리 공간을 미리 확보하기 때문에 재 할당 하는 데이터가 기존 데이터보다 메모리가 클 경우, 새로운 메모리 공간을 찾아서 할당해야하며, 기존 데이터를 복사해야 한다.
- 메모리 공간이 낭비될 수 있음.
- 배열에서의 삽입은 오버헤드가 많이 듦.
- 배열의 데이터 참조는 O(1)의 성능을 가진다.
- 데이터가 자주 변경되지 않고 참조가 많이 일어나는 경우에 적합하다.
자바스크립트에서의 Array
- 자바스크립트에서 배열은 불연속적으로 할당하며 내부적으로 연결해 배열인 것 처럼 보이게 함(희소 배열)
희소배열이란?
배열의 요소가 연속적으로 이어져있지 않은 배열
console.log(Object.getOwnPropertyDescriptors([1, 2, 3]));
/*
{
'0': { value: 1, writable: true, enumerable: true, configurable: true },
'1': { value: 2, writable: true, enumerable: true, configurable: true },
'2': { value: 3, writable: true, enumerable: true, configurable: true },
length: { value: 3, writable: true, enumerable: false, configurable: false }
}
*/위의 예제를 보면 알 수 있듯이, 자바스크립트의 배열은 인덱스를 프로퍼티 키로 갖으며 length 프로퍼티를 갖는 특수한 객체이다.
자바스크립트 배열의 요소는 사실 프로퍼티 값이며 자바스크립트에서 사용되는 모든 값은 객체의 프로퍼티 값이 될 수 있으므로 어떤 타입의 값이라도 배열의 요소가 될 수 있다고 한다. 인덱스로 접근하는 배열의 구조적인 단점을 보완하기 위해 대부분의 모던 자바스크립트 엔진은 배열을 일반 객체와 구별하여 배열처럼 동작하도록 최적화 되어있다고 한다.
2. Linked List(연결리스트)
- 저장하려는 데이터(Node)를 메모리 공간에 분산해 할당하여 연결
- 노드(Node)는 데이터를 담는 변수 하나와 다음 노드를 가르키는 변수 하나로 구성되어 있다.
- 첫 노드의 주소만 가지고 다른 모든 노드에 접근 할 수 있다.
- 배열에서 초기 크기를 알아야 하는 단점을 상쇄
- 연결리스트의 데이터 참조는 O(n)의 성능을 가진다.
- 데이터의 삽입과 삭제가 자주 일어난다면 연결리스트가 적합하다.
연결리스트의 추상자료형
1. printAll() - 모든 데이터 출력
2. clear() - 모든 데이터 제거
3. insertAt(index, data) - 인덱스 삽입
4. insertLast(data) - 마지막 삽입
5. deleteAt(index) - 인덱스 삭제
6. deleteLast() - 마지막 삭제
7. getNodeAt(index) - 인덱스 읽기
예제코드)
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
this.count = 0;
}
printAll() {
let currentNode = this.head;
while (currentNode !== null) {
console.log(currentNode.data);
currentNode = currentNode.next;
}
}
clear() {
this.head = null;
this.count = 0;
}
insertAt(index, data) {
// 범위를 넘어가는 경우에 대한 예외처리
if (index > this.count || index < 0)
throw new Error("범위를 넘어갔습니다.");
let newNode = new Node(data);
if (index === 0) {
newNode.next = this.head;
this.head = newNode;
} else {
// 원하는 인덱스에 삽입
let currentNode = this.head;
// 목표인덱스 전까지 이동
for (let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
newNode.next = currentNode.next;
currentNode.next = newNode;
}
this.count++;
}
insertLast(data) {
this.insertAt(this.count, data);
}
deleteAt(index) {
if (index >= this.count || index < 0)
throw new Error("제거할 수 없습니다.");
let currentNode = this.head;
// head가 위치하는 node 제거할 때
if (index === 0) {
let deletedNode = this.head;
this.head = this.head.next;
this.count--;
return deletedNode;
} else {
for (let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
let deletedNode = currentNode.next;
currentNode.next = currentNode.next.next;
this.count--;
return deletedNode;
}
}
deleteLast() {
return this.deleteAt(this.count - 1);
}
getNodeAt(index) {
if (index >= this.count || index < 0) return;
let currentNode = this.head;
for (let i = 0; i < index; i++) {
currentNode = currentNode.next;
}
return currentNode;
}
}
export { Node, LinkedList };
3. Stack(스택)
- FILO(First In Last Out): 먼저 들어간 데이터가 나중에 나오는 규칙
- 되돌리기 작업, 문법에러 검사 등에 쓰일 수 있다.
예제코드)
import { LinkedList } from "./LinkedList.mjs";
class Stack {
constructor() {
this.list = new LinkedList();
}
push(data) {
this.list.insertAt(0, data);
}
pop() {
try {
return this.list.deleteAt(0);
} catch (e) {
return null;
}
}
// 데이터 참조하는 함수
peak() {
return this.list.getNodeAt(0);
}
isEmpty() {
return this.list.count === 0;
}
}
export { Stack };
<br/ >
4. Queue(큐)
- FIFO(First In First Out): 먼저 들어간 데이터가 먼저 나오는 규칙
head와tail을 이용해 구현(이중 연결리스트)
그냥 연결리스트를 이용하여 구현할 경우head에서부터 하나씩 참조해야 하기 때문에 O(n)의 성능이지만 이중연결리스트를 이용하여tail을 사용하면 O(1)의 성능으로 구현 할 수 있다.
class Node {
constructor(data, next = null, prev = null) {
this.data = data;
this.next = next;
this.prev = prev;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.count = 0;
}
printAll() {
let currentNode = this.head;
while (currentNode !== null) {
console.log(currentNode.data);
currentNode = currentNode.next;
}
}
clear() {
this.head = null;
this.count = 0;
}
insertAt(index, data) {
// 범위를 넘어가는 경우에 대한 예외처리
if (index > this.count || index < 0)
throw new Error("범위를 넘어갔습니다.");
let newNode = new Node(data);
// head에 삽입하는 경우
if (index === 0) {
newNode.next = this.head;
if (this.head !== null) {
this.head.prev = newNode;
}
this.head = newNode;
} else if (index === this.count) {
// 마지막 index에 추가하는 경우
newNode.next = null;
newNode.prev = this.tail;
this.tail.next = newNode;
} else {
// 원하는 인덱스에 삽입
let currentNode = this.head;
// 목표인덱스 전까지 이동
for (let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
newNode.next = currentNode.next;
newNode.prev = currentNode;
currentNode.next = newNode.next;
currentNode.next = newNode;
newNode.next.prev = newNode;
}
if (newNode.next !== null) {
// 새로 삽입한 노드가 마지막 노드이라면
this.tail = newNode;
}
this.count++;
}
insertLast(data) {
this.insertAt(this.count, data);
}
deleteAt(index) {
if (index >= this.count || index < 0)
throw new Error("제거할 수 없습니다.");
let currentNode = this.head;
// head가 위치하는 node 제거할 때
if (index === 0) {
let deletedNode = this.head;
if (this.head.next === null) {
// head의 다음 노드가 null
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
this.head.prev = null;
}
this.head = this.head.next;
this.count--;
return deletedNode;
} else if (index === this.count - 1) {
//마지막 노드를 삭제하는 경우
let deletedNode = this.tail;
this.tail.prev.next = null;
this.tail = this.tail.prev;
this.count--;
return deletedNode;
} else {
// head와 tail이 아닌 노드를 삭제할 때
for (let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
let deletedNode = currentNode.next;
currentNode.next.prev = currentNode;
currentNode.next = currentNode.next.next;
this.count--;
return deletedNode;
}
}
deleteLast() {
return this.deleteAt(this.count - 1);
}
getNodeAt(index) {
if (index >= this.count || index < 0) return;
let currentNode = this.head;
for (let i = 0; i < index; i++) {
currentNode = currentNode.next;
}
return currentNode;
}
}
export { Node, DoublyLinkedList };
5. Deque(덱)
- 데이터의 삽입과 제거를
head와tail양쪽에서 자유롭게 할 수 있는 자료구조 - 덱을 이용하면 스택과 큐를 모두 구현할 수 있다.
덱의 추상 자료형
1. printAll()
2. addFirst(data)
3. removeFirst()
4. addLast(data)
5. removeLast()
6. isEmpty()
import { DoublyLinkedList } from "./DoublyLinkedList.mjs";
class Deque {
constructor() {
this.list = new DoublyLinkedList();
}
printAll() {
this.list.printAll();
}
// O(1)
addFirst(data) {
this.list.insertAt(0, data);
}
// O(1)
removeFirst() {
this.list.deleteAt(0);
}
addLast(data) {
this.list.insertAt(this.list.count, data);
}
removeLast() {
return this.list.deleteLast();
}
isEmpty() {
return this.list.count === 0;
}
}
export { Deque };
6. Hash Table(해시 테이블)
- 언어에 따라 해시(Hash), 맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary)라고 부르기도 한다.
- 해시와 테이블이 합쳐진 자료구조
- 테이블에서의 메모리 낭비를 보완하기 위해 해시 함수를 만들었고, 해시 함수를 이용한 새로운 테이블의 인덱스를 가지고 데이터를 보관한다.
key와value로 구성되어있고,value는 연결리스트로 이루어져 있다.- 좋은 해시함수는 데이터를 골고루 분배시키는 함수이다.
- 빠른 데이터의 읽기, 삽입, 삭제
- 해시함수에 따라 공간의 효율성은 좋지 못할 수도 있다.
해시테이블의 추상자료형
1. get(key) - 데이터 읽기
2. set(key, value) - 데이터 삽입
3. remove() - 데이터 제거
import { DoublyLinkedList } from "./DoublyLinkedList.mjs";
class HashData {
constructor(key, value) {
this.key = key;
this.value = value;
}
}
class HashTable {
constructor() {
this.arr = [];
for (let i = 0; i < 10; i++) {
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) {
if (currentNode.data.key === key) return currentNode.data.value;
currentNode.currentNode.next;
}
return null;
}
remove(key) {
let list = this.arr[this.hashFunction(key)];
let deletedIndex = 0;
while (!currentNode) {
if (currentNode.data.key === key) return list.deleteAt(deletedIndex);
currentNode.currentNode.next;
deletedIndex++;
}
return null;
}
}
export { HashTable };7. Set
- 자료구조의 중복을 허용하지 않음
- hash table을 이용하기 때문에 hash set 이라고도 불림
key가key의 역할을 함과 동시에value가 된다.
셋의 추상자료형
1. add(data) - 데이터 삽입
2. isContain(data) - 데이터 체크
3. remove(data) - 데이터 제거
4. clear() - 셋 비우기
5. isEmpty() - 셋이 비었는지 체크
6. printAll() - 모든 데이터 출력
import { HashTable } from "./HashTable.mjs";
class HashSet {
constructor() {
this.hashTable = new HashTable();
}
add(data) {
if (!this.hashTable.get(data)) this.hashTable.set(data, -1);
}
isContain(data) {
return this.hashTable.get(data);
}
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) {
console.log(currentNode.data.key);
currentNode = currentNode.next;
}
}
}
}
export { HashSet };
회고
강의의 자료구조파트를 듣고나서 정리를 한 번 하면 더 정리가 잘 되겠다 싶어 기록을 남기게 됐다. 이해하기 쉬운 그림을 함께 보여주면서 설명을 하셔서 개념을 책으로만 접하는 것 보다 이해가 잘 됐다. 그리고 직접 자료구조를 구현해 보니까 글로만 접했을 때 보다 훨씬 구조적인 이해가 잘 되었다. 여러모로 개념을 이해하기에 좋은 강의라고 생각한다. 알고리즘 파트부분도 얼른 완강 해서 또 정리해야지!
