[자료구조] 순차 리스트(Sequential List)

리스트 (List)

자료구조에서 리스트(List)는 가장 자주 사용되는 자료구조 중 하나이고, 선형으로 원소를 나열하는 구조이다.
리스트는 구현 방법에 따라 순차 리스트(Sequential List)와 연결 리스트(Linked List)로 나눌 수 있다.

오늘은 순차 리스트(Sequential List)에 대해 알아보는 시간을 갖도록 하자.

순차 리스트 (Sequential List)

순차 리스트는 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 자료구조이다.
즉, 자료의 논리적인 구조와 물리적인 구조가 일치하는 구현 방식을 갖는다.

데이터가 컴퓨터 메모리에 저장될 때 저장 시작 위치부터 빈자리 없이 순서대로 저장된다. 따라서, 데이터의 시작 위치와 원소의 크기를 안다면 특정 원소의 위치를 알 수 있다.

삽입

순서대로 연속적으로 메모리에 자료가 저장되어있기 때문에 새로운 원소를 삽입하고자 할 때에는
먼저 삽입 할 자리를 만든 후에 그 자리에 원소를 삽입해야한다.

삭제

메모리에 연속적으로 저장되어있어야 하기 때문에 중간에 빈자리가 있으면 안된다.
따라서, 원소를 삭제 후, 삭제한 원소 뒤에 있는 원소들을 모두 앞으로 옮겨야한다.

순차 리스트는 자료가 물리적으로 연속적으로 존재해야하기 때문에,
데이터를 삽입하거나 삭제할 때, 원소들을 옮기는 추가 작업이 필요하다.
따라서, 삽입과 삭제 연산이 많다면 그만큼 연산 시간이 길어진다.

탐색

순차 리스트는 배열로 구현하기 때문에 인덱스를 통해 원소를 탐색할 수 있다.

구현

순차 리스트는 배열을 통해 구현할 수 있다.
배열은 <인덱스, 원소 값> 쌍으로 구성되어 메모리에 연속적으로 할당되며, 인덱스는 배열 원소의 순서를 나타낸다.

1차원 배열

1차원 배열은 선형의 형태로 모든 원소가 존재하기 때문에 모든 원소를 한 개의 인덱스를 통해 접근할 수 있다.
arr[idx]와 같은 형식으로 접근한다.
첫번째 원소의 인덱스는 0, 2번째 원소의 인덱스는 1, N번째 원소의 인덱스는 N-1이다.
N번째 원소의 주소는 start_addr + (N - 1) * elem_size 이다.

다음 코드는 1차원 배열의 요소와 메모리 주소를 출력하는 코드이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>

using namespace std;

int main() {
    int arr[4] = {10, 20, 30, 40};

    for (int i = 0; i < 4; i++) {
         cout << "arr[" << i << "] = " << arr[i] << ", address : " << &arr[i] << endl;
    }

    return 0;
}

2차원 배열

2차원은 면으로 이루어진 공간이므로, 원소를 두 개의 인덱스를 통해 접근할 수 있다.
하지만, C언어에서는 2차원 배열을 1차원의 배열처럼 선형으로 원소를 저장한다.

다시 말해, 첫번째 행의 마지막 원소가 저장된 메모리 공간 다음에 두번째 행의 첫번째 원소가 저장되어 있다.
따라서, 2차원 배열은 1차원 배열의 배열이다.

2차원 배열을 코드로 나타내면 arr2[row][col]의 형태로 나타낼 수 있으며, 첫번째 인덱스는 행(row)이고, 두번째 인덱스는 열(col)이다.

다음 코드는 2차원 배열의 요소와 메모리 주소를 출력하는 코드이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>

using namespace std;

int main() {
    int arr2[2][3] = { {50, 30, 10}, {12, 27, 51} };

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 3; j++) {
            cout << "arr[" << i << "][" << j << "] = " << arr2[i][j] << ", address : " << &arr2[i][j] << endl;
        }
    }

    return 0;
}

다차원 배열

2차원 배열은 1차원 배열의 배열이다. 따라서, 3차원 이상의 다차원(고차원) 배열은 자신의 차원보다 낮은 차원의 배열의 배열로 이루어져 있다.
즉, 3차원 배열은 2차원 배열의 배열, 4차원 배열은 3차원 배열의 배열, N차원 배열은 N-1차원 배열의 배열이다.

따라서, 다차원 배열은 1차원 배열의 배열이며, 차원에 상관 없이 메모리 상에서 1차원 배열과 같이 선형으로 저장된다.
3차원 이상의 다차원 배열을 시각적으로 볼 수는 없지만, 배열의 특성을 이용해 다차원 배열의 순차 리스트를 구현할 수 있다.

정리

요약하면, 순차 리스트(Sequential List)는 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 자료구조이다.
삽입과 삭제 연산에는 비효율적이지만, 탐색에는 효율적이다.
순차 리스트는 배열을 이용해 구현할 수 있다.

• Previous
  [자료구조] 기본개념 및 종류
• Next
  [자료구조] 스택(Stack)