Array

선언할 때 초기값을 반드시 지정해줘야하는 데이터 묶음이다.
모든 원소가 메모리주소상에서 연속적으로 저장되어 효율적이고 집약적이다. 대신, 길이가 고정되어 있고 삽입, 삭제에서 불리하다. > O(n)

List

List는 자바를 기준으로 인터페이스다.
그리고 이 인터페이스 안에 LinkedList와 ArrayList 같은 클래스들이 구현되어 있는 셈이다.

LinkedList

LinkedList는 동적으로 크기가 변할 수 있는 데이터 묶음으로, 정확히는 새로운 값이 추가될 때 그 친구의 주소를 이전 친구에게 알려주는 개념이다. 이렇게 되면 첫번째 친구부터 값을 읽은 후 다음 친구가 어디에 있는지 주소를 찾은 다음 해당 주소로 가서 다음 친구의 값을 읽고 이렇게 건너건너 값을 저장하고 읽는 방식이다.

특정 index의 값을 찾을 때는 O(n)으로 매우 불리하고, 삽입, 삭제 연산은 O(1)로 매우 유리하다.

ArrayList

ArrayList는 동적으로 크기가 변할 수 있는 데이터 묶음으로, LinkedList와 같이 동적이지만 내부구조가 전혀 다르다. 이름을 보면 알 수 있다싶이 ArrayList는 Array로 구성되어 있다. 이때 새로운 값이 추가될 때 현재 Array의 크기를 넘어서면 1.5배 더 큰 Array를 새롭게 할당받고 그 Array에 기존 값들을 복사해서 가져와서 크기를 늘리는 방식이다.

파이썬의 List는 ArrayList와 같은 방식으로 구현되어 있다. 또한, LinkedList의 경우에는 파이썬에서 쉽게 쓰고 싶다면 이중연결리스트인 Deque(덱)을 쓸 수 있다.