TIL 34 자료구조와 알고리즘 - 자료구조

자료구조와 알고리즘에 대해 공부를 안했더니 대학다니면서 공부했던 내용들을 다 잊어버리기 시작했다. 그래서 다시 상기시키고 복습할 겸 정리를 했다. java에서는 자료구조 메소드들이 많이 내장되어 있어서 자주 사용했던 기억이 있는데 프론트엔드 개발자를 하기로 마음먹고 공부하면서 javaScript에는 있는 것도 있고 없는 것도 있어서 뭔가 소홀해졌던 내 자신이 밉다. 우선 java에 내장되어 있는 메소드들을 통해 종류를 알아보고 javascript에서 자주 사용되는? 것들을 더 자세히 다루겠다.

Stack

LIFO(Last In, First Out), FILO(First In, Last Out)구조이다. 먼저 들어온 데이터가 제일 나중에 나가는 구조이고, 상자에 무엇을 넣고 빼는 순서를 생각하면 된다.

삽입 : push
삭제 : pop
읽기 : peek

const stack = [];
stack.push('a');
stack.push('b');
stack.push('c');

console.log(stack); // [a, b, c]

let peek = stack[stack.length - 1];
console.log(peek); // c

stack.pop();
console.log(stack); // [a, b]

Queue

FIFO(First In, First Out), LILO(Last In, Last Out)구조이다. 한쪽 끝(rear)에서는 삽입만 이루어지면 다른 끝(front)에서는 삭제만 이루어지는 구조이다. 쉽게 말해 먼저 삽입된 것이 제일 먼저 빠져나오는 구조이다.

enqueue : 데이터 삽입
dequeue : 데이터 출력

const queue = [];

queue.push('a'); //enqueue
queue.push('b'); //enqueue
console.log(queue); // [a, b]

queue.shift(); //dequeue 'a'
console.log(queue); // [b]
queue.shift(); //dequeue 'b'

Linked List(연결리스트)

여러 노드들이 한 방향을 가리키는 구조이다. 가장 처음 노드를 had라고 하고, 마지막 노드를 tail이라고 한다.

function linkedList(val) {
  this.val = val;
  this.next = null;
}

let head = new linkedList(0);
let node1 = new linkedList(1);
let node2 = new linkedList(2);
let tail = new linkedList(3);

haed.next = node1;
node1.next = node2;
node2.next = tail;

Double Linked List(이중 연결리스트)

연결리트가 한방향으로 연결되어 있다면 이중 연결리스트는
노드끼리 서로 연결되어 있다. 노드들은 본인의 이전 노드와 다음 노드를 기억한다.

이전 노드(previous)와 다음 노드(next)로 구성되어있다. 양방향으로 연결되어 있기 때문에 노드를 탐색할 때 양쪽으로 가능하다.

이전 노드를 지정하기 위해 변수를 하나 더 사용해야한다. 메모리 사용이 좀 더 많아지지만 장점이 크기 때문에 현실에서는 대부분 이중 연결리스트를 사용한다.

function doubleLinkedList(val){
  this.val = val;
  this.next = null;
  this.prev = null;
}

let head = new doubleLinkedList(0);
let node1 = new doubleLinkedList(1);
let node2 = new doubleLinkedList(2);
let tail = new doubleLinkedList(3);

head.next = node1;
node1.next = node2;
node2.next = tail;

tail.prev = node2;
node2.prev = node1;
node1.prev = head;

Map

Map은 자바스크립트의 객체와 비슷하지만 약간 다르다. Map은 키에 다양한 자료형을 허용한다. 객체는 Key를 문자형으로 변환한다. 하지만 Map은 타입을 변형시키지 않고 그대로 유지한다.

O(1)의 시간복잡도를 가지고 있어 시간복잡도를 줄이는데 사용하면 유용하다.

1. Key는 중복일 수 없다.
2. Key와 Value 중 하나만 존재하지 않는다.
3. Value는 중복이 가능하다.

let map = new Map();
map.set('1', 'string');
map.set(1, 'number');
map.set(true, 'boolean');

for (let types of map.keys()) {
  console.log(typeof types);
  // string
  // number
  // boolean
}

console.log(map.size); // 3

Set

Set은 중복되지 않는 값을 모아놓은 것이다. key값은 0부터 순서대로 index가 매겨지고 중복된 값을 걸러준다.

let set = new Set();

set.add("son");
set.add("kwak");
set.add("chi");
set.add("son");
set.add("chi");

console.log(set)
// {0: 'son' 1: 'kwak' 2: 'chi'}

set.has('son') // set 내에 값이 있으면 true, 없으면 false 반환
set.size; // set에 있는 값의 갯수
set.clear(); // set을 비운다.