순차 자료구조와 선형리스트

요약

순차 자료구조는 자료를 논리적 순서에 따라 메모리에 연속적으로 저장하는 방식으로, 논리적 순서와 물리적 순서가 일치하는 특징을 가집니다.
이는 주로 배열(Array) 을 통해 구현됩니다.

선형 리스트는 순서가 있는 자료들의 집합으로, 순차 자료구조를 이용해 구현될 경우 '선형 순차 리스트' 라고 불립니다.
이 구조의 가장 큰 특징은 원소의 삽입 및 삭제 연산 시, 리스트의 연속성을 유지하기 위해 다른 원소들의 위치를 이동시켜야 한다는 점입니다.
이로 인해 삽입 및 삭제 연산은 비효율적일 수 있습니다.

다차원 배열을 사용하여 선형 리스트를 표현할 때는 논리적인 다차원 구조를 물리적인 1차원 메모리 공간에 매핑하는 방법이 필요하며,
주로 행 우선 순서(Row-Major Order) 또는, 면 우선 순서(Page-Major Order) 방식이 사용됩니다.

C 언어는 2차원 배열에 행 우선 순서를, 3차원 배열에 면 우선 순서를 적용합니다.
선형 리스트는 행렬, 특히 대부분의 원소가 0인 희소 행렬(Sparse Matrix)이나 다항식을 표현하는 데 응용될 수 있으나,
표준 배열 구현은 메모리 공간 낭비를 초래할 수 있어 효율적인 대안이 요구됩니다.

---

1. 순차 자료구조의 핵심 개념

정의 및 특징

순차 자료구조(Sequential Data Structure)는 구현할 자료들을 논리적 순서에 따라 메모리에 연속적으로 저장하는 방식을 의미합니다.
핵심적인 특징은 자료의 논리적 순서와 메모리에 저장되는 물리적 순서가 항상 일치해야 한다는 것입니다.
C 프로그래밍 언어에서는 배열(Array)이 순차 자료구조를 구현하는 대표적인 기법입니다.

순차 자료구조와 연결 자료구조 비교

순차 자료구조는 연결 자료구조와 대조적인 특징을 가집니다.
연결 자료구조는 물리적 저장 위치와 상관없이 링크(포인터)를 통해 논리적 순서를 표현합니다.

구분	순차 자료구조	연결 자료구조
메모리 저장 방식	메모리의 시작 위치부터 빈자리 없이 자료를 순서대로 연속하여 저장합니다. (논리적 순서 = 물리적 순서)	메모리에 저장된 물리적 위치나 순서와 상관없이, 링크에 의해 논리적인 순서를 표현합니다.
연산 특징	삽입·삭제 연산 후에도 자료가 연속적으로 저장되도록 원소 이동이 발생하며, 논리적 순서와 물리적 순서가 일치하도록 유지됩니다.	삽입·삭제 연산 시 링크 정보만 변경되고 원소의 물리적 위치는 변경되지 않습니다.
프로그램 기법	배열(Array)을 이용하여 구현합니다.	포인터(Pointer)를 이용하여 구현합니다.

2. 선형 리스트의 이해

정의 및 용어

선형 리스트(Linear List)는 자료를 구조화하는 가장 기본적인 방법인 '나열'을 통해 구현된 리스트입니다.
순서를 갖는 자료들의 집합으로, '순서 리스트(Ordered List)'라고도 합니다.

• 노드 (Node): 리스트를 구성하는 각 요소(element)입니다.
  일반적으로 데이터와 다음 노드를 가리키는 포인터(링크)로 구성됩니다.
• 머리 노드 (Head Node): 리스트의 가장 처음에 있는 노드입니다.
• 꼬리 노드 (Tail Node): 리스트의 가장 마지막에 있는 노드입니다.
  
• 앞쪽 노드 (Predecessor Node): 특정 노드의 바로 앞에 위치한 노드입니다.
  
• 다음 노드 (Successor Node): 특정 노드의 바로 뒤에 위치한 노드입니다.

표현 방식

선형 리스트는 일반적으로 다음과 같은 형식으로 표현됩니다.

• 일반 형식: 리스트 이름 = (원소1, 원소2, ..., 원소n)
  • 예: 동창 = (상원, 상범, 수영, 현정)
• 공백 리스트: 원소가 없는 리스트는 리스트 이름 = ( )로 표현합니다.

구현 방식

선형 리스트는 두 가지 주요 방식으로 구현될 수 있습니다.

• 선형 순차 리스트 (Linear Sequential List)
  • 원소를 논리적 순서대로 메모리에 연속하여 저장하는 순차 자료구조 방식의 리스트입니다.
    일반적으로 '선형 리스트'라고 하면 이 방식을 지칭하는 경우가 많습니다.
• 선형 연결 리스트 (Linear Linked List)
  • 원소를 논리적 순서대로 연결하여 구성하는 연결 자료구조 방식의 리스트입니다.
    보통 '연결 리스트(Linked List)'라고 불립니다.

3. 배열을 이용한 선형 리스트 표현

선형 순차 리스트는 주로 1차원 또는 다차원 배열을 사용하여 구현됩니다.

