[JAVA] List 객체 정리

List interface 하위 Class

1. Vector (deprecated)
   
   1. Stack
2. ArrayList
3. LinkedList

 

주의사항

Stack은 Vector를 상속받은 불필요한 로직만 추가된 클래스이고(책피셜)

Vector는 deprecated 된 삭제 예정 클래스이다.

실제 사용할 수 있는 클래스는 LinkedList와 ArrayList 두 개라고 생각하면 된다.

 

ArrayList

고정 크기의 Array를 기반으로 구현되는 List Class이다.

 

LinkedList

Doubly Linked List(양방향 연결 리스트)로 구현되는 동적 증가가 가능한 List Class이다.

 

ArrayList vs. LinkedList

데이터 접근/수정 패턴에 따라 사용해야 할 Class를 정해야 한다.

• element add 비용
  • list end node에서의 add
    • ArrayList는 element의 수가 공간의 크기보다 커지면, 새로운 Array 생성을 위한 공간 할당 비용이 추가로 발생한다.
    • LinkedList는 end node에 new node의 reference를 추가하기 때문에, O(1)의 고정 비용만 발생한다.
  • 중간 index에서의 add
    • ArrayList는 해당 index 기준 우측의 element들을 모두 한 칸씩 이동시켜야 한다.
    • LinkedList는 삽입 지점으로의 node 탐색 비용 O(n)이 발생한다. 대신 양쪽 node의 reference를 해제한 후 new element에 재등록하는 O(2)의 비용이 발생한다.

* element 삭제에도 동일한 비용이 발생한다.

 

결론

List의 Random index 조회가 빈번할 경우, 조회 비용 O(1)을 보장하는 ArrayList가 유리하다.

순차 조회 혹은 List element 삭제/추가가 빈번할 경우 LinkedList가 유리하다.

 

확인 필요 사항

LinkedList의 순환을 하면서 element 조회를 할 때

LinkedList의 각 element 조회 비용 O(n)이 필요한지, 아니면 순환 동작을 통한 O(1)로 가능한지는 확인이 필요하다.