선형 자료구조 - 배열/연결 리스트/큐/스택

By 공부하는동동

study/algorithm

2022. 4. 2. 21:55

알고리즘 공부 시작

알고리즘을 너무 오래 놓고 있는 것 같아서.. 나중에 이직을 위해서라도 공부를 해야겠다는 생각이 들었다.

제로 베이스로 기본부터 새로 시작해보려 한다. 선형 자료구조부터 시작!

선형 자료구조란?

- 연속적으로 자료 뒤에 자료가 배치되는 구조

- 배열, 리스트, 스택, 큐가 대표적이다.

배열

- 번호(인덱스)와 해당 인덱스에 대응하는 데이터로 이루어진 자료구조다.

- 메모리 상에 같은 종류의 데이터들이 순차적으로 저장되고, 인덱스로 해당 자료의 상대적인 위치를 알아낼 수 있다.

배열의 종류

배열에는 엄밀하게 성질에 따라 정적 배열과 동적 배열로 구분할 수 있다.

크게 자세하게 다루지는 않는다.

배열의 특징

- 말 그대로 크기가 정해져 있는 배열을 의미한다.

- 연속된 메모리 경로에 정해진 배열 사이즈만큼을 생성한다.

배열의 장단점

< 장점 >

- 인덱스로 데이터를 참조할 수 있으므로(Random Access), 탐색에 시간이 빠르다.

- 가장 기본이 되는 자료구조

- 순차적으로 데이터를 삽입하고 데이터에 변환이 많이 없는 경우 활용도가 높다.

< 단점 >

- 이미 정해진 사이즈를 가지기 때문에, 추가로 길이를 늘리거나, 지워주는 작업이 복잡하다.

- 배열의 데이터가 들어가있는 경우, 사이사이에 데이터를 새로 추가하거나, 삭제해주는 작업도 번거롭다.

배열의 연산에 대한 시간 복잡도

- 신규 원소를 맨 뒤에 추가 : O(1)

- 맨 뒤의 원소를 삭제 : O(1)

- 특정 원소의 값 변경( 갱신 ) : O(1)

- 특정 원소 검색 : O(1)

- 맨 뒤가 아닌 임의의 위치에 데이터를 추가 : O(N)

-- 중간에 데이터 추가시, 기존에 위치하고 있던 데이터를 밀어버려야 합니다.

- 맨 뒤가 아닌 임의의 위치에 있는 데이터를 삭제 : O(N)

-- 마찬가지로 중간 데이터에 구멍이 나므로, 한 칸씩 당겨야 합니다.

주의점?

배열 관련 문제를 풀 때 실수할 수 있는 부분에는 무엇이 있을까?

- 배열은 인덱스로 접근을 하니, 인덱스에 대한 부분

-- 사이즈보다 큰 인덱스로 데이터에 접근하려 시도할 때를 주의해야 한다.

-- 특히 배열 상에서 임의 데이터 삽입/삭제 시 데이터 이동할 때 인덱스가 범위를 넘지 않도록 주의한다.

연결 리스트

연결 리스트란, 노드로 구성되고 각 노드가 데이터와 메모리의 위치를 담는 포인터를 가지는 자료구조이다.

연결 리스트의 특징

- 배열과 달리, 연속적인 메모리 공간에 위치하지 않는다.

- 하나의 원소가 데이터 공간과 포인터 공간으로 이루어지고, 각 포인터로 연속되지 않은 원소들을 잇는다.

- 배열과 달리 포인터 공간이 추가적으로 연결 리스트의 사이즈만큼 더 필요하다.

연결 리스트의 종류

연결 리스트의 포인터가 어떻게 구성이 되어있는가로 구분을 할 수가 있다.

- 단일 연결 리스트

: 각 노드에 자료 공간과 한 개의 포인터 공간을 가지고, 각 포인터는 다음 노드를 가리킨다.

- 이중 연결 리스트

: 각 노드에 자료 공간과 두 개의 포인터 공간을 가지고, 각 포인터는 앞뒤의 노드를 가리킨다.

- 원형 연결 리스트

: 단일 연결 리스트의 마지막 노드의 포인터가 가장 앞쪽의 노드를 가리키며 원형의 형태를 가지는 리스트를 의미한다.

연결 리스트의 연산에 대한 시간 복잡도

- N번째에 있는 특정 원소 접근 : O(N)

- 삭제해야 하는 원소의 위치를 알고있는 경우( 메모리만 새로 이어준다. )

-- 맨 뒤가 아닌 임의의 위치에 데이터를 추가/삭제 : O(1)

- 삭제해야하는 원소의 위치를 모르는 경우

-- O(N)이 추가됨 : N번째 원소의 위치까지 이동후 삭제 작업 진행해야 함

주의점

연결 리스트에 관한 문제를 풀 때 주의해야 할 점은 무엇이 있을까?

- 연결 리스트는 배열과 다르게 메모리 인덱스로 접근하지 않는다.

- 하지만 위치를 지정하는 포인터라는 공간이 별도로 존재한다.

-- 특히 삭제 작업이나 추가 시, 새롭게 기존 노드의 포인터를 변경해주어야 하기 때문에, 가장 주의해야 하는 부분이지 않을까

큐

먼저 집어넣은 데이터가 먼저 나오게 되는 FIFO(First In First Out)의 구조로 저장하는 자료구조다.

일상적으로 음식점에서 줄 서있는 경우를 생각하면 된다.

큐의 특징

큐의 연산에 대한 시간 복잡도

큐의 연산은 기본적으로 맨 앞에 위치하고 있는 데이터와 맨 끝에 위치하고 있는 데이터를 기준으로 한다.

배열로도, 연결 리스트로도 큐를 구현할 수 있다. 연결 리스트로 구현한 큐가 배열보다는 메모리 추가에 대해 좀 더 자유롭다는 장점이 있다. 하지만 역시 메모리 추가 공간과, 메모리를 타고 이동해야 한다는 추가적인 이동 작업이 있다는 단점이 존재한다.

- 원소의 추가 : O(1)

- 원소의 제거 : O(1)

큐의 종류

- 선형 큐 : 일반적인 큐의 형태. 크기가 제한되어있어 빈 공간을 사용하려면 자료를 전부 꺼내거나, 옮겨야 하는 단점이 존재.

- 환형 큐 : 선형 큐의 단점을 보완하기 위해 고안. 큐에 추가적으로 저장할 공간이 없을 경우, 가장 앞의 빈 공간으로 위치를 이동해 데이터를 저장할 수 있도록 한 자료구조

스택

큐와 반대로 먼저 집어넣은 데이터가 가장 먼저 나오게 되는 LIFO(Last in First Out)의 구조로 저장되는 자료구조이다.

일상적으로 프링글스(?)의 경우를 생각해보면 된다. 가장 위에 있는 과자를 가장 먼저 꺼내가므로

스택의 특징

스택의 연산에 대한 시간 복잡도

스택의 연산도 큐와 마찬가지이다. 스택의 경우에는 사실 데이터의 추가와 삭제가 가장 위에 있는 뚜껑 부위에서 진행된다.

역시 배열로도, 연결 리스트로도 큐를 구현 가능하다.