선형 데이터 구조 - 배열, 리스트, 스택, 큐

선형 데이터 구조

선형 데이터 구조는 구성하는 요소들이 서로 인접해 순차적인 방식으로 정렬되어 있음을 뜻한다

이런 데이터 구조는 이해하기 쉽고 개발할 때 사용하기 쉽다

가장 일반적인 선형 데이터 구조는 배열과 리스트가 있다

배열과 리스트는 범용적인 데이터 구조다

거의 모든 데이터 구조가 배열이나 리스트에서 파생됐거나 어떤 방식으로든 이들을 사용한다

배열

배열은 데이터를 저장하고 구성하는 데 사용하는 가장 기본적인 데이터 구조 중 하나다

배열은 자료형이 같은 요소들을 저장한다

배열에 저장된 각각의 자료를 요소라고 하며, 0부터 번호가 매겨진다

요소에 매겨진 숫자를 배열의 인덱스라고 한다

배열의 구조

배열의 구조는 다음과 같다

배열 특징

배열 내의 요소들은 순차적 또는 연속적으로 정렬되어 있다

이 특징으로 배열 요소들을 임의의 순서로 읽을 수 있다

그러나 데이터를 추가하거나 삭제할 때는 배열 내 다른 데이터의 순서를 다시 매겨야 한다

이를 처리하는데 많은 시간이 걸릴 수 있다

배열 사용

대부분의 프로그래밍 언어에서 컴퓨터가 배열에 메모리를 할당하기전에 프로그래머가 배열 크기를 지정해야 한다

프로그램을 실행하기 전에 배열 크기를 예약할 수 있다

특정 프로그래밍 언어에서는 메모리를 명시적으로 예약할 필요가 없는 기능을 제공해 메모리 공간을 절약할 수 있다

배열 유형

앞에서 설명한 배열의 유형은 1차원 배열이다

배열은 다차원일 수 있다

다차원 배열은 요소가 배열로 이루어진 배열이며, 무언가를 그리드(격자) 형태로 정의할 때 유용하다

2차원 배열은 행과 열의 그리드다

리스트

리스트는 배열의 특별한 유형이다

배열 요소는 메모리에 순차적으로 저장되지만, 리스트의 요소는 흩어진 상태로 메모리에 저장된다

이 때문에 연결 리스트는 메모리를 더 효과적으로 사용할 수 있다

리스트 요소

리스트는 데이터 요소와 포인터(참조)의 쌍으로 구성된다

포인터는 리스트내의 바로 다음 요소가 저장된 메모리 위치를 가리킨다

어떤 데이터 요소에 접근하려면 바로 이전 요소의 포인터를 사용해야 한다

연결 리스트에서 데이터 요소와 포인터의 쌍을 노드라고 한다

연결 리스트의 진입점을 연결 리스트의 헤드라고 한다

리스트 구조

단방향 연결 리스트

노드 하나가 다른 노드를 가리키는 포인터 하나를 갖는 유형의 연결 리스트를 단방향 연결 리스트라고 한다

단방향 연결 리스트에서 마지막 노드는 다른 노드를 가리키지 않으므로 포인터는 null 값이다

양방향 연결 리스트

각 노드가 다음 노드를 가리키는 포인터와 이전 노드를 가리키는 포인터를 함께 갖는 연결 리스트다

양방향 연결 리스트는 데이터를 삭제할 때나 리스트를 양방향으로 순회할 때 더 효율적인 연결 리스트다

순환 연결 리스트

순환 연결 리스트에서 모든 노드는 원형으로 연결된다

마지막 노드는 첫 번째 노드와 연결 된다

따라서 마지막 노드의 포인터는 null 값이 아니다

순환 연결 리스트에서 노드 사이의 연결은 단방향 또는 양방향일 수 있다

순환 연결 리스트는 버퍼링과 관련된 용도로 많이 사용된다

버퍼링: 다양한 처리를 원활하게 실행시키려고 버퍼라는 임시 저장 공간에 데이터를 저장하는 작업

스택

스택은 추가된 요소를 사용 가능한 메모리의 가장 앞 주소에 배치하는 선형 데이터 구조다

스택의 동작은 같더라도 사용되는 기술이나 프로그래머가 원하는 스택 종류에 따라서 다양한 방식으로 구현된다

스택 동작

• 푸시(push): 스택에 요소를 추가한다
• 팝(pop): 스택에서 마지막으로 추가된 요소를 삭제한다

스택에 마지막으로 추가된 요소를 먼저 삭제하는 스택 구조를 후입선출(LIFO)라고 한다

스택 구조

스택의 구조는 다음과 같다

스택의 개념은 쉽게 시각화할 수 있다

하지만 데이터 구조로서 스택의 큰 문제점 중 하나는 그 단순함에 있다

최상단에서만 데이터 요소를 추가, 삭제할 수 있는데 이는 스택에서 특정 요소를 검색하는 속도를 제한한다

역추적이나 문자열을 반전시키는 응용프로그램에서는 스택이 필요하다

스택 종류

데이터 구조 크기나 규모가 고정된 정적 스택과 실행 중에 크기를 늘릴 수 있는 동적 스택으로 나눌 수 있다

동적 스택은 크기뿐 아니라 소비하는 메모리의 양도 변한다

정적 스택은 배열을 사용하여 설계할 수 있다

동적 스택은 최상단 요소를 가리키는 포인터가 있는 단방향 연결 리스트를 사용해 설계할 수 있다

스택은 함수 호출, 스케줄링, 인터럽트 매커니즘 등 다양한 기본 컴퓨팅 프로세스에서 사용되고 있다

큐

큐는 각 요소에 우선순위를 부여하는 데이터 구조의 한 종류다

큐에 첫 번째 요소를 추가하면 큐 뒤쪽에 배치된다

큐 동작

• 인큐(enqueue): 큐에 요소를 추가하는 것
• 데큐(dequeue): 큐에서 요소를 삭제하는 것

큐에서 요소를 삭제할 때는 큐에 가장 오랫동안 있던 요소가 먼저 삭제된다

큐에 가장 먼저 추가된 요소가 우선적으로 삭제된다는 점에서 큐를 선입선출(FIFO) 데이터 구조라고 한다

큐의 구조

기본적인 큐는 선형 데이터 구조지만, 비선형 데이터 구조의 큐도 존재한다

새로운 요소는 큐 맨 뒤에 추가되고, 요소 삭제를 하면 큐 맨 앞쪽부터 삭제된다

우선순위 큐

우선순위 큐는 기본적인 큐를 확정한 것으로 키와 값의 체계를 사용해 큐의 요소들을 정렬한다

키는 값을 식별하고 검색하는 데 사용하고 값을 실제 사용하는 데이터다

우선순위 큐 구현

우선순위 큐를 구현할 때 연결 리스트나 배열과 같은 데이터 구조를 사용한다

큐를 구현할 때 사용하는 기본 데이터 구조는 큐의 속성에 영향을 준다

우선순위

우선순위 큐에서 모든 요소는 우선순위가 있으며 이는 키에 해당한다

우선순위가 높은 요소는 큐에서 먼저 삭제된다

만약 우선순위가 같다면 큐에 먼저 추가된 요소부터 삭제된다

우선순위 큐 구조

숫자가 낮을수록 우선순위가 높은 예다

우선수위 큐는 데이터 압축, 네트워킹, 수많은 컴퓨터 과학 분야의 응용프로그램에서 사용된다