💡코드 없는 알고리즘과 데이터 구조을 바탕으로 작성된 글입니다.

선형 데이터 구조

💡선형 데이터 구조 : 데이터 구조를 구성하는 요소들이 서로 인접해 순차적인 방식으로 정렬되어 있는 구조

배열과 리스트

선형 데이터 구조의 대표적인 구조 2가지는 배열과 리스트이다. 이 두가지 구조는 범용적인 데이터 구조라 할 수 있는데 거의 모든 데이터 구조가 배열과 리트스에서 파생되었거나 어떤 방식으로든 이 구조를 사용하기 때문이다.

배열

: 데이터를 저장하고 구성하는데 사용하는 가장 기본적인 데이터 구조.

• 💡 단순하지만 강력한 데이터 구조.
• 💡 모든 것을 살펴보기 위한 최적의 출발점.

배열은 같은 자료형의 요소들만 저장하며 0부터 번호가 매겨진다. 이때 매겨진 번호들을 배열의 인덱스(Index)라고 하며, 이 인덱스에 따라 순차적 또는 연속적으로 정렬된다.

• 🚨이런 순차적인 정렬로 인해 데이터를 추가하거나, 삭제할 때는 문제가 발생한다.

🚨 배열의 한계점
데이터를 추가하거나 삭제할 경우 요소들의 순서(Index)를 다시 매겨야 하므로 처리하는데 많은 시간이 소요된다.

• 💡배열은 초기화 단계에서 크기를 지정해야 한다.

다차원 배열

위 처럼 하나의 Index값을 가진 것을 1차원 배열이라고 한다. 다차원 배열을 요소가 배열로 이루어진 배열을 말한다.

• 💡행렬: 2차원 배열을 말하며, 행과 열의 그리드라고 생각하면 된다.

리스트

배열의 특별한 유형!

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

• 흩어져 있는 요소들은 서로 연결되어 있는 상태로 존재하기 때문에 연결 리스트(LinkedList)라고도 한다.

• 💡리스트의 요소는 데이터와 포인터가 한 쌍인 구조로 되어있으며 이 쌍을 노드(node)라고 한다.

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

• 해당 리스트에 진입하는 지점을 연결리스트의 헤드(Head)라고 한다.

단방향 리스트

: 노드에 하나의 포인터만 갖는 연결 리스트

• 💡마지막 요소의 포인터는 Null 값을 갖는다.

양방향 리스트

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

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

순환 연결 리스트

: 모든 노드가 원형으로 연결되어 있는 연결 리스트

노드의 연결에 따라 단방향, 양방향으로 나뉜다. 하단의 그림은 단방향 순환 연결 리스트이다.

• 💡버퍼링과 관련된 용도로 많이 사용한다.

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

스택과 큐

스택

Stack

• 💡역추적이나 문자열을 반전시키는 응용 프로그램에서 사용된다.

큐

Queue

우선순위 큐

기존의 Queue를 확장한 것.

• 💡Key-Value의 체계를 사용해 큐의 요소들을 정렬한다.

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

• 우선순위 큐에서 모든 요소는 우선순위(Key)가 있다.

• 우선순위가 더 높은 쪽이 먼저 삭제되며, 우선순위가 같을 경우 먼저 추가된 요소부터 삭제된다.

• 💡데이터 압축, 네트워킹 등 많은 분야에서 사용된다.