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

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

순차 자료구조 (Sequential Data Structure)

• 정의 : 데이터를 논리적 순서대로 메모리에 연속적으로 저장하는 구현 방식입니다.
• 핵심 특징 : 데이터의 논리적 순서와 메모리에 저장된 물리적 순서가 항상 일치합니다.
• 장점 : 인덱스를 통해 데이터에 빠르게 접근할 수 있습니다.
• 단점 : 삽입/삭제 시 데이터를 이동시켜야 하므로 비효율적일 수 있습니다. (↔ 연결 자료구조)

선형 리스트 (Linear List)

• 정의 : 데이터를 '나열'하는 가장 기본적인 자료구조로, 데이터들 간에 순서가 있는 리스트입니다.
• 구조 : 리스트의 각 데이터를 요소(element) 또는 노드(node)라고 부릅니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터(논리적 연결)로 구성됩니다.
  • 헤드 노드(Head Node) : 리스트의 시작
  • 테일 노드(Tail Node) : 리스트의 끝

선형 리스트의 구현 방식

1. 선형 순차 리스트 (Linear Sequential List) : 배열을 사용하여 구현. 일반적으로 '선형 리스트'라고 부릅니다.
2. 선형 연결 리스트 (Linear Linked List) : 포인터를 사용하여 구현. 일반적으로 '연결 리스트'라고 부릅니다.

선형 리스트의 연산과 알고리즘 (배열 기반)

배열을 사용한 선형 리스트에서는 논리적 순서를 유지하기 위해 데이터의 물리적 이동이 필요합니다.

삽입 (Insertion) 연산

1. 삽입할 위치를 찾습니다.
2. 삽입할 위치부터 마지막 요소까지 모든 데이터를 한 칸씩 뒤로 이동시켜 빈자리를 만듭니다.
3. 만들어진 빈자리에 새로운 데이터를 삽입합니다.

• 이동 횟수 : 뒤에서부터 이동해야 데이터 덮어쓰기를 방지할 수 있습니다.

삭제 (Deletion) 연산

1. 삭제할 데이터를 찾습니다.
2. 삭제할 데이터의 다음 위치부터 마지막 요소까지 모든 데이터를 한 칸씩 앞으로 당겨 빈자리를 채웁니다.

• 이동 횟수 : 앞에서부터 이동해야 빈 공간을 효율적으로 채울 수 있습니다.

선형 리스트의 응용 및 구현

선형 리스트, 배열은 다양한 수학적 개념을 표현하는 데 사용됩니다.

행렬 (Matrix) 표현

• 행렬은 행과 열로 구성된 2차원 자료구조로, 2차원 배열을 사용해 자연스럽게 표현할 수 있습니다.
• 전치 행렬(Transpose Matrix) : 원래 행렬의 행과 열을 맞바꾼 행렬입니다.
• 희소 행렬(Sparse Matrix) : 대부분의 요소가 0인 행렬입니다.
  • 2차원 배열로 그대로 저장하면 0을 저장하기 위한 메모리 공간 낭비가 심합니다.
  • 해결책: 0이 아닌 요소만 <행, 열, 값>의 형태로 추출하여 2차원 배열에 저장하면 메모리를 크게 절약할 수 있습니다.

다항식 (Polynomial) 표현

• 다항식 P(x) = a_n * x^n + ... + a_1 * x^1 + a_0 * x^0을 선형 리스트로 표현할 수 있습니다.
• 1차원 배열 표현: 배열의 인덱스를 다항식의 '차수'로, 배열의 값을 '계수'로 사용하는 방식입니다.
  • A[i] = x^i 항의 계수
  • 단점: 3x^1000 + 4 와 같이 최고 차수는 높지만 항의 개수가 적은 '희소 다항식'의 경우, 중간의 사용하지 않는 공간 때문에 극심한 메모리 낭비가 발생합니다.
• 2차원 배열 표현 (희소 다항식): <계수, 차수> 쌍을 배열에 저장하여 메모리 낭비를 줄입니다.