배열 리스트 장단점 (Array vs List : 선형리스트 연결리스트)

순차리스트 (배열, Array)
물리적주소와 논리적 주소가 일치한다.
장점:
*배열을 사용하므로 원하는 인덱스에 빠르게 접근이 가능하다.
★메모리를 연속적으로 배정 받기 때문에 기억장소 이용효율은 밀도가1이기 떄문에 가장 좋다.
★구현이 쉽다.
★참조를 위한 추가적인 메모리 할당이 필요없다.
단점:
*크기가 정해져 있기 때문에 데이터를 적게 보관하면 메모리 낭비가 일어난다.
*삽입,삭제시 물리적,논리적 순서를 맞춰주어야 하기 때문에 원소가 많거나 삭제,삽입이 많은경우 성능이 별로다.
*배열을 사용하기 때문에 배열의 취약점을 그대로 갖는다.
★중간에 자료를 삽입하기 위에서는 뒤에 빈공간이 있어야한다.
★데이터를 삭제해도 그 공간은 남아있기 떄문에 용량을 차지한다.


연결리스트 (List, Linked List)
장점:
*포인터를 사용하기 때문에 삽입 삭제 연산이 순차리스트 보다 빠르다.
★삽입과 삭제가 간단하다.
*데이터가 추가되거나 삭제될 때마다 노드를 연결시키거나 삭제하면 되므로 메모리 효율이 좋고 크기 제한이 없다.
★오버헤드가 발생하지 않는다.
단점:
*포인터를 사용하기 때문에 특정 인덱스 접근시 맨처음 노드부터 해당 노드까지 탐색해야 하기 떄문에 접근속도가 느리다.
*중간에 노드가 끊기는 일이 발생할 시 다음 요소로 접근이 불가능하다.
★연결을 위한 링크부분이 필요하기 때문에 순차리스트보다 메모리 이용 효율이 좋지않다.
★물리적으로 인접한 메모리에 위치해 있지 않다.
★배열에 비해서 구현이 복잡하다.