Java Collection - List

#Java #Collection Framework #List #ArrayList #LinkedList #Foundation #ProjectJF

kiio

— 5 min read

자바의 자료구조는 콜렉션 프레임워크로 제공하고 있다. 대표적인 자료 구조로 리스트이며 다음 구조를 갖고 있다.

컬렉션 프레임워크 - 리스트

      +-------------+
      | Collection  |
      +------+------+
             ↑
      +-------------+
      | List        |
      +------+------+
             ↑
      ┌------+-------┐
+-----+-----+ +------+-----+
| ArrayList | | LinkedList |
+-----------+ +------------+
List          LinkedList

컬렉션 인터페이스는?

컬렉션 인터페이스는 java.util 기본 패키지에서 제공하며 컬렉션 프레임워크를 이루고 있는 인터페이스이다.
요약하면 데이터들을 다루기 위한 메소드들이 정의되어 있다. List, Set, Queue 다양한 하위 인터페이스와 함께 사용되고, 데이터를 리스트, 세트, 큐 등의 형태로 관리할 수 있다.

  • 자료 구조를 다루는 공통 기능으로 이루어짐

리스트 인터페이스는?

리스트 인터페이스는 마찬가지로 java.util 패키지의 컬렉션 프레임워크 중 하나이다. 리스트는 객체들의 순서가 있는 컬렉션이며 같은 객체의 중복 저장한다. 리스트는 배열과 비슷하나, 크기가 동적으로 변화하며 컬렉션을 다룰 때는 유연하게 사용할 수 있도록 한다.

리스트 인터페이스는 ArrayList, LinkedList와 같은 여러 구현의 클래스를 가지고 있으며 리스트 인터페이스로서 메소드를 구현한다.

List 인터페이스 지원 메소드

  • add(E e)
    • 리스트의 끝부분에 요소를 추가한다.
  • add(int index, E element)
    • 리스트의 지정된 위치로 요소를 삽입한다.
  • addAll(Collection<? extends E> c)
    • 지정한 컬렉션의 모든 요소를 리스트의 끝에 추가한다.
  • addAll(int index, Collection<? extends E> c)
    • 지정한 컬렉션의 모든 요소를 리스트의 지정한 위치로 추가한다.
  • get(int index)
    • 리스트의 지정한 위치의 요소를 반환한다.
  • set(int index, E element)
    • 지정한 위치 요소를 변경하며, 변경 전 요소를 반환한다.
  • remove(int index)
    • 리스트에서 지정한 요소를 제거하고 그 요소를 반환한다.
  • remove(Object o)
    • 리스트에서 지정한 값의 첫 번째 요소를 제거한다.
  • clear()
    • 리스트에서 모든 요소 제거
  • indexOf(Object o)
    • 리스트에서 지정된 요소의 첫 번째 인덱스를 반환한다.
  • lastIndexOf(Object o)
    • 리스트에서 지정한 요소의 마지막 인덱스를 반환한다.
  • contains(Object o)
    • 리스트에 지정한 요소를 포함하고 있는지 유무를 반환한다.
  • sort(Comparator<? super E> c)
    • 리스트의 요소를 지정한 비교자(Comparator) 따라서 정렬한다.
    • Comprarator의 하위를 받지 않도록 하위 파라미터를 제한을 걸었다.
  • subList(int fromIndex, int toIndex)
    • 리스트의 일부분의 뷰를 반환한다.
  • size()
    • 리스트의 요소 갯수를 반환한다.
  • isEmpty()
    • 리스트가 비었는지 유무를 반환한다.
  • iterator()
    • 리스트의 요소에 대한 반복자만큼 반환한다.
  • toArray()
    • 리스트의 모든 요소를 배열로 반환한다.
  • toArray(T[] a)
    • 리스트의 모든 요소를 지정한 배열로 반환한다.

ArrayList

java.util.ArrayList

자바가 제공하는 ArrayList 는 우리가 만든 CList와 비슷하며 특징은 다음과 같이 있다.

자바 ArrayList 특징

  • 배열을 사용해 데이터를 관리
  • DEFAULT_CAPACITY = 10, 기본 CAPACITY 값이 10이다.
    • CAPACITY 넘어갈 경우 50% 씩 증가한다. (10, 15, 22, 33, 49 증감)
  • 메모리 고속 복사 연산 사용
    • ArrayList 중간에 위치에 데이터 추가 시 모든 데이터를 한 칸씩 이동한다.
    • 자바가 제공하는 ArrayList 이 부분을 최적화 용도로 배열의 요소 이동은 시스템 레벨에서나 최적화된 메모리 고속 복사 연산을 사용해 빠르게 수행한다. (System.arraycopy())

데이터 추가 - 메모리 고속 복사 연산

1. 화살표 a 위치에 데이터 d 추가
+---+---+---+---+---+
| a | b | c |   |   |
+---+---+---+---+---+
  ↑ 

2. 배열 데이터 통채로 이동
+---+---+---+
| a | b | c |
+---+---+---+
  |
  └---┐
      ↓
+---+---+---+---+---+
|   | a | b | c |   |
+---+---+---+---+---+

3. 데이터 삽입
+---+---+---+---+---+
| d | a | b | c |   |
+---+---+---+---+---+
  • 시스템 레벨의 배열을 빠르게 복사한다. OS 하드웨어에 따라 성능이 다르므로 정확한 측정이 되지 않지만, 한 칸씩 이동하는 것보다는 몇 배나 빠른 성능을 자랑한다.

메모리 고속 복사가 빠르더라도 데이터 너무 많으면 병목이 언젠가는 생긴다.

LinkedList

자바도 연결리스트를 지원한다. 이전에 만든 단일 연결리스트 CLinkedList 구조가 비슷하나 몇 가지 다르다.

LinkedList 특징

  • 이중 연결 리스트
  • 첫 번째 노드가 마지막 노드를 참조함

단일리스트와 연결리스트의 차이점

  • 이중 연결 리스트는 다음 노드 뿐 아니라 이전 노드로 이동할 수 있는 prev 변수가 있다. (node.next, node.prev)
  • 마지막 노드 참조로 마지막에 추가한 경우에도 O(1) 성능을 제공한다.
  • 검색에는 이전 노드를 이용해 역방향으로 조회가 된다.
    • 인덱스 조회 성능이 최적화 가능
    • 인덱스 조회시 사이즈 값의 절반 이하라면 처음부터 찾고, 인덱스가 사이즈 값보다 절반 이상이면 역방향으로 조회한다.

LinkedList 클래스

class Node {
    E item;
    Node next;
    Node prev;
}

class LinkedList {
    Node first; // 첫 번째 노드 참조
    Node last; // 마지막 노드 참조
    int size;
}

더 읽어볼 내용