[자료구조 기초] 시퀀스 자료구조 1 - 배열·리스트

시퀀스 자료구조 (Sequence Data Structure)

시퀀스 자료구조는 원소 간의 순서(Order) 를 유지하는 자료구조를 말한다. 즉, 데이터가 입력된 순서가 보존되며, 특정 위치(인덱스)나 앞·뒤 관계를 기준으로 원소에 접근할 수 있다.

대표적인 시퀀스 자료구조로는 배열(Array) 과 연결 리스트(Linked List) 가 있다. 이들은 데이터를 순차적으로 저장하고, 인덱스나 포인터를 통해 각 원소에 접근할 수 있다.

배열 (Array)

특징

배열에서는 원소들을 연속된 메모리 공간에 저장하고 , 호출할 때는 인덱스로 즉시 호출할 수 있도록 설계된 자료구조이다. 예컨데 복도식 아파트를 생각하면 된다. 아파트 호실이 연속적으로 이어져있고(101호, 102호, ..., 109호) 각 호실에는 정해진 사람이 살고 있는 것이다.

장점

배열의 장점은 인덱스를 통해서 바로 메모리에 저장된 주소값을 1:1로 계산하기 떄문에 데이터에 대한 접근이 매우 빠르다는 점이다. 또한 구조 특성 상 캐시 친화적이라는 특징도 있다.

제약점

다만 인덱스 별 주소가 연속적으로 배치되어 있기 때문에, 인덱스 중간에 원소를 삽입하려면 원소 전체가 이동해야하는 단점이 있다. 또한, 길이가 고정되어있다면 확장, 축소가 번거로울 수 있다.

#include <array>


std::array<int, 4> a{1, 2, 3, 4};
a[0] = 10; // 접근/수정

연결 리스트 (Linked List)

특징

각 원소가 포인터로 연결되어 있다. 단일 / 이중 / 원형 (Singly / Doubly / Circular) 링크드 리스트의 형태로 변형해서 사용 가능하다. 예컨데 어릴 적 하던 보물찾기를 떠올려보면 이해하기 쉬울 수 있다. 각 보물상자 안에는 보물과 함께 다음 보물이 숨겨진 장소(주소)가 나와있는 구조이다.

장점

이미 노드를 알고 있다면 노드의 주소값만 수정하면 되기 때문에 그 노드 인근에 원소의 삽입과 삭제가 빠르다. 또한 크기 변경에 제약이 없다

제약점

인덱스에 바로 접근하는 것이 불가능하기 때문에 탐색이 느리다. 임의의 원소에 접근하기 위해서는 처음부터 링크를 따라가야 한다. 또한 메모리에 연속적으로 저장되어있지 않기 때문에 캐시 미스가 증가하고, 포인터 오버헤드가 생길 수 있다.

#include <list>

void listEnds()
{
    std::list<int> lst;
    lst.push_front(5);     // [5]
    lst.push_back(10);     // [5, 10]
    lst.pop_front();       // [10]
    lst.pop_back();        // []
}

#include <list>
#include <algorithm> // std::find, std::next

void listInsertEraseMiddle()
{
    std::list<int> lst{10, 20, 30};

    auto it = std::next(lst.begin()); // 20 가리킴
    lst.insert(it, 99);               // [10, 99, 20, 30]

    it = std::find(lst.begin(), lst.end(), 20);
    if (it != lst.end())
    {
        it = lst.erase(it);           // 20 제거 → [10, 99, 30], it는 30 가리킴
    }
}

#include <list>

void listSplice()
{
    std::list<int> a{1, 2, 3};
    std::list<int> b{7, 8, 9};

    auto pos = std::next(a.begin());  // a에서 2의 위치
    a.splice(pos, b, b.begin());      // b의 7을 a의 2 앞에 이동
    // a: [1, 7, 2, 3], b: [8, 9]
}