다차원 배열의 물리적 저장

컴퓨터 메모리는 1차원 구조이므로, 2차원 이상의 논리적 배열 구조를 저장하기 위해서는 이를 1차원 물리적 순서로 변환하는 규칙이 필요합니다.

2차원 배열

• 행 우선 순서 (Row-Major Order): 첫 번째 인덱스인 행 번호를 기준으로 데이터를 저장합니다. C 컴파일러가 사용하는 방식입니다.
  • sale[0][0], sale[0][1], ..., sale[1][0], sale[1][1], ... 순서로 저장됩니다.
  • 위치 계산 공식: α + (i × nj + j) × ℓ
    • α: 배열 시작 주소
    • A[ni][nj]: ni개의 행, nj개의 열을 가진 배열
    • A[i][j]: i행 j열 원소
    • ℓ: 원소의 길이(바이트)
• 열 우선 순서 (Column-Major Order): 마지막 인덱스인 열 번호를 기준으로 데이터를 저장합니다.
  • sale[0][0], sale[1][0], ..., sale[0][1], sale[1][1], ... 순서로 저장됩니다.
  • 위치 계산 공식: α + (j × ni + i) × ℓ

3차원 배열

• 면 우선 순서 (Page-Major Order): 첫 번째 인덱스인 면 번호를 기준으로 데이터를 저장합니다. C 컴파일러가 사용하는 방식입니다.
  • 위치 계산 공식: α + {(i × nj × nk) + (j × nk) + k} × ℓ
    • A[ni][nj][nk]: ni면, nj행, nk열을 가진 배열
    • A[i][j][k]: i면 j행 k열 원소
• 열 우선 순서 (Column-Major Order): 마지막 인덱스인 열 번호를 기준으로 데이터를 저장합니다.
  • 위치 계산 공식: α + {(k × nj × ni) + (j × ni) + i} × ℓ

4. 선형 리스트의 주요 연산

선형 순차 리스트에서 삽입과 삭제 연산은 논리적·물리적 순서의 일관성을 유지하기 위해 원소의 이동을 수반합니다.

원소 삽입 (Element Insertion)

리스트 중간에 원소가 삽입되면, 삽입 위치 이후의 모든 원소는 한 자리씩 뒤로 이동해야 합니다.br/>

1. 빈자리 만들기: 삽입할 위치부터 마지막 원소까지 순차적으로 한 칸씩 뒤로 이동시킵니다. 데이터 덮어쓰기를 방지하기 위해 마지막 원소부터 이동을 시작해야 합니다.
2. 원소 삽입: 확보된 빈자리에 새로운 원소를 저장합니다.

• 자리 이동 횟수: (n+1)개 원소로 구성된 리스트의 k번 자리에 삽입 시, k번 원소부터 마지막 n번 원소까지 이동합니다.
  • 이동 횟수 = n – k + 1

원소 삭제 (Element Deletion)

리스트 중간의 원소가 삭제되면, 삭제된 위치 이후의 모든 원소는 한 자리씩 앞으로 이동해야 합니다.

1. 원소 삭제: 해당 위치의 원소를 제거합니다.
2. 빈자리 채우기: 삭제된 자리 바로 다음 원소부터 마지막 원소까지 순차적으로 한 칸씩 앞으로 이동시킵니다. 데이터 덮어쓰기를 방지하기 위해 삭제된 자리 바로 다음 원소부터 이동을 시작해야 합니다.

• 자리 이동 횟수: (n+1)개 원소로 구성된 리스트의 k번 자리 원소 삭제 시, (k+1)번 원소부터 마지막 n번 원소까지 이동합니다.
  • 이동 횟수 = n - k

5. 선형 리스트의 응용

행렬 표현

행렬은 행과 열로 구성된 자료구조로, 2차원 배열을 이용해 쉽게 표현할 수 있습니다.

• 희소 행렬 (Sparse Matrix): 대부분의 원소가 0인 행렬입니다. 이를 표준 2차원 배열로 표현하면 0을 저장하기 위한 메모리 공간 낭비가 심각해집니다.
• 효율적 표현: 메모리 효율을 높이기 위해, 0이 아닌 원소만 추출하여 <행번호, 열번호, 원소> 형태의 순서쌍으로 구성하고,
  이를 별도의 2차원 배열에 저장합니다. 이 배열의 0번 행에는 원래 행렬의 크기(행, 열)와 0이 아닌 원소의 개수 정보를 저장합니다.

다항식 표현

다항식은 aX^e (a: 계수, e: 지수) 형태의 항들의 합으로 구성됩니다.

• 배열 표현의 문제점: 다항식을 1차원 배열(배열 인덱스를 지수로 사용)로 표현할 경우, 최고 차수는 높지만 항의 개수가 적으면 심각한 메모리 낭비가 발생합니다.
  예를 들어, 4x^1000 + 2 라는 다항식을 표현하려면 크기가 1001인 배열이 필요하지만 실제로는 단 2개의 공간만 사용하게 됩니다.
• 응용: 순차 리스트를 이용해 다항식의 덧셈과 같은 연산을 구현할 수 있습니다.