배열과 링크 목록의 차이점에 대해 각각의 장점 단점 요약

배열

장점

・랜덤한 값의 읽기가 고속
배열에는 인덱스가 있으므로 무작위 값을 검색할 때 매우 빠릅니다. 그 인덱스의 요소로 날아가면 된다.
그 성질 때문에 이분 탐색 등과도 궁합이 좋다.

단점

· 메모리의 연속 슬롯 사용
무슨 일이냐고 하면, 배열의 길이분의 연속한 슬롯이 비어 있지 않으면 그 배열은 작성할 수 없다.
예를 들어 길이가 10인 배열을 생성하는 경우, 메모리에는 10개의 연속적인 슬롯이 있어야 한다.
(10개의 슬롯이 점점 혹은 떨어져 있으면 안 됨)

또한 요소를 추가한 결과 슬롯이 부족한 경우
필요한만큼 연속적인 슬롯이있는 곳으로 가서 배열을 다시 만듭니다.

· 요소 추가, 삭제가 느림
추가나 삭제가 된 요소로부터, 후의 요소의 인덱스는 모두 수정할 필요가 있다.
따라서 요소의 시작 부분에 추가하거나 삭제하면 모든 요소의 인덱스가 다시 계산됩니다.
정보 처리 기술자 시험의 오전 문제에서 자주 나온 것은

링크 리스트(기본적으로 배열과 반대의 특징을 가진다)

장점

· 목록의 요소는 메모리의 어느 곳에나 배치 가능
배열과 달리 목록에는 다음 요소에 대한 주소가 있습니다.
따라서 다음 요소가 반드시 연속 슬롯에 존재할 필요는 없으며 점등 슬롯에 존재할 수 있습니다.
또한 요소가 추가되어도 목록을 재생성 할 필요가 없습니다.

・요소의 추가, 삭제가 고속
요소의 추가나 삭제가 되어도, 그 이전의 요소가 가지는 다음 요소에의 주소를 수정하는 것만으로 좋다.

단점

· 무작위 값 읽기가 느립니다.
배열과 달리 인덱스를 가지지 않기 때문에, 최초의 요소로부터 읽고 싶은 요소까지 차례로 검색할 필요가 있다.
즉 5번째의 요소를 읽고 싶은 경우, 1 > 2 > 3 > 4 와 다음의 요소의 주소를 쫓아야 한다.
다만 모든 요소를 ​​읽는 경우에는 배열과 성능 차이는 없다.

요약

【배열】
・랜덤한 읽기가 고속. O(1)
· 요소 추가, 삭제가 느립니다. O(N)
・메모리상의 연속한 슬롯이 필요.

【리스트】
· 무작위 읽기가 느립니다. O(N)
・요소의 추가, 삭제가 고속. O(1)
・메모리상에 연속한 슬롯은 필요없고, 요소분의 빈 슬롯이 있으면 좋다.