배열과 리스트

배열과 연결리스트

배열은

- 스택 영역에 자료를 저장하고 컴파일시 공간을 확보하게 됩니다.

- 자료를 순차적으로 저장하고 인덱스의 번호로 접근이 가능합니다.

 + 자료의 접근과 저장이 빠릅니다.

- 한번 확보한 배열의 크기를 변경하기가 어려워 메모리가 낭비되고 비효율적일 수 있습니다.

- 배열의 내부 요소를 정렬하고자 할 때 연결리스트에 비해 빠릅니다.

 + 인덱스 번호로 바로 접근해서 요소를 찾아내고 정렬하기 때문입니다.

- 내부 데이터의 탐색이나 정렬을 자주한다면 배열을 사용하는 편이 좋습니다.

 + 접근하기가 연결리스트에 비해 빠르기 때문 (인덱스)

연결리스트는

- 힙 영역에 자료를 저장하고 필요할 때마다 메모리를 확보해 사용합니다.

- 매번 데이터를 저장할 때마다 데이터를 위한 메모리를 확보해야 하므로 연산 속도가 배열보다 느립니다.

- 또한, 매번 포인터연산을 하므로 그 만큼의 비용이 발생합니다.

- 반면, 필요한 만큼의 메모리를 확보하므로 배열보다 효율적인 메모리 관리가 가능하다고 할 수 있습니다.

 + 요소가 작으면 배열이 메모리가 더 작습니다. 링크 필드의 포인터도 메모리를 차지하기 때문

- 연결리스트의 내부 요소를 정렬하고자 할 때 배열에 비해 느립니다.

 + 가장 작은 자료를 찾기 위해 순차적으로 접근해야하며 노드를 재연결하는 연산 과정이 필요하기 때문입니다.

- 내부 데이터의 삽입이나 삭제를 자주한다면 연결리스트를 사용하는 편이 좋습니다.

 + 삽입과 삭제시 재정렬할 필요가 없기 때문입니다.

출처 : http://wonjayk.tistory.com/249