ArrayList vs LinkedList

ArrayList

• List + Array의 자료 구조
• 크기가 가변적인 배열이라고 생각하는 것이 편하다.
• 실제 내부도 배열로 구현
• 데이터 접근 및 변경시 성능이 좋음 (o(1))
• 데이터를 추가하거나 삭제하는 경우 시간 복잡도는 o(N)
  • 그 이유는 배열의 시간복잡도와 동일 (데이터를 밀거나 땡겨야하기에..)
  • 맨 긑에 추가하는 경우는 O(1) 이다. 하나만 추가하면 되니까!
• 실제 내부도 배열로 이루어져있기에 빈 엘리먼트의 허용이 가능하다.

LinkedList

• 양방향의 연결로 구현한 리스트
• Data 접근시에 속도가 느리다. (o(N))
• Data 삽입, 삭제시에 연결에서 참조하는 주소 값만 변경하면 된다. 이는 ArrayList와 비교했을 때 효율적이라고 할 수 있다.
• 그래도 시간 복잡도는 O(N)이 소요된다.
• 양방향의 연결로 이루어졌기에 빈 엘리먼트를 허용하지 않는다.