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

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

---

순차 자료구조의 개념

- 구현할 자료들을 논리적 순서로 메모리에 연속 저장하는 구현 방식

- 논리적인 순서와 물리적인 순서가 항상 일치해야 함

- C 프로그래밍에서 순차 자료구조의 구현 방식 제공하는 프로그램 기법은 배열

선형 리스트의 표현

리스트 : 자료를 구조화하는 가장 기본적인 방법은 나열하는 것

선형 리스트 Linear List

순서 리스트 Ordered List

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

리스트의 표현 형식

선형 리스트의 저장

순차 방식으로 구현하는 선형 순차 리스트(선형 리스트)

•순차 자료구조는 원소를 논리적인 순서대로 메모리에 연속하여 저장

 

연결 방식으로 구현하는 선형 연결 리스트(연결 리스트)

선형 리스트에서 원소 삽입

- 선형리스트 중간에 원소가 삽입되면, 그 이후의 원소들은 한 자리 씩 자리를 뒤로 이동하여

물리적 순서를 논리적 순서와 일치시킴

원소 삽입 방법

① 원소를 삽입할 빈 자리 만들기

- 삽입할 자리 이후의 원소들을 한 자리씩 뒤로 이동

 

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

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

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

선형 리스트에서 원소 삭제

선형리스트 중간에서 원소가 삭제되면, 그 이후의 원소들은 한 자리씩 앞으로 이동하여

물리적 순서를 논리적 순서와  일치시킴

원소 삭제 방법

① 원소 삭제하기

② 삭제한 빈 자리 채우기

☞ 삭제한 자리 이후의 원소들을 한자리씩 앞으로 자리 이동

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

(n+1)개의 원소로 이루어진 선형 리스트에서 k번 자리의 원소를 삭제한 경우

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