[자료구조] Array Vs List

Array Vs List

 

Array

• 번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료 구조를 나타낸다.

• 같은 종류의 데이터들이 순차적으로 저장되어, 값의 번호가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 된다.

• 배열의 첫 번째 요소의 메모리 주소를 첫 번째 주소, 기본 주소 또는 기본 주소라고 한다.

• 배열은 정의와 동시에 길이를 지정하며 길이를 바꿀 수 없다.

 

장점

• 인덱스를 통한 검색이 용이함(검색 속도가 빠름)

• 연속적이므로 메모리 관리가 편하다.

 

단점

• 배열은 길이를 바꿀 수 없다.

• 배열은 인덱스에 따라서 값을 유지하기 때문에, 엘리먼트가 삭제되어도 빈자리(null)가 남게 된다.

 

 

List

• 데이터를 순차적으로 저장하는 선형구조 자료구조이다.

• 리스트에서 인덱스는 절대적인 데이터의 위치가 아닌 리스트에서 몇 번째 데이터인지 정도의 의미를 가진다.(사진)

• 빈 엘리먼트를 허용하지 않는다.

• 불연속적으로 메모리 공간을 차지한다.

• 포인터를 통해 접근한다.

 

장점

• 포인터를 통하여 다음 데이터를 가리키고 있어 삽입 삭제에 용이하다.

• 리스트의 크기가 동적이다.

• 메모리 재사용이 편리하다.

 

단점

• 검색 성능이 좋지 않다. (불 연속적인 메모리 공간으로 하나하나 찾아야 한다)

• 포인터를 통한 다음 데이터를 가르키므로 추가적인 메모리 공간이 발생한다.

 

 

Array와 Listd의 요소 삭제 예시

 

Array는 해당 인덱스에 접근하여 데이터를 삭제 -> 빈 메모리 공간이 생김 -> 메모리 낭비

List는 해당 데이터의 데이터를 삭제하고 연결 포인터를 변경해줌 -> 빈 메모리가 발생하지 않음

 

요약

배열

데이터의 크기가 정해져 있고, 추가적인 삽입 삭제가 일어나지 않으며 검색을 필요로 할 때 유리. 

 

리스트

데이터의 크기가 정해져 있지 않고, 삽입 삭제가 많이 일어나며, 검색이 적은 경우 유리.