Array

Array는 index값을 통한 원소 접근이 용이하고 구현이 쉽다. 논리적 순서와 물리적 순서가 일치한다.
단점으로는 삽입/삭제 등에 대한 연산에 필요한 Cost가 높다.

LinkedList

List는 배열의 삽입/삭제 연산에 대한 비효율성을 극복하고자 등장했다.
List는 Array와 다르게 물리적으로 순서대로 되어있지 않다.
대신 각 원소가 다음 index 위치에 해당하는 물리 주소를 가지고 있다.
그렇기에 삽입/삭제 시 데이터를 shift 할 필요 없이 해당 원소의 물리적 주소만 변경해주면 된다.
하지만 index를 참조하려면 1번 index부터 차례대로 접근해야 한다는 비효율성이 있다.(파이썬의 list를 처음 사용할때 느낌.)