Part 1. 데이터 구조 - 선형 데이터 구조(배열, 리스트, 스택, 큐)

2. 선형 데이터 구조

  컴퓨터에서 메모리란 컴퓨터가 처리 중이거나 처리를 끝낸 데이터를 저장하는 공간, 즉 컴퓨터의 저장공간을 뜻하며 데이터 구조는 이러한 저장공간을 효과적으로 관리하기 위한 방법이다. 컴퓨터 메모리는 각각 정해진 역할을 하는 유형으로 계층적으로 구성되어 있다. 메모리 계층구조는 메모리 용량과 속도를 기준으로 아래와 같은 그림으로 표현할 수 있다.

 

메모리의 계층구조

컴퓨터 메모리

  하드 디스크(Hard Disk)는 디스크 저장장치(Disk Storage)라고도 부르며, SSD(Solid State Drive) 또는 HDD(Hard Disk Drive)와 같은 저장장치로 구분된다. 하드 디스크는 메인 메모리인 RAM(Random Access Memory)에 적재되는 데이터를 저장한다. RAM은 컴퓨터의 메인 메모리로, RAM에 적재된 데이터는 CPU 칩에 내장된 캐시(Cache)라는 메모리 유형에 적재된 후, 결국 CPU가 처리 중인 데이터를 저장하는 레지스터(Register)에 적재된다. 캐시 메모리의 경우 CPU가 가장 많이 사용하는 데이터를 저장하여 일부 연산의 속도를 매우 빠르게 만든다. 일반적으로 L1 캐시와 L2 캐시가 있으며 L1 캐시는 CPU 레지스터만큼 빠르고, L2 캐시는 L1 캐시보다는 느리지만 RAM 보다 빠르다.

  캐시는 많은 장점을 갖고 있지만 용량이 너무 크면 비효율적이 된다. 캐시의 연산처리가 빠른 이유 중 하나가 용량이 RAM보다 훨씬 작아 데이터를 쉽게 찾을 수 있기 때문인데, 용량이 커질수록 연산 처리 속도 면에서의 장점이 줄어들기 때문이다. 메모리 계층 구조의 최상단 요소는 레지스터이다. 레지스터는 연산 처리 속도가 굉장히 빠르며 CPU에 장착할 수 있을 만큼 크기가 매우 작다. 저급(low-level) 프로그래밍 언어를 사용하면 레지스터 유형의 메모리에 직접 접근하여 명령어를 수행할 수 있다.

  메모리는 메모리 주소(Memory Address)를 이용하여 사용된다. 이는 RAM이나 하드디스크 같은 실제 자료나 프로그램이 저장되는 공간인 물리적 주소를 가리키며, 이를 통해 운영체제는 물리적인 주소에 가상의 주소를 매핑하여 실제 메모리보다 더 많은 메모리가 있다고 프로그램이 착각하게 만들 수 있다. 이처럼 실제로 존재하지 않지만 물리적인 주소에 매핑되어 메모리 역할을 하는 영역을 가상 메모리(Virtual Memory)라고 지칭한다. 이처럼 가상 메모리를 사용하면 물리적 메모리가 고갈되는 상황을 막을 수 있다.

  가상 메모리는 물리적인 메모리에 가상 주소를 통해 매핑된다. 가상 주소는 메모리상의 위치를 식별하도록 하며, 가상 메모리를 일정한 크기로 나눠서 사용하는 페이징(Paging) 개념과 함께 페이지 테이블(Page Table)을 만들어 물리적 메모리를 더욱 효율적으로 사용할 수 있게 한다. 이러한 개념은 특정 데이터가 물리적인 메모리 공간에 여러 개로 나뉘어 저장되더라도 서로를 참조하도록 하여 데이터를 손실 없이 안전하게 불러올 수 있도록 돕는다. 또한, 하나의 데이터가 연속된 메모리 공간에 저장되지 않아도 정상적으로 저장되기 때문에 물리적 메모리 공간을 더욱 효율적으로 사용하게 된다.

 

선형 데이터 구조의 개요

  데이터 구조가 선형이라는 것은 데이터 구조를 구성하는 요소들이 서로 순차적인 방식으로 정렬되어 있음을 뜻한다. 배열과 리스트는 가장 대표적인 선형 데이터 구조로, 거의 모든 데이터 구조가 배열이나 리스트에서 파생되거나 어떤 방식으로든 배열과 리스트를 사용한다고 해도 과언이 아닐 정도로 범용적인 데이터 구조이다.

 

배열

  배열은 데이터를 저장하고 구성하는 데 사용되는 가장 기본적인 데이터 구조이다. 배열에 저장되는 각각의 자료는 요소(Element)라고 불리며 각 요소는 동일한 자료형으로 구성된다. 배열의 요소에는 인덱스(Index)라는 번호가 각각 매겨지는데, 이 인덱스는 0번부터 시작되어 순차적으로 부여되고, 요소들의 값을 표현할 때에는 쉼표로 구분하여 작성한다.

 

배열의 구조

  배열내의 요소들은 순차적 또는 연속적으로 정렬되어 있고 요소에는 각각의 인덱스가 부여되어 있기 때문에 임의의 순서로 값을 읽어낼 수 있다. 하지만 요소들이 순차적으로 배정되어 있기 때문에 배열에 데이터를 추가하거나 삭제하게 될 때 해당 데이터를 기준으로 뒤에 존재하는 요소들의 정보를 재배치해야 하기 때문에 데이터가 커질수록 시간이 오래 소요될 수 있다는 단점이 존재한다. 배열은 데이터가 어떤 식으로 구성되어 있느냐에 따라 각각 명칭이 다른데, 위의 그림과 같이 일렬로 구성되는 배열은 1차원(one-dimensional) 배열이라고 부른다. 행과 열로 구분된 다차원(multi-dimensional) 배열도 존재하며, 2차원 배열의 경우 가장 일반적인 다차원 배열이자 2차원 구조이며, 여기에 데이터를 저장한 것을 행렬(matrix)라고 부른다.

 

