[Java 복습] 자바 리스트의 모든 것

목차

• 자바 리스트
• Collection 인터페이스
• List 인터페이스
• ArrayList
• LinkedList
• List 성능 비교

 

자바 리스트

 

List 자료 구조
순서가 있고, 중복을 허용하는 자료 구조를 리스트라 한다. 

자바의 컬렉션 프레임워크가 제공하는 가장 대표적인 자료구조가 바로 리스트이다. 

리스트와 관련된 컬렉션 프레임워크는 다음 구조를 가진다.

 

 

Collection 인터페이스

Collection 인터페이스는 java.util 패키지의 컬렉션 프레임워크의 핵심 인터페이스 중 하나이다. 

이 인터페이스는 자바에서 다양한 컬렉션, 즉 데이터 그룹을 다루기 위한 메서드를 정의한다. 

Collection 인터페이스는 List , Set , Queue 와 같은 다양한 하위 인터페이스와 함께 사용되며,

이를 통해 데이터를 리스트, 세트, 큐 등의 형태로 관리할 수 있다. 

 

List 인터페이스

List 인터페이스는 java.util 패키지에 있는 컬렉션 프레임워크의 일부다. 

List 는 객체들의 순서가 있는 컬렉션을 나타내며, 같은 객체의 중복 저장을 허용한다. 

이 리스트는 배열과 비슷하지만, 크기가 동적으로 변화하는 컬렉션을 다룰 때 유연하게 사용할 수 있다.

List 인터페이스는 ArrayList , LinkedList 와 같은 여러 구현 클래스를 가지고 있으며,

각 클래스는 List 인터페이스의 메서드를 구현한다.

 

 

자바 ArrayList

java.util.ArrayList
자바가 제공하는 ArrayList 는 우리가 직접 만든 MyArrayList 와 거의 비슷하다. 

 

자바 ArrayList의 특징

• 배열을 사용해서 데이터를 관리한다.
• 기본 CAPACITY 는 10이다.( DEFAULT_CAPACITY = 10 )
  
  • CAPACITY 를 넘어가면 배열을 50% 증가한다.
  • 10 => 15 => 22 => 33 => 49로 증가한다. (최적화는 자바 버전에 따라 달라질 수 있다.)
• 메모리 고속 복사 연산을 사용한다.
  
  • ArrayList 의 중간 위치에 데이터를 추가하면, 추가할 위치 이후의 모든 요소를 한 칸씩 뒤로 이동시켜야 한다.
  • 자바가 제공하는 ArrayList 는 이 부분을 최적화 하는데, 배열의 요소 이동은 시스템 레벨에서 최적화된 메모리 고속 복사 연산을 사용해서 비교적 빠르게 수행된다. 참고로 System.arraycopy() 를 사용한다.

 

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

 

시스템 레벨에서 배열을 한 번에 아주 빠르게 복사한다. 

이 부분은 OS, 하드웨어에 따라 성능이 다르기 때문에 정확한 측정이 어렵지만, 

한 칸씩 이동하는 방식과 비교하면 보통 수 배 이상의 빠른 성능을 제공한다.

 

 

 

자바 LinkedList

java.util.LinkedList

자바가 제공하는 LinkedList 는 우리가 직접 만든 MyLinkedList 와 거의 비슷하다. 

우리가 직접 만든 MyLinkedList 의 노드는 다음 노드로만 이동할 수 있는 단일 연결 구조다. 

 

자바의 LinkedList 특징

• 이중 연결 리스트 구조
• 첫 번째 노드와 마지막 노드 둘다 참조

 

• 자바가 제공하는 LinkedList 는 이중 연결 구조를 사용한다. 
• 이 구조는 다음 노드 뿐만 아니라 이전 노드로도 이동할 수 있다.
  • 예) node.next 를 호출하면 다음 노드로, node.prev 를 호출하면 이전 노드로 이동한다.
• 마지막 노드에 대한 참조를 제공한다. 따라서 데이터를 마지막에 추가하는 경우에도 O(1)의 성능을 제공한다.
• 이전 노드로 이동할 수 있기 때문에 마지막 노드부터 앞으로, 그러니까 역방향으로 조회할 수 있다.
  
  • 덕분에 인덱스 조회 성능을 최적화 할 수 있다.
  • 예를 들어 인덱스로 조회하는 경우 인덱스가 사이즈의 절반 이하라면 처음부터 찾아서 올라가고, 인덱스가 사이즈의 절반을 넘으면 마지막 노드 부터 역방향으로 조회해서 성능을 최적화 할 수 있다.

자바의 LinkedList 클래스

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

 

 

 

자바 리스트의 성능 비교

public class JavaListPerformanceTest {

    public static void main(String[] args) {

        int size = 50000;
        System.out.println("== ArrayList 추가 ==");
        addFirst(new ArrayList<>(), size);
        addMid(new ArrayList<>(), size); // 찾는데 O(1), 데이터 추가(밀기) O(n)
        ArrayList<Integer> arrayList = new ArrayList<>(); // 조회용 데이터로 사용
        addLast(arrayList, size); // 찾는데 O(1), 데이터 추가(밀기) O(1)

        int loop = 10000;
        System.out.println("== ArrayList 조회 ==");
        getIndex(arrayList, loop, 0);
        getIndex(arrayList, loop, size / 2);
        getIndex(arrayList, loop, size - 1);

        System.out.println("== MyArrayList 검색 ==");
        search(arrayList, loop, 0);
        search(arrayList, loop, size / 2);
        search(arrayList, loop, size - 1);

        System.out.println("== MyLinkedList 추가 ==");
        addFirst(new LinkedList<>(), size);
        addMid(new LinkedList<>(), size); // 찾는데 O(n), 데이터 추가 O(1)
        LinkedList<Integer> linkedList = new LinkedList<>(); // 조회용 데이터로 사용
        addLast(linkedList, size); // 찾는데 O(n), 데이터 추가 O(1)

        System.out.println("== MyLinkedList 조회 ==");
        getIndex(linkedList, loop, 0);
        getIndex(linkedList, loop, size / 2);
        getIndex(linkedList, loop, size - 1);

        System.out.println("== MyLinkedList 검색 ==");
        search(linkedList, loop, 0);
        search(linkedList, loop, size / 2);
        search(linkedList, loop, size - 1);
    }

