자료구조

승진·2019년 9월 28일

자료구조

자료구조란?

사전적인 의미는 자료(Data)의 집합을 의미하고, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이다.

자료구조를 사용하는 목적

Data를 더 효율적으로 저장하고 관리하기 위해 사용되며, 잘 선택된 자료구조는 실행시간을 단축시켜주거나 메모리 용량의 절약을 이끌어 낼 수 있다.

자료구조의 선택 기준

자료의 처리 시간
자료의 크기
자료의 활용 빈도
자료의 갱신 정도
프로그램의 용이성

자료구조의 특징

효율성 - 자료구조를 사용하는 목적은 효율적인 데이터의 관리 및 사용이다. 따라서 목적에 맞게 적절한 자료구조를 선택하여 사용하는 것이 업무의 효율을 높혀준다.
추상화 - 복잡한 자료, 모듈, 시스템 등으로 부터 핵심적인 개념을 간추려 내는 것이다. 자료구조를 구현할 때 중요한 것은 어느 시점에 데이터를 삽입하고, 어느 시점에서 이 데이터를 어떻게 사용할 것인지에 대해 초점을 맞출 수 있기 때문에 구현 외적인 부분에 더 시간을 쏟고 알고리즘 자체에는 중점을 두지 않는다.
재사용성 - 자료구조를 설계할때 특정 프로그램에서만 동작하게 설계하지 않는다. 다양한 프로그램에서 동작할 수 있도록 범용성 있게 설계하기 때문에 해당 프로젝트가 아닌 다른 프로젝트에서도 사용할 수 있다.

자료구조의 분류

자료구조는 크게 선형과 비선형으로 나뉜다. 선형 자료구조의 경우 데이터가 일렬로 나열되어 있는 것을 뜻하고, 비 선형 자료구조는 특정한 형태를 띄고 있는 것을 뜻한다.

선형구조

배열 (Array)
연결 리스트 (Linked List)
스택 (Stack)
큐 (Queue)

비선형 구조

트리 (Tree)
그래프 (Graph)

연결 리스트 (Linked List)

가장 기본인 연결리스트는 여러 개의 노드로 이루어져 있다. 노드는 데이터와 다음 노드가 뭔지 알려주는 주소를 갖고있고 연결 리스트는 새로운 데이터를 추가하거나, 데이터의 위치를 찾거나, 제거하는 기능이 있어야 한다.
자바스크립트에는 이미 구현이 되어있는데 이것이 배열이다. [1, 2, 3, 4]가 있다면 1234는 데이터이고 각각의 인덱스가 주소이다.

연결 리스트 특징

data의 입력과 삭제가 자유롭다. 배열의 경우 중간의 data를 삭제하거나, 삽입하려 한다면 배열 중간에 빈 공간이 생기거나, data를 밀어내야 하는데 연결 리스트의 경우 이러한 현상이 발생하지 않는다.

(위치에 상관없이) 새로운 데이터를 입력할 때, 새로운 데이터는 들어가고자 하는 위치에 해당하는 앞 node의 tail에 자신의 data를 연결하고, 자신의 tail을 원래 자신의 앞 node tail에 연결돼 있던 후위 node와 연결하여 입력을 수행한다.

스택 (Stack)

Stack : 자료의 입출력이 한 방향에서만 이루어지는 자료구조

후입선출의 자료구조, 스택은 실생활에도 많이 사용되는 자료구조 중 하나로, 연결 리스트인데 뒤로 넣고 뒤로만 뺄 수 있다.
자바스크립트의 배열로 생각하면 shift, unshift 없이 push와 pop만 있다고 생각할 수 있다.
push와 pop이라는 메소드 이름도 스택에서 나온 것이고, 또 한가지 메소드는 stakTop으로 스택의 마지막 요소를 알려준다.

const stack = [];

stack.push(2);       // stack is now [2]
stack.push(5);       // stack is now [2, 5]

const i = stack.pop(); // stack is now [2]

alert(i);            // console.log(i);

큐 (Queue)

Queue : 한 방향에서 입력이 이뤄지고, 그 반대편 방향에서 출력이 이루어지는 자료구조

선입선출의 자료구조. 대기열이라고도 한다. Queue라는 단어 자체가 표 같은 것을 구매하기 위해 줄서는 것을 의미한다. 뒤에서 들어가고 앞에서 빠지는 구조로 자바스크립트의 배열로 생각하면 push와 shift 메소드만 있고 추가로 제일 앞에 데이터를 알 수 있는 front가 있다.

const queue = [];
queue.push(2);         // enqueue
queue.push(5);         // enqueue
const i = queue.shift(); // dequeue
alert(i);

트리 (Tree)

자료구조에서의 트리는 부모-자식 관계로 정의하고, 부모에서 자식으로 간선이 이어져 있는 유향 그래프이다.
하나의 root Node와 다수의 subtree Node 들의 집합으로 트리는 root와 subtree의 관계를 parent와 child 관계로 표현 할 수 있고, 각각의 subtree들은 자신 아래에 또 다른 subtree를 두어 parent, child 관계를 가질 수 있다.

보통 그냥 Tree 자료구조를 쓰는 경우는 많지 않고, Tree 중에서 이진 탐색 트리(Binary Search Tree)를 이용해 검색에 활용하기 위해 많이 쓴다.

마무리

자료구조에 대해 알기 전에도 이미 자료구조를 사용하고 있었고, 내용들을 공부하면서 코드를 작성할 때 상황과 목적에 맞게 어떤 방식을 사용해야 하는지에 대해 알게 됐다. 자바스크립트 덕분에 복잡한 과정들을 편하게 사용하고 있었다는 것을 알게 되어 감사함을 느끼고 기본적인 지식의 중요성을 깨달았다.