ArrayList vs LinkedList차이?

ArrayList

상속관계

• java.lang.Object
  • java.util.AbstractCollection<>
    • java.util.AbstractList<>
      • java.util.ArrayList<>

특징

• 중복을 허용
• 순서를 유지하며 배열의 형태로 관리
• ArrayList는 클래스이며 배열을 추가 삭제하는 메소드가 존재
• 정적인 배열과는 달리 더많은 요소가 ArrayList에 추가되면 동적으로 증가한다.
• 타입 안정성을 보장하는 제네릭 사용 가능
• random access 가능

따로 지정을 하지 않는 경우 배열의 크기가 10으로 지정되어 있다.

ArrayList로 초기 용량을 따로 설정하는 것이 효율적

• 초기 배열의 크기는 10으로 지정되어있는데 작은 규모의 프로젝트에서는 티가 안나더라도
  많은 요소가 추가되고 삭제되면 여러번의 배열이 복사가 일어난다.
  그러므로 대략적으로 초기 용량을 생각하여 여유있게 초기 용량을 설정해주는 것이 도움이 된다.

get

조회를 할때는 index에 위치한 원소를 한번에 검색이 가능

• 배열의 index를 통해 접근하는 방식이기 때문에 시간복잡도 O(1)을 갖는다.

add

add(E e)

• 배열의 가장 끝에 데이터를 담는다.
  • 맨 끝에 담는 것에 한하여 시간복잡도 O(1)을 가진다.

add(int index, E e)

• 지정된 위치에 있는 기존 데이터들은 위치가 하나씩 뒤로 밀려난다.
  • 매번 한칸씩 미뤄서 공간을 만드는 작업이 필요하기 때문에 느리다.
    • 인덱스를 찾는 시간(O(1))과 + 공간을 만드는 작업(O(n)) => O(N) 시간 복잡도를 가진다.

remove

remove는 add와 비슷한데 add는 뒤로 하나씩 밀리지만 remove는 앞으로 한 칸씩 당겨진다.
그러므로 O(n)의 시간 복잡도를 가진다.

LinkedList

상속관계

• java.lang.Object
  • java.util.AbstractCollection<>
    • java.util.AbstractList<>
      • java.util.AbstractSequentialList<>
        • java.util.ArrayList<>

구조

LinkedList는 이중 연결 리스트의 형태

get

연결 리스트 형태를 띄고 있기 때문에 해당하는 index에 대한 값을 얻어올 때 시작이나 끝에서부터 해당 index까지 순차적으로 접근하여 값을 가져옴

• 그러므로 시간 복잡도는 O(n)을 가진다.

add

index에 도달할 때까지 순차 접근을 하는 시간 O(n) + 노드끼리 연결하는 시간 O(1) => O(n)

시작과 끝에 요소를 추가할 때

head와 tail을 갖기 때문에 시작과 끝을 찾는 시간은 O(1)을 갖는다.

remove

add메소드와 비슷

정리

일반적으로 get을 자주 사용한다면 ArrayList
삽입 삭제가 잦다면 LinkedList