[자료구조] 선형 리스트 (Linear List)

● 선형 리스트 (Linear List)

- 데이터를 논리적인 순서대로 메모리에 연속하여 저장하는 구현하는 방식

- 데이터의 논리적인 순서와 기억 장소에 저장되는 물리적 순서가 일치하는 구조다.

- 배열을 이용해 구현한다.

 

● 장점

- 인덱스(Index)로 접근할 수 있기 때문에 접근 속도가 매우 빠르다.

- 연속된 메모리 공간에 존재하기 때문에 관리하기가 편하다.

 

● 단점

○ 배열을 이용해 구현하기 때문에 배열이 갖고 있는 메모리 사용의 비효율성 문제를 그대로 가지고 있다. 

- 배열의 크기 >> 데이터 수 : 메모리 공간의 낭비를 가져온다.

- 배열의 크기 << 데이터 수 : 데이터를 저장할 수 없다.

○ 삽입 & 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해 원소들을 이동시키는 추가 작업과 시간이 소요된다.

- 원소들의 이동 작업으로 인한 오버헤드로 원소의 개수가 많고 삽입 & 삭제 연산이 많은 경우 더 많이 발생한다.

 

● 삽입 연산

- 새로운 원소를 삽입하려면, 삽입할 자리를 만들기 위해, 삽입할 위치 이후의 원소들을 모두 한 자리씩 뒤로 옮겨야한다.

① 원소를 삽입할 빈 자리 만들기 (삽입할 자리 이후의 원소들을 한 칸씩 뒤로 이동)

② 빈 자리에 원소 삽입하기

○ 삽입할 자리를 만들기 위한 자리 이동 횟수

- N 개의 원소로 이루어진 선형 리스트에서 인덱스 K에 원소를 삽입하는 경우

- 마지막 원소의 인덱스 - 삽입할 자리의 인덱스 + 1 -> (N - 1) - K + 1

 

● 삭제 연산

- 원소를 삭제하려면, 삭제한 이후에 빈자리를 채워주기 위해 , 삭제한 위치 이후의 원소들을 모두 한 자리씩 앞으로 옮겨야한다.

① 원소 삭제하기

② 삭제한 빈 자리 채우기 (삭제한 자리 이후의 원소들을 한 칸씩 앞으로 이동)

○ 삭제후, 빈 자리를 채우기 위한 자리 이동 횟수

- N개의 원소로 이루어진 선형 리스트에서 인덱스 K의 원소를 삭제하는 경우

- 마지막 원소의 인덱스 - 삭제한 자리의 인덱스 -> (N - 1) - K

 

● 1차원 배열 선형 리스트

- 시작 주소 + (인덱스 * 자료형의 크기)

 

● 2차원 배열 선형 리스트

- 논리적으로 표현할 때는 행과 열의 구조로 나타낸다.

- 실제로 메모리에 저장되는 물리 구조는 1차원의 선형 구조로 저장된다.

- 2차원의 논리적 순서를 1차원의 물리적 순서로 변환해야한다.

○ 행 우선 순서 방법

- 시작 주소 + (행의 인덱스 * 열의 개수 + 열의 인덱스) * 자료형의 크기

 

○ 열 중심 순서 방법

- 시작 주소 + (열의 인덱스 * 행의 개수 + 행의 인덱스) * 자료형의 크기

 

● 3차원 배열 선형 리스트

- 논리적인 표현할 때는 면, 행, 열의 구조로 나타낸다.

- 실제로 메모리에 저장되는 물리 구조는 1차원의 선형 구조로 저장된다.

- 3차원의 논리적 순서를 1차원의 물리적 순서로 변환해야한다.

○ 면(행) 우선 순서 방법

- 시작 주소 + {(면의 인덱스 * 행의 개수 * 열의 개수) + (행의 인덱스 * 열의 개수) + 열의 인덱스} * 자료형의 크기

 

○ 열 우선 순서 방법

-  시작 주소 + {(열의 인덱스 * 면의 개수 * 행의 개수) + (행의 인덱스 * 면의 개수) + 면의 인덱스} * 자료형의 크기