[자료구조] 02. 선형 리스트 (배열)

선형 리스트는 원소들이 순서를 가지고 1:1 관계로 나열된 자료구조다. 배열로 구현한 선형 리스트는 메모리에 원소가 연속으로 저장되므로 인덱스 접근이 빠르다.

---

1. 배열 리스트의 특징

항목	내용
저장 방식	연속된 메모리 공간에 저장
접근	iArray[iIndex]로 O(1) 접근
삽입	삽입 위치 뒤쪽 원소들을 한 칸씩 뒤로 이동
삭제	삭제 위치 뒤쪽 원소들을 한 칸씩 앞으로 이동
단점	크기를 미리 정해야 하고 중간 삽입/삭제가 느림

 

배열 리스트의 핵심은 논리적 순서와 물리적 저장 순서가 같다는 점이다. 그래서 0번, 1번, 2번처럼 바로 접근할 수 있지만, 중간에 값을 넣거나 빼면 뒤쪽 원소들이 움직여야 한다.

---

2. 삽입 연산

예를 들어 {10, 20, 30, 40}의 1번 위치에 15를 넣으려면, 기존 20, 30, 40을 오른쪽으로 한 칸씩 밀어야 한다.

단계	배열 상태
시작	10 20 30 40
40 이동	10 20 30 40 40
30 이동	10 20 30 30 40
20 이동	10 20 20 30 40
15 삽입	10 15 20 30 40

 

삽입은 뒤쪽 값부터 움직여야 한다. 앞에서부터 움직이면 아직 복사하지 않은 값을 덮어쓸 수 있다.

#include <stdio.h>

#define MAX_SIZE 100

int insertValue(int iArray[], int iCount, int iPosition, int iValue)
{
    int iMoveIndex;

    if (iCount >= MAX_SIZE)
    {
        printf("overflow\n");
        return iCount;
    }

    if (iPosition < 0 || iPosition > iCount)
    {
        printf("wrong position\n");
        return iCount;
    }

    iMoveIndex = iCount;

    while (iPosition < iMoveIndex)
    {
        iArray[iMoveIndex] = iArray[iMoveIndex - 1];
        iMoveIndex = iMoveIndex - 1;
    }

    iArray[iPosition] = iValue;
    iCount = iCount + 1;

    return iCount;
}

---

3. 삭제 연산

삭제는 삽입과 반대로 뒤쪽 원소를 앞으로 당긴다. {10, 15, 20, 30, 40}에서 1번 위치의 15를 삭제하면 20, 30, 40이 왼쪽으로 한 칸씩 이동한다.

int deleteValue(int iArray[], int iCount, int iPosition)
{
    int iMoveIndex;

    if (iPosition < 0 || iPosition >= iCount)
    {
        printf("wrong position\n");
        return iCount;
    }

    iMoveIndex = iPosition;

    while (iMoveIndex < iCount - 1)
    {
        iArray[iMoveIndex] = iArray[iMoveIndex + 1];
        iMoveIndex = iMoveIndex + 1;
    }

    iCount = iCount - 1;

    return iCount;
}

---

4. 출력 함수

자료구조 예제는 연산 후 상태를 확인하는 출력 함수가 있으면 디버깅하기 쉽다.

void printArrayList(int iArray[], int iCount)
{
    int iIndex;

    for (iIndex = 0; iIndex < iCount; iIndex++)
    {
        printf("%d ", iArray[iIndex]);
    }

    printf("\n");
}

---

5. C++ 구현 예제: vector

C에서는 배열 크기와 현재 개수 iCount를 직접 관리해야 한다. C++에서는 vector가 내부 배열 크기를 자동으로 관리해 준다. 그래도 중간 삽입과 삭제 때 뒤쪽 원소가 이동한다는 원리는 같다.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> vNumbers;
    int iIndex;

    vNumbers.push_back(10);
    vNumbers.push_back(20);
    vNumbers.push_back(30);
    vNumbers.push_back(40);

    vNumbers.insert(vNumbers.begin() + 1, 15);
    vNumbers.erase(vNumbers.begin() + 3);

    for (iIndex = 0; iIndex < (int)vNumbers.size(); iIndex++)
    {
        cout << vNumbers[iIndex] << " ";
    }

    cout << endl;

    return 0;
}

 

vector는 인덱스 접근이 빠르다는 점에서 배열 리스트와 같은 성격을 가진다. 다만 insert, erase를 중간에서 사용하면 C 구현처럼 뒤쪽 원소가 이동하므로 O(n) 비용이 든다.

---

6. 정리

• 배열 리스트는 인덱스 접근이 빠르다.
• 중간 삽입은 뒤에서 앞으로 밀어야 한다.
• 중간 삭제는 앞에서 뒤로 당겨야 한다.
• 삽입/삭제의 최악 시간복잡도는 O(n)이다.
• C 구현에서는 배열 크기와 현재 원소 개수 iCount를 반드시 따로 관리한다.

---