자료구조...4

순차 자료구조

데이터를 순서대로 저장하고 인덱스를 부여하여 관리하는 자료구조를 말한다. 배열을 이용해 리스트를 구현한 선형 리스트(또는 ArrayList)를 포함한다.

 

선형 리스트

데이터가 메모리에 물리적으로 연속적으로 저장되기 때문에 리스트 중간에서 데이터를 삽입하거나 삭제하는 연산을 하는 경우 데이터를 옮긴 후 동작을 처리해야 하는 오버헤드가 발생한다.

 

- 원본 데이터

인덱스	0	1	2	3	4
데이터	10	20	30	40

 

- 리스트 끝에 데이터를 삽입하는 경우

인덱스	0	1	2	3	4
데이터	10	20	30	40	50

빈 공간에 데이터를 삽입하고 종료한다.

 

- 리스트 중간에 데이터를 삽입하는 경우

인덱스	0	1	2	3	4
데이터	10	20	30	40	40

인덱스	0	1	2	3	4
데이터	10	20	30	30	40

인덱스	0	1	2	3	4
데이터	10	20	50	30	40

원하는 위치에 빈 공간이 만들어질 때까지 데이터들을 옮겨준 뒤 데이터를 삽입한다.

 

- 리스트 끝의 데이터를 삭제하는 경우

인덱스	0	1	2	3	4
데이터	10	20	30	40	50

데이터를 삭제하고 종료한다.

 

- 리스트 중간에 데이터를 삭제하는 경우

인덱스	0	1	2	3	4
데이터	10	20	50	30	40

인덱스	0	1	2	3	4
데이터	10	20	30	30	40

인덱스	0	1	2	3	4
데이터	10	20	30	40	40

해당 값을 제거한 뒤 빈 공간이 없어질 때까지 데이터를 옮겨준다.

 

※ 데이터를 옮길 때는 기존 값을 제거하는 동작을 하지 않는다. 이해를 돕기 위한 표현일 뿐이다.