[자료구조]Array와 List(그리고 Java List)
Array
- 여러 데이터를 하나의 이름으로 Grouping해서 관리하기 위한 자료구조
- Index와 값으로 구성
- Array에서의 Index는 값에 대한 고유 식별자이다
- List의 인덱스는 단순히 몇 번째 데이터인가의 순서를 나타냄
- 논리적 저장 순서와 물리적 저장 순서가 일치한다
- 연속된 메모리의 공간으로 이루어져 있다.
- 정적타입으로 정의와 동시에 길이를 지정하며 변경할 수 없다.
장점
- 인덱스를 통한 검색이 용이하다.
- 연속적으로 메모리에 적재되므로 관리하기에 좋다
단점
- 크기가 고정되어 있기 때문에 어떤 값이 삭제되면, 삭제된 곳은 빈 공간이 된다.
→ 메모리 낭비 우려가 있음
- 정적이므로 크기를 컴파일 이전에 정해주어야 한다.
List
- 순서가 있는 Element들의 모임 (Sequence)으로 배열과는 다르기 빈 엘리먼트는 허용하지 않는다.
- 배열이 가지고 있는 Index라는 장점을 버리는 대신 빈틈없는 데이터의 적재 라는 장점을 취한다.
- 리스트의 Index는 몇번째 데이터인가의 순서라는 의미를 가진다.
- 빈 엘리먼트는 허용하지 않지만 Java에서는 허용하는 경우가 존재한다.
- 불연속 적으로 메모리 공간을 차지하여 메모리 관리가 용이하다.
- 포인터를 통한 접근을 한다.
- 동적타입이며 크기가 정해져 있지 않다.
장점
- 포인터를 사용하여 다음 값의 위치를 가르키고 있으므로 삽입/삭제가 용이하다.
- 메모리의 재사용이 용이하다.
단점
- 불연속적인 메모리 공간을 사용하기 때문에 검색 성능이 좋지 못하다.
- 포인터를 통하여 다음값을 가르키므로 배열 대비 추가적인 메모리 공간이 필요하다.
- 빈 요소를 허용하지 않는다.
Conclusion
- 배열 : 데이터의 크기가 정해져 있고, 추가적인 삽입 삭제가 일어나지 않으며 검색을 필요로 할 경우에 유리
- 리스트 : 데이터의 크기가 정해져 있지 않고, 삽입/삭제가 많이 일어나며, 검색이 적은 경우 유리하다.