순차 자료구조와 선형 리스트의 이해 (3장)

선형 리스트 란 리스트에 나열한 원소들이 순서대로 나열된 리스트로 순서 리스트 라고도 합니다.
순차 자료구조 란 논리적인 순서와 물리적인 순서가 항상 일치해야 하는 자료구조 입니다.
자료를 구조화 하는 가장 기본적인 방법은 나열이며, 이렇게 나열한 목록을 리스트(List)라고 합니다.

리스트를 표현하는 형식

리스트 이름 = (원소1, 원소2, ..., 원소 n)
공백 리스트 이름 = ()

선형 리스트의 연산
선형 리스트에서 삽입 또는 삭제 연산을 하면 원소들의 논리적 순서가 바뀌기 때문에 물리적 순서도 바뀌어야 합니다

삽입 연산에 따른 원소의 이동 횟수 = 마지막 원소의 인덱스 - 삽입할 자리의 인덱스 + 1
삭제 연산에 따른 원소의 이동 횟수 = 마지막 원소의 인덱스 - 삭제한 자리의 인덱스

선형 리스트의 구현
선형 리스트는 c프로그래밍의 배열을 사용해 구현합니다. 배열은 인덱스, 원소의 쌍으로 구성되어 메모리에 연속적으로 할당되는데, 이때 인덱스는 배열 원소의 순서를 나타내며 배열 원소들이 순서대로 메모리에 연속하여 순차 저장됩니다.

희소 다항식의 선형 리스트 표현
희소 다항식은 메모리 사용 효율성을 높이기 위해 지수에 따라 (지수+1) 크기의 배열을 생성하는 방법 대신 항의 개수에 따라 배열 크기를 결정하는 방법을 사용하여 <지수, 계수> 쌍을 2차원 배열에 저장합니다.

행렬의 선형 리스트 표현
희소행렬을 처리하기 위해 선형 리스트로 표현하고, 행과 열 인덱스가 있는 2차원 배열을 사용하여 구현합니다.