자료구조 - 4 | 순차 자료구조

순차 자료구조

순차 자료구조는 선형 자료구조의 일종으로, 저장할 자료들을 메모리에 연속적으로 저장하는 방식인 자료구조이다. 단순히 메모리에 저장할 자료들을 순서대로 저장하기만 하면 되기 때문에 구현이 매우 간단하다는 특징이 있다. C언어에서 배열이라고 불리는 자료구조가 바로 이 순차 자료구조이다.

선형 자료구조
자료들이 서로 1:1의 관계를 가지는 자료구조로, 데이터가 마치 한 줄로 연결된 듯한 형태를 가지고 있다.
순차 자료구조, 연결 자료구조, 스택, 큐, 데크 등이 선형 자료구조에 해당한다.

반면 같은 선형 자료구조이지만 순차 자료구조와는 다른 방식으로 구현할 수 있는 연결 자료구조라는 방식도 있다. 이는 순차 자료구조를 사용함에 있어서 생길 수 있는 문제점들을 개선하기 위해 고안된 자료구조로, 순차 자료구조와 연결 자료구조는 각자의 장점과 단점을 가지고 있다.

 

이번 포스트에서는 순차 자료구조를 이해할 것이기 때문에, 먼저 순차 자료구조의 장점과 단점에 대해 알아보도록 하자.

구현이 간단함

처음에 순차 자료구조를 간단히 설명하면서 언급했듯이, 순차 자료구조는 구현이 매우 간단하다는 특징이 있다. 사용할 메모리 공간을 정해두고, 해당 공간 내에서는 원하는 위치에 데이터를 마음대로 저장할 수 있다.

항목 접근이 빠름

순차 자료구조는 원하는 위치에 즉시 접근할 수 있다.

 

예를 들어 정수를 저장하기 위한 배열을 생성하였다고 가정하자. 해당 배열을 생성할 때 배열의 첫 시작 메모리주소를 기억하기 때문에, 시작 주소와 한 칸의 크기만 알고 있다면 n번째 데이터의 주소도 한 번에 알아낼 수 있을 것이다. C언어를 기준으로 하자면 정수인 int는 4바이트의 크기를 가지므로, 이를 이용하여 정수형 배열에서 원하는 위치의 주소를 계산을 통해 즉시 알아낼 수 있다.

int A[6]인 배열을 생성했을 때의 배열의 모습과 각 메모리의 주소

정수형 배열의 시작 주소가 20230113이라고 가정하면, 3번째 위치의 주소는 20230113 + (2 * 4byte)인 20230121 임을 알 수 있다. 이처럼 순차 자료구조를 사용하면 원하는 위치의 주소를 산술적으로 계산하여 바로 접근하는 것이 가능하다.

삽입, 삭제가 비효율적

순차 자료구조는 위와 같은 장점이 있지만, 그와 동시에 단점도 존재한다. 첫 번째 단점으로는 삽입과 삭제가 비효율적이라는 점이 있다.

 

배열을 하나 생성하여 데이터를 저장했다고 가정하자. 이후 새로운 데이터를 저장하고 싶은데, 어떠한 이유로 인해 기존의 데이터 사이에 새롭게 저장해야 한다고 하자. 이 경우 저장할 위치를 비워주기 위해 해당 위치와 그 뒤에 있는 모든 데이터들을 한 칸씩 뒤로 밀어내야 한다.

 

또는 데이터를 삭제하는 경우를 생각해 보자. 가장 끝의 데이터를 삭제한다면 큰 문제가 없겠지만, 중간의 데이터를 삭제한다면, 삭제한 자리를 채우기 위해 뒤에서 데이터들을 하나씩 당겨와야 한다.

원소 삽입 전

원소 삽입 후

이처럼 데이터를 삽입하거나 삭제할 때마다 자리를 재조정해야 하는 과정이 필요하기 때문에, 순차 자료구조의 크기가 커져 움직여야 하는 데이터가 많아질수록 비효율적이게 된다.

항목의 개수 제한

순차 자료구조의 경우 미리 사용할 항목의 개수를 정해야만 한다. 순서대로 데이터를 쌓기 위해서는 데이터를 쌓을 공간을 미리 확보해 둬야만 하기 때문이다. 만약 미리 공간을 선점해두지 않는다면, 계속 데이터를 쌓다가 언젠가는 다른 데이터를 저장해 둔 메모리영역을 침범할 수도 있다.

 

이러한 이유로 미리 사용할 메모리의 크기를 정해야 하는데, 문제는 보통의 프로그램의 경우 프로그램이 동작하는 도중에 데이터를 새로 저장하거나 삭제하는 경우가 많다는 것이다. 따라서 어느 정도의 메모리를 사용해야 하는지 미리 알기 힘든 경우에는 순차 자료구조가 아닌 다른 방식의 자료구조를 사용하는 것이 좋다.