자바스크립트로 자료구조 연습하기 자료구조 data structure 정리
개발하면서 꼭 알아야할 기본 지식을 쌓고자 작성하게되었다.
자료구조란?
데이터에 편리하게 접근하고 변경하기 위해서 데이터를 저장하거나 조직하는 방법을 말한다. 즉 데이터를 얼마나 효율적으로 저장 및 관리하고 메모리를 절약할건지, 실행시간을 단축시킬건지 등에 목적을 두고있다.
자료구조의 특징
작업의 효율성, 추상화, 재사용성을 증가시키기 위해 상황에 따른 적절한 자료구조를 선택할 필요가 있다. 특히 대규모의 데이터를 관리 및 활용하는 경우에는 특히 더 중요하다.
자료구조의 분류
대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는데 특화되어있다.
많은 자료구조중에 상황에 적합한 자료구조를 찾아 사용하면 빠르게 해결할수있다.
1)단순구조
정수, 실수, 문자, 문자열 등과 같이 자료값을 사용하기 위해서 기본적으로 컴퓨터가 제공하는 기본 자료형을 의미한다.
2)선형 자료구조(Linear Data Structure)
자료들 간의 앞뒤 관계가 1:1인 선형 관계를 의미한다
1. 배열
배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어있는 자료구조이다. 메모리상에서 연속적으로 저장되어 있는 특징을 갖기때문에 index를 통한 접근이 용이하다. 배열의 크기는 처음 생성할때 정하며 이후에는 변경할수없다.
2. 연결리스트
어떤 데이터를 저장할 때 데이터들을 메모리 공간에 분산해주고 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장한다
- Abstract Data Type (추상자료형)
- printAll() : 모든 데이터 출력
- clear() : 연결리스트 모든 원소제거
- insertAt() : 원하는 인덱스 삽입
- insertLast() : 마지막 데이터 뒤 삽입
- deleteAt() : 인덱스의 데이터 삭제
- deleteLast() : 마지막 데이터 제거
- getNodeAt() : 원하는 인덱스 데이터 읽기
- 단순연결리스트
시작부분에 head가 있으며 노드에 값과 다음 노드를 가리키는 주소값을 가지고 있다. 마지막 노드의 링크 값은 NULL을 가리켜야 한다. (순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수가 없어 일반적으로 탐색 속도가 떨어진다.)
- 이중연결리스트
양방향으로 이동할 수 있는 리스트로 노드에서 다음 노드를 가리키는 주소값과 이전 노드를 가리키는 주소값 두개를 가지고 있다. 양방향으로 이동할 수 있다는 장점으로 예를들어 마지막 데이터(tail)를 삭제할 때 삭제하고 난 다음, 이전 노드를 마지막 데이터(tail)로 지정해주기 위해 다시 한번 더 탐색을 하지 않아도 된다.
- 원형연결리스트
마지막 노드의 넥스트값이 null이 아닌 첫번째 노드의 주소를 가리키는 연결리스트. 리스트의 끝에 노드를 삽입,삭제하는 연산이 단순 연결리스트보다 효율적이다. 헤드포인터에서 시작하여 모든 노드를 거쳐 마지막에 삽입하는것이 아니라 헤드포인터가 마지막 노드를 가리키도록 구성하면 리스트의 끝에 노드를 쉽게 삽입할수있다.
배열과 연결리스트 비교
| 비교 | 배열 | 연결리스트 |
|---|---|---|
| 장점 | 인덱스를 통한 빠른 접근이 가능하다. | 삽입과 삭제가 용이하다. 중간에 하나의 데이터를 삽입하려면 서로 다음에 위치할 노드만 가리켜주면 되기때문에 쉽다. |
| 단점 | 삽입과 삭제가 오래걸린다. 중간에 하나의 데이터를 삽입하기위해 모두 한칸씩 뒤로 밀려져야하고 배열 중간에 있는 데이터가 삭제되면 공간 낭비가 발생한다. | 데이터들이 전부 떨어져있기때문에 바로 접근이 불가능하며 첫번째 노드에서 다음노드를 찾고 또 다음노드를 찾고 찾아야 접근할수있다.(O(n)) |
| 용도 | 시작주소를 알고있고 연속적으로 나열되어있어 빠른 접근이 가능 (O(1))하기 때문에 탐색이 요구되고 데이터의 삽입과 삭제가 적을때 용이 | 삽입과 삭제 연산이 잦고, 검색빈도가 적을때 용이 |
3. 스택
스택(stack)은 쌓다라는 의미로 데이터를 쌓아 올린 형태의 자료구조이다.
LIFO(Last In First Out)라고 불리는것처럼 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다.
ex)그림판 실행취소, 프링글스먹을때
- Abstract Data Type (추상자료형)
- push() : 데이터삽입
- pop() : 마지막에 저장된 데이터 제거, 삭제된 데이터 반환
- peek() : 데이터참조, 마지막에 저장된 요소를 반환하되 삭제하지 않음
- isEmpty() : 데이터체크 (스택이 빈 경우 true, 그렇지 않으면 false)
자바스크립트로 연결리스트를 사용해 스택 구현하기
class Stack{
constructor(){
this._count = 0;
this.head = null
}
count(){
return this._count;
}
push(item){
const node = {item:item, next:this.head}
this.head = node
this._count++;
}
pop(){
const node2 = this.head
this.head = node2.next //banana의 이전노드인 apple이 this.head로 업데이트되고 바나나는 삭제.
this._count--;
return node2.item
}
peek(){
if(this.head === null){
throw new Error('nothing is here')
}
return this.head.item
}
isEmpty(){
return (this._count == 0)
}
}
export {Stack}import { Stack } from "./Stack2.mjs"
const stack = new Stack()
stack.push('apple')
stack.push('banana')
console.log(stack.pop()) //banana
console.log(stack.isEmpty()) //false4. 큐
큐는 스택과 다르게 먼저 들어온것이 먼저 나가는 FIFO(First In First Out)의 구조를 가지고있다. 스택과는 다르게 한쪽 끝에서는 삽입작업이 다른 한쪽끝에서는 삭제 작업이 나누어져서 이루어진다.
ex)은행업무, 프로세스 관리, 맛집 줄설때
- Abstract Data Type (추상자료형)
- enqueue : 데이터삽입
- dequeue : 데이터제거
- front : 먼저들어온 데이터 참조.
- isEmpty : 리스트가 비었는지 확인
자바스크립트에서 세가지방법으로 큐 구현하기
1)배열 : 구현이 쉽고 간단하나 삽입/삭제를 위해 배열 apis 메소드인 push()로 추가하고, shift()를 사용해서 제거할경우 모든 인덱스를 재조정해야하기때문에 시간복잡도 면에서 좋지않다.
2)객체 : 객체를 이용해서 큐를 구현할수있다. 삽입/삭제 연산이 배열보다 훨씬 빠르지만 큐의 요소가 많아질수록 객체의 프로퍼티도 많아지며, 이는 메모리 공간을 더 많이 차지함.
const queue = {
items: {}, // 객체를 사용하여 큐 요소 저장.
head: 0, // 큐의 맨 앞 요소의 인덱스 저장.
tail: 0, // 큐의 맨 뒤 요소의 인덱스 저장.
enqueue(item) { // 큐에 요소 추가.
this.items[this.tail] = item;
this.tail++;
},
dequeue() { // 큐에서 요소 삭제하고 반환.
if (this.head === this.tail) {
return undefined;
}
const item = this.items[this.head];
delete this.items[this.head];
this.head++;
return item;
},
front() { // 큐의 맨 앞 요소 반환.
if (this.head === this.tail) {
return undefined;
}
return this.items[this.head];
},
size() { // 큐의 크기를 반환합니다.
return this.tail - this.head;
},
isEmpty() { // 큐가 비어있는지 여부를 반환합니다.
return this.size() === 0;
}
}3)연결리스트 : 삽입/삭제가 굉장히 빠르고 메모리공간을 효율적으로 사용할수있지만 인덱스에 바로 접근할수없어 탐색에 시간이 다소걸린다.
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Queue 클래스 정의
class Queue {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
// 큐의 끝에 데이터 추가
enqueue(data) {
let newNode = new Node(data);
if (this.tail === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.size++;
}
// 큐의 맨 앞에서 데이터 삭제
dequeue() {
if (this.head === null) {
return null;
}
let removedNode = this.head;
this.head = this.head.next;
if (this.head === null) {
this.tail = null;
}
this.size--;
return removedNode.data;
}
front(){
if(this.head === null){
return null
}
return this.head.data
}
isEmpty(){
return (this.size == 0);
}
}
let queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.getSize()); // 3
console.log(queue.front()); //15. 덱
덱(Deque)이란 Double-Ended Queue의 줄임말로 앞쪽 뒤쪽에서 모두 삽입과 삭제가 가능한 큐와 스택의 기능을 모두 가지고 있다. 연결리스트의 head와 tail을 모두 가리키는 포인터를 유지하면서 구현할수있다.
- Abstract Data Type (추상자료형)
- printAll() : 리스트의 모든 요소 출력
- addFirst() : head에 데이터 삽입
- removeFirst() : head에 데이터 제거
- addLast() : tail에서 데이터 삽입
- removeLast() : tail에서 데이터 제거
- isEmpty() : 리스트가 비었는지 체크
자바스크립트에서 연결리스트로 덱 구현하기
class Node {
constructor(data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
class Deque {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
isEmpty() {
return this.size === 0;
}
getSize() {
return this.size;
}
addFirst(data) {
const node = new Node(data);
if (this.isEmpty()) {
this.head = node;
this.tail = node;
} else {
node.next = this.head;
this.head.prev = node;
this.head = node;
}
this.size++;
}
addLast(data) {
const node = new Node(data);
if (this.isEmpty()) {
this.head = node;
this.tail = node;
} else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
}
this.size++;
}
removeFirst() {
if (this.isEmpty()) {
return null;
}
const data = this.head.data;
if (this.size === 1) {
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
this.head.prev = null;
}
this.size--;
return data;
}
removeLast() {
if (this.isEmpty()) {
return null;
}
const data = this.tail.data;
if (this.size === 1) {
this.head = null;
this.tail = null;
} else {
this.tail = this.tail.prev;
this.tail.next = null;
}
this.size--;
return data;
}
}6. 해시테이블
해시테이블은 키와 값의 쌍을 저장하는 자료구조이다.
해시테이블의 특징
- 해시 함수 (중요)
해시 함수는 키를 입력으로 받아 해시 테이블의 인덱스로 변환하는 함수이다. 해시 함수는 최대한 고르게 분포되도록 설계해야해서 매우 중요한데 이는 충돌의 확률을 줄이기 위함이다. 자바스크립트의 내장 함수인 hashCode()를 사용할 수도 있으며, 직접 구현할 수도 있다.
- 충돌 처리
해시 함수를 사용하여 서로 다른 키가 같은 인덱스를 반환할 수 있다. 이를 충돌이라고 하며, 충돌이 발생할 경우 해결 방법이 필요하다. (필자는 연결리스트를 사용해 인덱스에 값이 있냐 없냐에 따라 나눴고 값이 있으면 새로운 노드를 기존노드 옆에 추가하는 방식으로 구현했다.) 연결리스트를 통해 같은 인덱스라도 하나이상의 노드를 함께 저장할수있다
- 검색, 삽입, 삭제 연산의 시간 복잡도
연결 리스트를 사용한 해시 테이블은 검색, 삽입, 삭제 연산의 시간 복잡도가 O(1)이다. 이는 해시 함수를 사용하여 각 키를 인덱스로 변환하기 때문이다. 단, 최악의 경우 충돌이 많이 발생하면 연결 리스트의 길이가 길어져 O(n)의 시간 복잡도를 가질 수 있습니다. 그렇기 때문에 해시함수를 정말 잘 만들어야한다
- 해시 테이블의 크기 조정
해시 테이블은 초기 크기를 지정할 수 있으며, 필요에 따라 크기를 조정할 수도 있다. 크기를 조정하는 방법으로는 해시 테이블의 크기를 늘리거나 줄이는 방법이 있다. 크기를 늘릴 경우, 모든 키를 다시 해싱해야 하므로 비용이 크지만, 크기를 줄일 경우에는 일부 키가 삭제될 가능성이 있다.
Abstract Data Type (추상자료형)
- set() : 데이터삽입
- get() : 데이터읽기
- remove() : 데이터제거
자바스크립트로 연결리스트를 사용해서 해시테이블 구현하기
// 연결리스트를 구현한 Node 클래스
class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.next = null;
}
}
// 해시테이블을 구현한 HashTable 클래스
class HashTable {
constructor(size) {
this.size = size;
this.table = new Array(size);
}
// 해시 함수: key 값을 입력받아 인덱스 반환.
hashFunction(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash + key.charCodeAt(i) * i) % this.size;
}//각문자의 아스키코드 가져와서 최종값 리턴
return hash;
}
// 해시테이블에 key-value 추가.
set(key, value) {
const index = this.hashFunction(key);
if (!this.table[index]) {
this.table[index] = new Node(key, value);
} else {
let node = this.table[index];
while (node.next) { //해당 인덱스의 맨 처음 노드를 node 변수에 할당한다. 그리고 while 구문에서 node 변수가 가리키는 노드의 next 속성이 null일 때까지, 즉 연결리스트의 끝까지 계속해서 다음 노드를 찾아 이동한다. 해당노드를 찾으면 연결리스트의 끝에 새로운 노드를 추가한다.
node = node.next;
}
node.next = new Node(key, value);
}
}
// 해시테이블에서 key에 해당하는 value 반환.
get(key) {
const index = this.hashFunction(key);
let node = this.table[index];
while (node) {
if (node.key === key) {
return node.value;
}
node = node.next;
}
return null;
}
// 해시테이블에서 key에 해당하는 key-value 삭제.
remove(key) {
const index = this.hashFunction(key);
let node = this.table[index];
let prev = null;
while (node) {
if (node.key === key) {
if (prev) {
prev.next = node.next;
} else {
this.table[index] = node.next;
}
return true;
}
prev = node;
node = node.next;
}
return false;
}
}
// 예제
const table = new HashTable(5);
table.set("apple", 5);
table.set("banana", 2);
table.set("cherry", 9);
console.log(table.get("apple")); // 5
console.log(table.get("banana")); // 2
console.log(table.get("cherry")); // 9
table.remove("banana");
console.log(table.get("banana")); // null
7. 셋
데이터의 중복을 허용하지 않는 자료구조, 해시테이블을 사용하기 때문에 해시셋이라고도 불린다. 셋은 해시테이블의 value값은 사용하지 않고 key만 사용해서 구현한다.
Abstract Data Type (추상자료형)
- add(data) : 데이터 삽입
- isContain(data) : 중복되는 데이터체크
- remove(data) : 데이터제거
- clear() : 셋 비우기
- isEmpty() : 셋이 비었는지 체크
- printAll() : 모든 데이터 출력
class Node {
constructor(key, value, next=null) {
this.key = key;
this.value = value;
this.next = next;
}
}
class HashSet {
constructor(size) {
this.size = size;
this.table = new Array(size);
}
// 해시 함수: 값을 입력받아 인덱스를 반환.
hashFunction(value) {
let hash = 0;
for (let i = 0; i < value.length; i++) {
hash = (hash + value.charCodeAt(i) * i) % this.size; //모듈러스 연산(%)을 사용해서 인덱스는 항상 size보다 작거나 같도록 만들어줌.
}
return hash;
}
// 해시셋에 값 추가.
// 인덱스가 겹쳤을때 추가해주는 방식으로 구현
add(value) {
const index = this.hashFunction(value);
if (!this.table[index]) {
this.table[index] = new Node(index, value);
}
else {
let current = this.table[index];
while (current) {
if (current.value === value) {
return false;
}
if(!current.next){
current.next = new Node(index, value)
return true
}
}
}
}
// 해시셋에서 값 삭제.
remove(value) {
const index = this.hashFunction(value);
let current = this.table[index];
let prev = null;
while (current) { //current가 null이 될때까지
if (current.value === value) {
if (prev) {
prev.next = current.next;
} else {
this.table[index] = current.next;
}
return;
}
prev = current;
current = current.next;
}
}
// 해시셋에 값이 포함되어 있는지 확인.
isContain(value) {
const index = this.hashFunction(value);
let current = this.table[index];
while (current) {
if (current.value === value) {
return true;
}
current = current.next;
}
return false;
}
clear() {
this.table = new Array(this.size);
}
isEmpty() {
for (let i = 0; i < this.table.length; i++) {
if (this.table[i] !== null && this.table[i] !== undefined) {
return false;
}
}
return true;
}
printAll(){
let text = '[';
for (let i = 0; i < this.table.length; i++) {
let node = this.table[i];
while (node) {
if (node.next) {
text += `${node.value}, `;
} else {
text += `${node.value}`;
}
node = node.next;
}
if (i < this.table.length - 1) {
text += ', ';
}
}
text += ']';
return text;
}
}
const set = new HashSet(5); //5인 새로운 배열 생성, 해시테이블의 크기 5 (인덱스 0~4)
set.add("apple"); //index:4
set.add("banana"); //index:3
set.add("orange"); //index:0
set.add("cherry"); //index:4
set.add("watermelon"); //index:3
//인덱스 1,2에 노드는 없는 상황
console.log(set.has("apple")); // true
console.log(set.has("banana")); // true
console.log(set.has("orange")); // true
console.log(set.has("cherry")); // true
console.log(set.has("watermelon")); // true
console.log(set.printAll()) //[orange, , , banana, watermelon, apple, cherry]
console.log(set.isEmpty()) //false
set.remove("apple");
set.remove("banana");
set.remove("orange");
set.remove("cherry");
set.remove("watermelon");
console.log(set.printAll()) //[, , , , ]
console.log(set.isEmpty())//true3)비선형구조
자료들 간의 앞뒤 관계가 1:다 또는 다:다인 비선형 관계를 의미한다.
- 트리 : 부모 노드 밑에 여러 자식 노드가 연결되는 구조로, 자식 노드가 부모가 되어 다시 각각의 자식 노드가 연결되는 재귀적인 형태의 자료구조이다.
- 그래프 : 노드(Node)/정점(Vertex)과 이들 사이를 연결하는 엣지(Edge)로 구성된 자료구조를 의미한다. 그래프는 방향이 있을 수도 없을 수도 있으며 다양한 구조로 설계된다.
4)파일구조
서로 관련있는 필드(Field)로 구성된 레코드(Record) 집합인 파일에 대한 자료구조이다. 보조 기억장치에 데이터가 실제로 기록되는 형태를 말한다. 순차 파일, 색인 파일, 직접 파일 등이 있다.
독학으로 여러 자료 참조하며 공부하고있습니다.
잘못된 정보가 있거나 누락된 참조가 있으면 부탁드립니다 :)
https://re-code-cord.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%99%9C-%EA%B7%B8%EB%A0%87%EA%B2%8C-%EC%A4%91%EC%9A%94%ED%95%A0%EA%B9%8C
