Linear Data Structure

프로그램이 실행되면 메모리에 프로세스가 저장된다. 더불어, 프로세스 내에서 어떤 작업을 실행하기 위해 여러 스레드 가 존재하며, 각각의 스레드 안에는 사용된 변수, 함수 등의 여러 데이터들을 메모리에 저장한다. 따라서, 한정되어있는 메모리 공간을 보다 효율적으로 사용하기 위해 사용 되는 것이 자료구조이다.

자료구조는 크게 선형 자료구조, 비 선형 자료구조 로 나뉜다.

선형구조란, 자료를 구성하는 데이터들을 순차적으로 하나씩 나열시킨 형태의 구조이다. 즉, 1:1 관계의 구조이며 우리에게 익숙한 배열, 리스트, 스택, 큐 등이 이 구조에 해당된다.

비 선형구조는 하나의 데이터 뒤에 여러 개의 데이터가 올수 있는 형태의 구조로, 1:N 의 관계, N:N의 관계를 가진다. 대표적으로 트리와 그래프 구조가 여기에 해당한다.

이번 포스팅에서는 선형 자료구조에 대해서 살펴 보려 한다.

Array

배열은 연속된 메모리 공간에 차례대로 데이터를 저장하는 구조이다.

배열 선언 시 크기를 정하면 그 크기로 고정 되며, 선언된 값은 재 선언 하지 않으면 변경이 불가 하다.

배열의 주소는 배열에 사용된 자료형의 크기 만큼이다. 즉, int 형 을 사용한다면 크기도 int형 의 크기인 4byte인 것이다.

배열의 인덱스를 통해 데이터에 접근이 가능하고 이때 시간 복잡도는 O(1) 이며 삽입 / 삭제 시 데이터의 주소를 한 칸씩 옮겨야 하기 때문에 시간복잡도는 O(n)이다.

O(1) : 상수 시간 복잡도로써, 데이터의 크기와 상관없이 일정한 시간이 걸린다는 것을 의미한다. (한번의 연산으로 결과도출)

O(n) : 선형 시간 복잡도로써, 처리해야할 데이터의 갯수 n에 비례하여 연산시간이 n으로 증가하는 것을 의미한다.

비교적 간단한 구조의 형태를 가지고 있고 연속된 메모리 공간에 저장되기 때문에 관리가 편하고, 인덱스를 통해 원하는 데이터에 빠르게 접근이 가능하다.

하지만, 데이터 삽입/삭제시, O(n) 의 시간복잡도를 가져 느리며, 연속적인 메모리 할당이 필요하기 때문에 메모리 공간이 많이 필요할 수 있다.

List

자료구조 상으로는 먼저 살펴본 배열과 유사하지만, 인덱스로 인해 발생하는 메모리 낭비의 문제를 해결하기 위해 인덱스 대신 각 노드를 연결하여 데이터를 저장한 자료구조이다.

구현 방법에 따라 순차 리스트, 연결 리스트로 나뉜다.

순차 리스트는 데이터들을 순서대로 메모리에 연속해 저장한 리스트이다. 논리적인 구조와 물리적인 구조가 동일하다.

배열과 유사하기 때문에 데이터 삽입 / 삭제시 연속된 물리적 위치를 유지 하기 위해서 데이터를 옮겨주는 작업을 수행해야 하기에 해당 연산이 많다면 시간이 오래걸린다.

연결 리스트는 링크드 리스트로 더 친숙한 키워드로, 각 노드에 저장된 다음 노드의 주소에 의해 연결된 구조를 말한다.

따라서 메모리가 연속될 필요가 없기 때문에 데이터 삽입/삭제시 순차 리스트 처럼 데이터를 옮기는 작업을 수행하지 않고 이전값, 다음값이 가리켰던 주소만 수정하면 되기 때문에 빠른 연산이 가능하다. 데이터 접근시 시간 복잡도는 O(n) 이며, 삽입/삭제시 시간 복잡도는 O(1)이다.

n번째 노드에 접근하기 위해 Head 에서 n번 이동해야 하기 때문에 탐색시 O(n)의 복잡도를 가지고, 삽입/삭제시 주변 노드들에 연결된 주소만 수정하면 되기 때문에 항상 O(1)로 일정하다.

Stack

스택은 컴퓨터에서 자주 사용되는 자료구조로, 데이터를 하나하나 쌓아놓은 구조를 가지고있다.

가장 큰 특징으로는 후입선출 (LIFO)의 구조를 가지고있는데, 가장 최근에 저장된 데이터가 가장 먼저 빠져나가게 된다.

그림처럼 top으로 정해진 방향으로만 저장/삭제의 접근이 가능하다. 삽입 연산을 push, 삭제 연산을 pop이라고 한다.

Queue

스택과 달리 선입선출 (FIFO) 의 구조를 가지고있는 자료 구조이다. 자바스크립트의 태스크 큐의 큐가 바로 이 자료구조를 가지고 있다.

자료구조의 한쪽(back)에선 삽입연산만, 반대쪽(front)에서는 삭제연산만 이루어지는 리스트 (데이터 접근 또한 back과 front에서만 가능하다. )로써, 우리가 기다릴때 줄서는 것을 생각하면 편하다. 입력동작을 Enqueue, 삭제 동작을 Dequeue라고 한다.