[자료구조] Array와 List

배열(Array)

• 여러 데이터를 하나의 이름으로 그룹핑해서 관리 하기 위한 자료구조. index와 값의 쌍으로 구성
• index는 값에 대한 유일무이한 식별자
• 논리적 저장 순서와 물리적 저장 순서가 일치 => index로 해당 원소에 접근할 수 있다. (O(1))
• 연속된 메모리의 공간으로 이루어져 있다
• 배열은 정의와 동시에 길이를 지정하며 길이를 바꿀 수 없다.

장점

• 인덱스를 통한 검색이 용이함.
• 연속적이므로 메모리 관리가 편하다.

단점

• 크기가 고정되어 있기 때문에 빈 공간이 남아 있을 수 있다. => 메모리 낭비
• 정적이므로 배열의 크기를 컴파일 이전에 정해주어야 한다.
• 컴파일 이후 배열의 크기를 변동 할 수 없다.

 

리스트(List)

• 리스트는 순서가 있는 엘리먼트의 모임으로 배열과는 다르게 빈 엘리먼트는 절대 허용하지 않는다.
• 리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재 라는 장점을 취함
• 리스트에서 인덱스는 몇 번째 데이터인가 정도(순서)의 의미를 가진다. 
• 순차성을 보장하지 못하기 때문에 spacial locality 보장이 되지 않아서 cash hit가 어렵다.(데이터 갯수가 확실하게 정해져 있고, 자주 사용된다면 array가 더 효율적이다.)

장점

• 동적이므로 크기가 정해져 있지 않다.
• 메모리의 재사용 편리

단점

• 검색 성능이 좋지 않다
• 포인터를 통해 다음 데이터를 가르키므로 추가적인 메모리 공간 발생.

 

 

	크기	조회
Array	고정	빠름
List	가변	느림

• 배열 : 데이터의 크기가 정해져 있고, 추가적인 삽입 삭제가 일어 나지 않으며 검색을 필요로 할 때 유리.
• 리스트 : 데이터의 크기가 정해져 있지 않고, 삽입 삭제가 많이 일어나며, 검색이 적은 경우 유리.