자료구조(Data Structor)
효율적인 접근/수정을 가능하게 하는 자료의 구조를 의미하는 용어로,
데이터 값들의 모임이나 관계를 의미하기도 한다.
자료구조는 설계된 완성도가 높을수록 실행시간/메모리 용량과 같은 자원의 사용량을 감소시킬수 있기 때문에 효율적인 알고리즘을 제작에 도움을 준다.
추상 자료형 (ADT, Abstract Data Type)
데이터의 추상적 형태와 다루는 방법만을 정해놓은 것을 의미하며, 큐, 스택, 트리, 연결 리스트 등이 해당된다.
스택 (Stack)
한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조로
나중에 들어간 데이터가 먼저 나오는 LIFO(Last In First Out) 방식으로 데이터를 처리한다.
가장 큰 예로 브라우저의 뒤로가기 등이 있는데, 이전 데이터를 기억해야 할때 사용된다
보통 다음과 같은 연산이 존재한다.
-
top : 스택의 최상위 데이터 반환
-
pop : 스택의 최상위 데이터 삭제 및 반환
-
push : 데이터 삽입
-
empty : 스택이 비었는지 확인, 비었다면 1 아니면 0을 반환
배열을 통해 다음과 같이 구현할 수 있다.
class Stack {
constructor() {
this.memory = [];
}
top() {
return this.memory[this.memory.length - 1];
}
pop() {
return this.memory.pop();
}
push(data) {
this.memory.push(data);
}
empty() {
if (this.memory.length===0) {
return 1;
} else {
return 0;
}
}
}
const stack = new Stack();큐 (Queue)
양 쪽 방향에서 각각 데이터의 입력과 출력을 담당해 수행하는 선형 자료 구조로 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 방식으로 데이터를 처리한다.
예시로 프린터의 출력 처리나 윈도우 시스템의 메시지 처리기, 프로세스 관리 등이 있는데, 데이터를 시간 순서대로 처리해야 할때 사용된다.
보통 다음과 같은 연산이 존재한다.
- 기능
- enqueue : 데이터 삽입
- dequeue : 데이터 추출
배열을 통해 다음과 같이 구현할 수 있다.
class Queue {
constructor() {
this.memory = [];
}
enqueue(data) {
this.memory.push(data);
}
dequeue() {
return this.memory.shift();
}
}
const queue = new Queue();트리 (tree)
계층 구조를 가지는 비선형 자료구조이자 그래프의 일종으로
한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다.
노드는 주로 다음과 같이 구분된다.
-
root node : 최상위 노드
-
ancestor node : 특정 하위 노드에서 한 계층 이상으로 연결되어있는 노드
- root node는 leaf node의 ancestor node이다.
-
parent node : 자신과 연결된 하위 노드를 가진 노드
-
child node : 한 상위 노드에 종속되는 하위 노드
-
leaf node(혹은 terminal node) : 하위 노드를 가지지 않는 최하위 노드
-
internal node : 최하위 노드가 아닌 노드
class Node {
constructor(data, children = []) {
this.data = data;
this.children = children;
}
}
const tree = new Node(1, [
new Node(2),
new Node(3),
new Node(4, [
new Node(5)
])
]);
function printAllData(tree) {
console.log(tree.data);
for (let child of tree.children) {
printAllData(child);
}
}
function sumAllData(tree) {
let sum = 0;
function searchTree(tree) {
sum += tree.data;
for (let child of tree.children) {
searchTree(child)
}
}
console.log(sum)
}
printAllData(tree);
// 1
// 2
// 3
// 4
// 5
sumAllData(tree); // 15연결 리스트 (Linked list)
각 노드가 데이터와 포인터를 지니며, 한 줄로 연결되어 있는 선형 자료 구조이다.
다음과 같은 구조를 가지고 있다.
- node : 데이터와 포인터를 가지는 저장 개체
- pointer : 다른 노드를 가리키며, 연결을 담당하는 요소
종류로는 단일 연결 리스트, 이중 연결 리스트 등이 있으며,(추후에 큐와 트리의 종류와 함께 다룰 예정이다.)
연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 가능하며, 시간복잡도가 O(1)이라는 장점을 지닌다.
그러나 배열이나 트리 구조와 달리 특정 위치에 존재하는 데이터를 검색하는데 걸리는 시간 복잡도가 O(n)이라는 단점을 지닌다.
class 문법을 통해 다음과 같이 구현할 수 있다.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor(){
this.head = new Node('head');
}
addtail(newData) {
let tailNode = new Node(newData);
let curNode = this.head;
while(curNode.next != null) {
curNode = curNode.next;
}
curNode.next = tailNode;
}
select(nodeData){
let curNode = this.head;
while(curNode.data !== nodeData) {
if(curNode.next===null) return alert(`List have no ${nodeData}`)
curNode = curNode.next;
}
return curNode;
}
selectPrev(nodeData) {
let curNode = this.head;
while(curNode.next.data !== nodeData) {
if(curNode.next===null) return alert(`List have no ${nodeData}`)
curNode = curNode.next;
}
return curNode;
}
insert(newData, pointer) {
let insertNode = new Node(newData);
let current = this.select(pointer);
insertNode.next = current.next;
current.next = insertNode;
}
remove(removeData) {
let preNode = this.selectPrev(removeData);
preNode.next = preNode.next.next;
}
printAll() {
let result = [];
let curNode = this.head;
while(curNode.next !== null){
result.push(curNode.next.data);
curNode = curNode.next;
}
return result.join(' ')
}
}
const linkedList = new LinkedList();
linkedList.addtail(1);
linkedList.addtail(2);
linkedList.addtail(3);
linkedList.insert(4,1);
linkedList.remove(2)
linkedList.addtail(5)
console.log(linkedList.select(4).next.data) // 3
console.log(linkedList.printAll()) // 1 4 3 5