리스트

  리스트는 배열의 특별한 유형이라고 볼 수 있다. 배열 요소는 메모리에 순차적으로 저장되지만, 리스트의 요소는 흩어진 상태로 메모리에 저장된다는 차이점이 있다. 이러한 특징 때문에 리스트는 연결 리스트(Linked List)라고도 부른다. 리스트의 요소는 데이터 요소와 포인터(참조)의 쌍으로 구성된다. 포인터는 리스트 내의 바로 다음 요소가 저장된 메모리의 위치를 가리키기 때문에 어떠한 데이터 요소에 접근하고자 하면 바로 이전 요소의 포인터를 사용하여야 한다. 연결 리스트에서 데이터 요소와 다음 요소를 가리키는 포인터의 쌍은 노드(Node)라 하며, 해당 연결 리스트에 진입하는 첫 지점은 헤드(Head)라고 부른다. 노드 하나에 다른 노드를 가리키는 포인터 하나를 갖는 유형의 연결 리스트는 단방향 연결 리스트(Singly Linked List)라 한다. 단방향 연결 리스트에서 마지막 노드는 다른 주소를 가지지 않으므로 null값을 가지게 된다.

 

단방향 연결 리스트의 구조

  각 노드가 다음 노드를 가리키는 포인터와 이전 노드를 가리키는 포인터를 함께 갖는 연결 리스트 구조는 양방향 연결 리스트(Doubly Linked List)라고 부르며, 해당 리스트는 데이터를 삭제할 때나 리스트를 양방향으로 순회 할 때 더 효율적인 연결 리스트이다.

 

양방향 연결 리스트의 구조

  마지막으로, 순환 연결 리스트(Circular Linked List)는 모든 노드가 원형으로 연결되어 마지막 노드가 첫 번째 노드와 연결된다. 그러므로 해당 리스트는 마지막 노드의 포인터가 널(Null) 값이 아니게 된다는 점을 기억하여야 한다. 순환 연결 리스트에서 노드 사이의 연결은 단방향 또는 양방향일 수 있다. 이러한 리스트는 컴퓨팅 분야에서 특히 버퍼링(처리를 원활히 하기 위해 임시 저장공간-버퍼-에 데이터를 저장하는 것) 처리에서 많이 사용된다.

 

단방향 순환 연결 리스트의 구조

 

스택

  스택은 추가된 요소를 가장 먼저 배치하는 데이터 구조의 한 종류이다. 쉽게 말해 처음 들어간 데이터가 가장 늦게 출력되고, 가장 늦게 들어간 데이터가 가장 빠르게 나오는 구조(후입 선출/Last In First Out, LIFO)이다. 스택에 요소를 추가하는 동작은 푸시(Push), 요소를 삭제(출력)하는 동작은 팝(Pop)이다.

 

스택의 구조

  스택은 최상단에서만 데이터 요소를 삭제하거나 추가할 수 있다. 이러한 구조는 스택에서 특정 요소를 검색하는 속도를 제한시키기 때문에 스택을 사용하기 전에는 시스템의 특성을 정확히 파악하여야 한다. 스택은 역추적이나 문자열을 반전시키는 응용프로그램에서 사용하기에 적합한 데이터 구조이다.

  스택은 생성 방식에 따라 데이터 구조의 크기나 규모가 고정된 정적(Static) 스택과 실행 중에 크기를 늘릴 수 있는 동적(Dynamic) 스택으로 나뉘며, 이때 늘어나는 것은 스택의 크기뿐만 아니라 소비되는 메모리의 양도 포함한다. 정적 스택은 배열을 사용하여 설계가 가능하다. 또한 최상단 요소를 가리키는 포인터를 생성하면 단방향 연결 리스트로도 구현이 가능하다.

 

큐

  큐는 각 요소에 우선순위를 부여하는 데이터 구조로, 첫 번째 요소를 추가한 뒤 두 번째 요소를 추가할 때 데이터의 가장 마지막에 배치되는 구조를 가진다. 큐에 요소를 추가하는 것은 인큐(Enqueue), 삭제하는 것은 데큐(Dequeue)라 지칭한다. 큐에서 데이터를 삭제할 때는 큐에 가장 오랫동안 있던 요소(가장 처음에 추가된 요소)가 먼저 삭제되어, 이러한 점을 따 선입선출(First In First Out, FIFO) 구조라고 부른다.

 

큐의 구조

 

우선순위 큐

  우선순위 큐는 앞에서 설명한 기본적인 큐를 확장한 모습으로, 키(Key)-값(Value) 구조를 이용하여 큐의 요소들을 정렬한다. 우선순위 큐를 구현할 때에는 연결 리스트나 배열과 같은 데이터 구조를 사용하며, 우선순위가 높은 키 값(높은 우선순위)을 가진 요소가 먼저 삭제되도록 구성된다. 만약 요소들의 우선순위가 동일하다면 선입선출 특징에 따라 먼저 추가된 요소부터 삭제된다. 이에 따라 우선순위 큐는 일반적으로 요소 추가, 요소 삭제, 우선순위가 가장 높은 요소 출력 등의 기능이 제공된다.