[자료구조] 리스트(List) - 1

 

리스트라는 자료 구조는 구현 방법에 따라서 다음과 같이 크게 두 가지로 나뉘어 진다.

 

 

 

 

먼저 순차리스트는 …

배열을 기반으로 구현된 리스트이다.

 

이어서 연결리스트는

메모리의 동적 할당을 기반으로 구현된 리스트 이다.

 

 

순차리스트는 배열로 구현되어 있기 때문에 …

 

다음 그림을 보면…

1000	1001	1002	1003	1004	1005	1006	1007	1008	1009

위의 구조를 메모리라고 생각을 해보자..

 

배열의 경우 배열의 크기를 5라고 하고 메모리에 잡았을 경우.

		100	200	300	400	500
1000	1001	1002	1003	1004	1005	1006	1007	1008	1009
		0	1	2	3	4

 

이렇게 나란히 배열의 크기만큼 잡히므로

데이터의 참조가 쉽다 (인덱스로 바로 접근 및 참조가능)

그러나 장점이 있으면 단점도 존재하는법!

배열의 크기는 초기에 결정되어야 한다.(변경이 불가능함)

삭제의 과정에서 데이터의 이동 혹은 복사가 매우 많이 일어난다.