[선형 구조 기초] 배열, 동적 배열, 연결 리스트 복습/정리

 

[선형 구조 기초] 배열, 동적 배열, 연결 리스트

 

기초적인 선형 자료 구조를 복습해보자.

선형 구조는 알다시피 데이터를 순차적으로 나열한 상태를 말한다.

반대로 비선형 구조는 하나의 데이터 뒤에 다수의 자료가 올 수 있는 형태를 말한다.

 

선형 구조의 대표적인 기법

- 배열

- 연결 리스트

- 스택 / 큐

 

비선형 구조의 대표적인 기법

- 트리

- 그래프

 

---

 

배열

 

배열은 고정된 메모리 공간을 연속적으로 할당받아서 사용하는 선형 자료 구조이다.

고정된 공간이기 때문에 새로운 공간을 추가하거나 축소하는 등의 행동을 할 수가 없다.

그리고 무조건 연속된 공간에 할당되어야 한다는 특징이 있다.

 

---

 

동적 배열

 

배열을 개선한 것이 동적 배열이다.

일반 배열과 다르게 고정된 메모리 공간을 사용하지 않는다. 유동적으로 메모리 공간을 할당받아 사용할 수 있다.

일반 배열과 마찬가지로 할당받는 공간이 연속적이어야 한다. 연속적으로 할당받은 메모리 공간에 새로운 데이터를 

넣으려고 하는데 해당 공간이 부족하다면 다른 메모리 공간으로 이동해서 새롭게 할당을 받는 형식이다.

 

이러한 동적 배열은 메모리 공간이 부족하다면 계속 다른 공간으로 이동해야 하기 때문에 어찌 보면 비효율적이다.

하지만 다음과 같은 방법으로 해당 문제를 어느 정도 보완하고 있다. 바로 동적 배열 할당 정책이다.

특별한 게 있는 것은 아니고 실제로 사용할 공간보다 여유롭게(약 1.5~2배) 공간을 할당받는 방식이다.

매번 비효율적으로 메모리 공간을 이동하는 것이 비효율적이기 때문에 이러한 것을 최소화하기 위한 방법이다.

 

그럼 동적 배열은 단점이 없을까?

단점은 중간 삽입/삭제가 매우 비효율적이라는 것이다.

이 단점은 따로 대책이 없기 때문에 동적 배열을 사용하고 있다면 웬만하면 중간 삽입/삭제는 하지 않는 것을 권장한다.

 

---

 

연결 리스트

 

연결 리스트의 경우 연속되지 않은 메모리 할당 공간을 사용하는 특징이 있다.

각 공간들이 서로의 위치 정보를 가지고 있어서 이 위치 정보를 통해 다음 저장 공간으로 이동해서 데이터를

사용하는 방식이다. 그렇기 때문에 특정 공간의 데이터를 사용하고 싶을 때, 즉 중간 삽입/삭제에 이점이 있다.

데이터들이 연속된 공간에 할당되어 있는 것이 아니기 때문에 각 저장 공간에 있는 위치 정보만 수정하게 되면

중간에 삽입이나 삭제가 매우 간편하다. 

 

하지만 단점으로는 n번째 저장 공간을 빠르게 찾을 수 없다는 점이다. 다시 말해 임의 접근이 매우 비효율적이다.

 

그렇다면 여기서 모순점이 생긴다.

임의 접근이 좋지 않은데 중간 삽입/삭제는 왜 장점일까?

중간에 데이터를 삽입/삭제하기 위해서는 특정 지점의 위치를 알아야 할 텐데 그렇다면 임의 접근을 해야 한다는

소리 아닌가? 라고 생각할 수 있다. 맞는 말이긴 하지만 다음과 같은 방법으로 중간 삽입/삭제를 하게 된다.

 

특별한 방법은 아니고 특정 지점의 위치 정보를 따로 관리하는 것이다.

연결 리스트가 임의 접근이 비효율적이기 때문에 어느 공간으로 이동해야 할지 위치 정보를 따로 관리하게 되면

매우 효율적으로 특정 지점으로 이동할 수 있게 된다. 

이러한 관점에서 중간 삽입/삭제가 장점이라는 소리다.