[비교]배열(Array)과 링크드 리스트(Linked List)의 차이

목표

l  배열(Array)과 리스트(Linked List)의 차이를 알자.

 

l  장단점

 

 

* 본문에서 말하는 List는 자료구조에 일종인 Linked List 입니다.

 

배열( Array )의 특징

 

- 같은 자료형을 가진 변수를 하나로 나타낸 것.

 

- 연속된 메모리 공간으로 이루어져있는 것.

 

- 정적 표현.

 

- 인덱스를 이용하여 표현.

- 지역성을 가지고 있다.

배열의 장점

- 인덱스를 통한 검색이 용이함.

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

 

배열의 단점

- 한 데이터를 삭제하더라도 배열은 연속해야 하므로 공간이 남는다. 즉, 메모리 낭비

- 정적이므로 배열의 크기를 컴파일 이전에 정해주어야 한다.

- 컴파일 이후 배열의 크기를 변동 할 수 없다.

 

리스트(Linked List)의 특징

- 순서가 있는 데이터의 집합.

- 불연속적으로 메모리 공간을 차지.

- 동적 표현

- 인덱스가 없음.

- 포인터를 통한 접근

리스트의 장점

- 포인터를 통하여 다음 데이터의 위치를 가르켜고 있어 삽입 삭제의 용이.

- 동적이므로 크기가 정해져 있지 않다.

- 메모리의 재사용 편리

- 불연속적이므로 메모리 관리의 편리

 

리스트의 단점

- 검색 성능이 좋지 않다.

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

 

l  정리

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

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

 

 

* 2020.04.12 추가 사항

리스트 보다 검색 성능이 좋지 않은 이유에 대하여 질문이 들어와 추가 합니다.

배열은 int num[4] 이라고 선언하고 사용하면, 주소값 + 4byte의 형식으로 메모리가 연속적으로 잡히게 됩니다.

이에 비하여 리스트는 주소가 연속적이지 않기 때문에 예측을 할 수 없고, 그만큼 소요 시간이 들어가게 됩니다. 

* 2021.09.27 수정 사항

댓글에 나온 것 처럼 혼란이 있을까 수정합니다.

본문에 나오는 List는 자료구조에서 사용되는 Linked List 기준입니다. 

자바에서 사용되는 List에 일종인 Vector, Array List와는 차이가 있습니다. 

조금 더 세밀하게 적어야 됐었는데 혼란을 야기한점 죄송합니다.