[ 자료구조 및 알고리즘 ] 4. 순차 자료구조 - 1.선형 리스트

1. 선형 리스트

리스트(List) :자료를 나열한 목록

선형 리스트(Linear List) 

= 순서 리스트(Ordered List)

- 자료들 간에 순서를 갖는 리스트 

순서를 가짐

- 리스트의 표현 형식: 리스트 이름 = (원소1, 원소2, ..., 원소n)

- 선형 리스트에서 원소를 나열한 순서는 원소들의 순서가 됨.

- [표4-2]의 동창이름 선형 리스트의 표현

  동창 = (상원, 승희, 수영, 철이)

 

-  공백 리스트

: 원소가 하나도 없는 리스트 

빈 괄호를 사용하여 표현

   공백리스트이름 = ( )

 

 

선형 리스트의 저장

: 원소들의 논리적 순서와 같은 순서로 메모리에 저장

⇒ 순차 자료구조
-  원소들의 논리적 순서 = 원소들이 저장된 물리적 순서

-  [표4-2]의 동창 선형 리스트가 메모리에 저장된 물리적 구조

-  순차 자료구조의 원소 위치 계산

• 선형 리스트가 저장된 시작 위치 : α

•원소의길이: l

•i번째원소의위치= α+(i-1)xl

 

선형 리스트에서 원소 삽입

선형리스트 중간에 원소가 삽입

⇒ 그 이후의 원소들은 한자리씩 자리를 뒤로 이동하여 물리적 순서를 논리적 순서와 일치시킴

- 원소 삽입 방법

1 원소를 삽입할 빈 자리 만들기
☞ 삽입할 자리 이후의 원소들을 한자리씩 뒤로 자리 이동

2 준비한 빈 자리에 원소 삽입하기

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

• (n+1)개의 원소로 이루어진 선형 리스트에서 k번 자리에 원소를 삽입하는 경우

                : k번 원소부터 마지막 인덱스 n번 원소까지 (n-k+1)개의 원소를 이동

− 이동횟수 = n-k+1 = 마지막 원소의 인덱스 - 삽입할 자리의 인덱스 +1

 

선형 리스트에서 원소 삭제

선형리스트 중간에서 원소가 삭제

⇒ 그 이후의 원소들은 한자리씩 자리를 앞으로 이동하여 물리적 순서 를 논리적 순서와 일치시킴

- 원소 삭제 방법 

1 원소 삭제하기

2 삭제한 빈 자리 채우기
☞ 삭제한 자리 이후의 원소들을 한자리씩 앞으로 자리 이동

- 삭제 후, 빈 자리를 채우기 위한 자리이동 횟수
• (n+1)개의 원소로 이루어진 선형 리스트에서 k번 자리의 원소를 삭제한 경우 : (k+1)번 원소부터 마지막 n번 원소까지 (n-(k+1)+1)개의 원소를 이동

− 이동횟수 = n-(k+1)+1 = n-k = 마지막 원소의 인덱스-삭제한 자리의 인덱스

 

선형 리스트의 구현

 - 순차 구조의 배열을 사용

• 배열 : <인덱스, 원소>의 순서쌍의 집합 

• 배열의 인덱스 : 배열 원소의 순서 표현