Array vs. ArrayList vs. LinkedList

한 문장으로 비교하기

• Array
  선언할 때 크기 지정해야 하며, 데이터의 삽입 및 삭제가 비효율적이지만 Index로 빠르게 값을 찾을 수 있음

• ArrayList
  선언할 때 크기 지정하지 않아도 되는 데다가, Index로 빠르게 값을 찾을 수 있지만, 데이터의 삽입 및 삭제가 상대적으로 느림

• LinkedList
  선언할 때 크기 지정하지 않아도 되는 데다가, 데이터의 삽입 및 삭제가 상대적으로 빠르지만 검색이 상대적으로 느림

자료구조별 상세 비교

ArrayList

철길로 비유할 수 있다.

• default capacity 10으로 지정됨. 초과될 때마다 더 큰 저장공간에 새로 저장한다.
• 자동으로 resize된다. 기본적으로 두 배씩 늘어난다.
• 대량의 자료를 추가/삭제하는 경우에는 그만큼 데이터의 복사가 많이 일어나게 되어 성능 저하를 일으킬 수 있다. 반면, 각 데이터는 인덱스를 가지고 있기 때문에 한 번에 참조가 가능해 데이터의 검색에는 유리한 구현체이다.
• 빅오 표기법(Big-O notation) 관점에서 검색에는 O-(1)이지만, 리스트 중간에 데이터를 삽입 및 삭제를 하려면 O-(N)만큼(최악의 경우) 걸린다.
• 대부분의 일반연산은 ArrayList가 수월하다.

LinkedList

진주목걸이로 비유할 수 있다.

• 내부에 노드가 따로 저장되어 있다.

• ArrayList와 반대로, 조회성능은 O-(N) 일일이 하나하나씩 찾아야 한다.

• 리스트 중간에 데이터를 삽입 및 삭제하는 경우 O-(N)
  (왜 O-(1))이 아니냐면 중간 노드를 찾는 과정이 필요하기 때문이다.)

• deck, queue이 LinkedList로 구현된다.

이미지 출처 : "ArrayList vs LinkedList in Java
", scaler.com, 2021년 9월 20일 수정, 2024년 1월 19일 접속, https://www.scaler.com/topics/arraylist-vs-linkedlist/