자료구조) 순차 표현, 연결 표현

데이터를 저장하는 방식에는 여러 가지가 있지만, 대표적으로 순차 표현과 연결 표현 방식이 많이 사용된다. 이 두 방식은 데이터를 어떻게 메모리에 배치하고 접근하는지에 따라 차이가 있다.

순차 표현 (Sequential Representation)

순차 표현은 데이터를 연속된 메모리 공간에 저장하는 방식이다.

일반적인 배열(Array)과 같이 인접한 메모리 주소에 데이터를 배치하는 구조를 말한다.

• 각 원소가 연속된 메모리 공간에 저장됨.

• 배열처럼 인덱스를 사용하여 접근 속도가 빠름 (O(1)).

• 데이터 크기가 고정적이거나 크기를 미리 알 때 유리함.

• 데이터 삽입/삭제 시 비효율적 (O(n)) → 중간에 요소를 추가하거나 삭제하면, 나머지 요소들을 이동해야 함.

int arr[5] = {10, 20, 30, 40, 50};  // 순차적으로 저장된 배열

• arr[2]에 즉시 접근 가능 → O(1)

• 하지만 중간에 25를 삽입하면 30, 40, 50을 한 칸씩 뒤로 이동해야 함 → O(n)

연결 표현 (Linked Representation)

연결 표현은 데이터를 저장할 때 각 데이터 요소가 다음 요소를 가리키는 포인터를 포함하여 저장하는 방식이다.

대표적인 예로 연결 리스트(Linked List) 가 있다.

• 데이터가 비연속적인 메모리 공간에 저장된다.
• 삽입/삭제가 빠름 (O(1) ~ O(n)) → 새로운 노드를 추가하거나 삭제해도 다른 요소들의 위치를 변경할 필요 없다.
• 하지만 임의 접근(Random Access)이 불가능 → 특정 위치의 요소를 찾으려면 처음부터 순차적으로 탐색해야 한다. (O(n)).

struct Node {
    int data;
    Node* next;
};

Node* head = new Node{10, nullptr};
head->next = new Node{20, nullptr};
head->next->next = new Node{30, nullptr};

• head는 첫 번째 노드를 가리키고, 각 노드는 다음 노드를 가리키는 포인터를 포함한다.

• 특정 위치를 찾으려면 처음부터 탐색해야 한다 → O(n)

언제 어떤 방식?

• 빠른 임의 접근(Random Access)이 필요할 때 → 순차 표현(배열)
  • 예) 배열 인덱스를 사용하여 빠르게 데이터에 접근해야 하는 경우
• 삽입/삭제가 빈번할 때 → 연결 표현(연결 리스트)
  • 예) 데이터의 크기가 자주 변경되거나, 삽입/삭제가 많을 경우