5-2. 자바 리스트(java.util)

📜 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와 거의 비슷함

자바의 LinkedList 특징

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

단일 연결 리스트

• 우리가 직접 만든 MyLinkedList의 노드는 다음 노드로만 이동할 수 있는 단일 연결 구조
• 따라서 이전 노드로 이동할 수 없다는 단점이 있음

이중 연결 리스트

• 자바가 제공하는 LinkedList는 이중 연결 구조를 사용함

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

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

• 이 구조는 다음 노드 뿐만 아니라 이전 노드로도 이동할 수 있음

  • 예) node.next를 호출하면 다음 노드로, node.prev를 호출하면 이전 노드로 이동함

• 마지막 노드에 대한 참조를 제공함

  • 따라서 데이터를 마지막에 추가하는 경우에도 O(1)의 성능을 제공함

• 이전 노드로 이동할 수 있기 때문에 마지막 노드부터 앞으로, 즉 역방향으로 조회할 수 있음

  • 인덱스 조회 성능을 최적화할 수 있게됨
  • 예를 들어 인덱스로 조회하는 경우 인덱스가 사이즈의 절반 이하라면 처음부터 찾아서 올라가고, 인덱스가 사이즈의 절반을 넘으면 마지막 노드부터 역방향으로 조회하여 성능을 최적화할 수 있음

자바 리스트의 성능 비교

package collection.list;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class JavaListPerformanceTest {

    public static void main(String[] args) {
        int size = 50_000;
        System.out.println("==ArrayList 추가==");
        addFirst(new ArrayList<>(), size);
        addMid(new ArrayList<>(), size);
        ArrayList<Integer> arrayList = new ArrayList<>(); //조회용 데이터로 사용
        addLast(arrayList, size);
        
        System.out.println("==LinkedList 추가==");
        addFirst(new LinkedList<>(), size);
        addMid(new LinkedList<>(), size);
        LinkedList<Integer> linkedList = new LinkedList<>(); //조회용 데이터로 사용
        addLast(linkedList, size);
        
        int loop = 10000;
        System.out.println("==ArrayList 조회==");
        getIndex(arrayList, loop, 0);
        getIndex(arrayList, loop, size / 2);
        getIndex(arrayList, loop, size - 1);
        
        System.out.println("==LinkedList 조회==");
        getIndex(linkedList, loop, 0);
        getIndex(linkedList, loop, size / 2);
		getIndex(linkedList, loop, size - 1);

 		System.out.println("==ArrayList 검색==");
		search(arrayList, loop, 0);
 		search(arrayList, loop, size / 2);
 		search(arrayList, loop, size - 1);
 
 		System.out.println("==LinkedList 검색==");
 		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는 요소들이 메모리 상에서 연속적으로 위치하여 CPU 캐시 효율이 좋고, 메모리 접근 속도가 빠름

• 반면에 LinkedList는 각 요소가 별도의 객체로 존재하고 다음 요소의 참조를 저장하기 때문에 CPU 캐시 효율이 떨어지고, 메모리 접근 속도가 상대적으로 느려질 수 있음

• ArrayList의 경우 CAPACITY를 넘어서면 배열을 다시 만들고 복사하는 과정이 추가됨

  • 하지만 한 번에 50%씩 늘어나기 때문에 이 과정은 가끔 발생하므로, 전체 성능에 큰 영향을 주지는 않음

결론

---

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

배열 리스트 vs 연결 리스트

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

강의 출처 : 김영한의 실전 자바 - 중급 2편