    private static void addFirst(List<Integer> list, int size) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(0, i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("앞에 추가 - 크기: " + size + "계산 시간: " + (endTime - startTime) + " ms");
    }

    private static void addMid(List<Integer> list, int size) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i / 2, i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("평균 추가 - 크기: " + size + "계산 시간: " + (endTime - startTime) + " ms");
    }

    private static void addLast(List<Integer> list, int size) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("평균 추가 - 크기: " + size + "계산 시간: " + (endTime - startTime) + " ms");
    }
    private static void getIndex(List<Integer> list, int loop, int index) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < loop; i++) {
            list.get(index);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("index: " + index + ", 반복: " + loop + ", 계산 시간: " + (endTime - startTime) + " ms");
    }

    private static void search(List<Integer> list, int loop, int findValue) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < loop; i++) {
            list.indexOf(findValue);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("findValue: " + findValue + ", 반복: " + loop + ", 계산 시간: " + (endTime - startTime) + "ms");    
    }
}

==ArrayList 추가==
앞에 추가 - 크기: 50000, 계산 시간: 106ms
평균 추가 - 크기: 50000, 계산 시간: 49ms
뒤에 추가 - 크기: 50000, 계산 시간: 1ms

==LinkedList 추가==
앞에 추가 - 크기: 50000, 계산 시간: 2ms
평균 추가 - 크기: 50000, 계산 시간: 1116ms
뒤에 추가 - 크기: 50000, 계산 시간: 2ms

==ArrayList 조회==
index: 0, 반복: 10000, 계산 시간: 1ms
index: 25000, 반복: 10000, 계산 시간: 0ms
index: 49999, 반복: 10000, 계산 시간: 1ms

==LinkedList 조회==
index: 0, 반복: 10000, 계산 시간: 0ms
index: 25000, 반복: 10000, 계산 시간: 439ms
index: 49999, 반복: 10000, 계산 시간: 1ms

==ArrayList 검색==
findValue: 0, 반복: 10000, 계산 시간: 0ms
findValue: 25000, 반복: 10000, 계산 시간: 104ms
findValue: 49999, 반복: 10000, 계산 시간: 218ms

==LinkedList 검색==findValue: 0, 반복: 10000, 계산 시간: 1ms
findValue: 25000, 반복: 10000, 계산 시간: 473ms
findValue: 49999, 반복: 10000, 계산 시간: 945ms

 

데이터를 추가할 때 자바 ArrayList가 직접 구현한 MyArrayList보다 빠른 이유

자바의 배열 리스트는 이때 메모리 고속 복사를 사용하기 때문에 성능이 최적화된다.
메모리 고속 복사는 시스템에 따라 성능이 다르기 때문에 정확한 계산은 어렵지만 대략 O(n/10) 정도로 추정하자. 

상수를 제거하면 O(n)이 된다. 하지만 메모리 고속 복사라도 데이터가 아주 많으면 느려진다.

 

 

 

시간 복잡도와 실제 성능

• 이론적으로 LinkedList 의 중간 삽입 연산은 ArrayList 보다 빠를 수 있다.
• 그러나 실제 성능은 요소의 순차적 접근 속도, 메모리 할당 및 해제 비용, CPU 캐시 활용도 등 다양한 요소에 의해 영향을 받는다.
  • 추가로 ArrayList 는 데이터를 한 칸씩 직접 이동하지 않고, 대신에 메모리 고속 복사를 사용한다.
• ArrayList 는 요소들이 메모리 상에서 연속적으로 위치하여 CPU 캐시 효율이 좋고, 메모리 접근 속도가 빠르다.
• 반면, LinkedList 는 각 요소가 별도의 객체로 존재하고 다음 요소의 참조를 저장하기 때문에 CPU 캐시 효율이 떨어지고, 메모리 접근 속도가 상대적으로 느려질 수 있다
• ArrayList 의 경우 CAPACITY 를 넘어서면 배열을 다시 만들고 복사하는 과정이 추가된다. 하지만 한번에 50%씩 늘어나기 때문에 이 과정은 가끔 발생하므로, 전체 성능에 큰 영향을 주지는 않는다.

이론적으로 LinkedList 가 중간 삽입에 있어 더 효율적일 수 있지만, 현대 컴퓨터 시스템의 메모리 접근 패턴, CPU 캐시 최적화, 메모리 고속 복사 등을 고려할 때 ArrayList 가 실제 사용 환경에서 더 나은 성능을 보여주는 경우가 많다.

 

 

배열 리스트 vs 연결 리스트
대부분의 경우 배열 리스트가 성능상 유리하다. 이런 이유로 실무에서는 주로 배열 리스트를 기본으로 사용한다.
만약 데이터를 앞쪽에서 자주 추가하거나 삭제할 일이 있다면 연결 리스트를 고려하자.