자료구조 기초 - 선형 데이터 구조
데이터 구조가 선형이라는 것은 데이터 구조를 구성하는 요소들이 서로 인접해 순차적인 방식으로 정렬되어 있음을 뜻한다.
배열과 리스트는 가장 일반적인 선형 데이터 구조다. 거의 모든 데이터 구조가 배열이나 리스트에서 파생되었거나 어떤 방식으로든 배열과 리스트를 사용하기 때문에 범용적이다.
배열
배열 내의 요소들은 순차적 또는 연속적으로 메모리에 정렬되어 있어 배열 요소들을 임의의 순서로 읽을 수 있다.
그러나 요소들의 순차적 구성 때문에 배열에서 데이터를 추가하거나 삭제할 때는 배열 내 다른 데이터의 순서를 다시
매겨야 하므로 처리하는데 많은 시간이 걸린다.
배열에 저장된 각각의 자료를 요소, 요소에 매겨진 숫자를 인덱스라고 한다.
요소들은 보통 쉼표로 구분한다.
1차원 배열 - 배열의 요소에 접근할 때 각 인덱스가 가리키는 요소가 단일 행 또는 단일 열을 나타낸다.
다차원 배열 - 요소가 배열로 이루어진 배열. 무언가를 그리드(격자) 형태로 정의할 때 유용하다.
여기에 데이터를 저장한 것을 행렬이라고 한다.
리스트
리스트의 요소는 데이터 요소와 포인터(=참조)의 쌍으로 구성된다. 포인터는 리스트 내의 바로 다음 요소가 저장된 메모리
위치를 가리킨다. 따라서 어떤 데이터 요소에 접근하려면 바로 이전 요소의 포인터를 사용해야한다.
리스트는 배열과 달리 요소가 흩어진 상태로 메모리에 저장된다. 이 떄문에 연결 리스트(Linked List)는 메모리를 더
효과적으로 사용할 수 있다.
노드 - 연결 리스트에서 데이터 요소와 다음 요소를 가리키는 포인터의 쌍.
헤드 - 연결 리스트는 해당 리스트에 진입하는 지점이 있도록 구성되며, 이러한 진입점.
단방향 연결 리스트(Singly Linked List)
노드 하나가 다른 노드를 가리키는 포인터 하나를 갖는 유형의 연결 리스트.
마지막 노드는 다른 노드를 가리키지 않으므로 포인터는 널 값을 갖는다.
양방향 연결 리스트(Doubly Linked List)
각 노드가 다음 노드를 가리키는 포인터와 이전 노드를 가리키는 포인터를 함께 갖는 연결 리스트.
데이터를 삭제할 때나 리스트를 양방향으로 순회할 때 더 효율적이다.
순환 연결 리스트(Circular Linked List)
모든 노드는 원형으로 연결된다. 마지막 노드는 널 값이 아닌 첫 번째 노드와 연결되어 있다.
순환 연결 리스트에서 노드 사이의 연결은 단방향 또는 양방향일 수 있다.
버퍼링(원활한 처리를 위해 버퍼라는 임시 저장 공간에 데이터를 저장하는 작업)과 관련된 용도로 많이 사용된다.
스택
추가된 요소를 사용 가능한 메모리의 가장 앞 주소에 배치하는 구조이다.
스택에 요소를 추가하는 동작은 푸시(Push), 요소를 삭제하는 동작은 팝(Pop)이라고 한다.
스택은 마지막으로 추가된 요소를 먼저 삭제되는 후입선출(Last In First Out, LIFO) 구조이다.
스택은 최상단에서만 데이터를 수정할 수 있어 그 단순함으로 인해 특정 요소를 검색하는 속도가 제한되나, 역추적이나
문자열을 반전시키는 등의 기능에서는 필요하다.
정적 스택
데이터 구조의 크기나 규모가 고정되어 있다.
배열을 사용하여 설계할 수 있다.
동적 스택
실행 중에 크기를 늘릴 수 있다. 소비하는 메모리의 양도 변한다.
최상단 요소를 가리키는 포인터가 있는 단방향 연결 리스트를 사용하여 설계할 수 있다.
동작은 같더라도 사용되는 기술이나 프로그래머가 원하는 스택 종류에 따라 다양한 방식으로 구현될 수 있다.
함수 호출, 스케줄링, 인터럽트 메커니즘 등의 다양한 기본 컴퓨팅 프로세스에서 사용되고 있다.
큐
각 요소에 우선순위를 부여하는 데이터 구조의 한 종류. 요소를 추가하면 큐 뒤쪽에 배치된다.
큐에 요소를 추가하는 것을 인큐(Enqueue), 요소를 삭제하는 동작은 디큐(Dequeue)라고 한다.
큐는 가장 오랫동안 있던 요소가 먼저 삭제되는 선입선출(Frist In Frist Out, FIFO)구조이다.
우선순위 큐
기본적인 큐를 확장한 것으로, 키(값을 식별하고 검색)와 값(실제 사용하는 데이터)의 체계를 사용해 요소를 정렬한다.
연결리스트나 배열과 같은 데이터 구조를 사용하여 구현한다. 큐를 구현할 때 사용되는 기본 데이터 구조는 큐의 속성에
영향을 준다.
우선순위 큐에서 모든 요소는 우선순위가 있으며 이는 키에 해당한다. 우선순위가 높은 요소는 우선순위가 낮은 요소보다
먼저 삭제된다. 따라서 우선순위 큐는 일반적으로 요소 추가하기, 요소 삭제하기, 우선순위 가장 높은 요소 가져오기,
큐가 가득 찼는지 확인하기 등의 메소드를 제공한다.
일부 알고리즘뿐만 아니라 데이터 압축, 네트워킹, 수많은 컴퓨터 과학 분야의 응용 프로그램에서도 사용된다.