List, ArrayList, LinkedList

Java에서 List, ArrayList, LinkedList는 모두 데이터를 저장하고 관리하는 데 사용되는 컬렉션 클래스와 인터페이스입니다. 하지만 각각의 구조와 사용 방식, 성능 특성이 다릅니다.

컬렉션 클래스
데이터를 모아놓는 "그릇" 같은 역할을 하는 클래스입니다.
즉 배열처럼 여러 데이터를 한곳에 저장할 수 있지만, 크기가 고정되지 않고 데이터를 쉽게 추가하거나 삭제할 수 있는 것을 말합니다.

인터페이스
인터페이스는 기능만 정의하고 실제 구현은 없습니다.
즉 클래스들이 따라야 할 "규칙" 이나 "약속"을 정의한 것입니다.

List

List 는 인터페이스입니다. 

데이터를 순서대로 저장하며, 중복된 값을 허용합니다. 또한 데이터를 추가하거나 삭제, 검색할 때 사용할 여러 메서드가 정의되어 있습니다. ArrayList, LinkedList 모두 List 인터페이스를 구현합니다.

배열의 크기는 정해져 있기 때문에 자료형의 크기가 가변 하는 상황이라면 List를 사용하는 것이 훨씬 효율적

주요 메서드

add(element) : 데이터를 추가합니다.

get(index) : 특정 위치의 데이터를 가져옵니다.

remove(index) : 특정 위치의 데이터를 삭제합니다.

size() : 리스트의 크기를 반환합니다.

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

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        System.out.println(list.get(0)); // 출력: A
    }
}

ArrayList

ArrayList 는 List 인터페이스를 구현한 클래스로, 배열 기반의 동적 자료구조입니다.

기본 배열과 다르게, 데이터가 추가되면 자동으로 크기가 증가합니다.

데이터를 읽거나 검색하는데 빠르지만 중간에 데이터를 삽입하거나 삭제하는 경우 느립니다. 왜냐하면 배열 요소를 이동해야 하기 때문입니다.

 

ArrayList는 크기가 고정되어 있는 배열을 개선한 자료구조입니다.

내부적으로 데이터를 배열에서 관리하며 데이터의 추가 삭제를 아래와 같이 임시 배열을 생성해 데이터를 복사하는 방법을 사용합니다. 따라서 대량의 자료를 추가 / 삭제하는 경우 그만큼 데이터의 복사가 많이 일어나 성능 저하를 일으킬 수 있습니다.

 

여기서 착각할 수 있는게 기존 배열에 여유 공간이 있을 때에는 기존 배열에 데이터를 바로 추가해 별도의 복사가 발생하지는 않습니다. 위에 예시는 배열의 크기가 꽉 차려고 할 때 배열 크기를 확장하면서 새로운 배열에 데이터를 복사하는 개념입니다.

특징

- 데이터는 연속된 메모리 공간에 저장됩니다.

- 데이터 검색 속도는 빠름(O(1))입니다.

- 데이터 삽입 / 삭제 시, 나머지 요소를 이동해야 하므로 삽입 / 삭제 속도는 느립니다. (O(n))

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>();
        arrayList.add("A");
        arrayList.add("B");
        arrayList.add("C");
        System.out.println(arrayList); // 출력: [A, B, C]
        System.out.println(arrayList.get(0))
        
        arrayList.remove(1); // B 삭제
        System.out.println(arrayList); // 출력: [A, C]
        System.out.println(arrayList.size()); // 출력: 2
    }
}

LinkedList

LinkedList는 List 인터페이스를 구현한 클래스로, 연결 리스트 구조를 사용합니다.

각 데이터는 노드로 저장되며, 노드는 이전 노드와 다음 노드의 참조를 가지고 있습니다.

중간 데이터의 삽입 / 삭제는 빠르지만(O(1)), 데이터 검색 속도는 느립니다.(O(n))

배열도 구조가 간단하고 사용하기 쉬우며, 데이터 조회 시간이 가장 빠르다는 장점을 갖고 있어 LinekedList를 왜 사용해야 하는지 문득 궁금할 수 있지만 기존 배열은 크기를 변경할 수 없으며, 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸리기 때문에 LinkedList라는 자료구조가 만들어졌습니다.

 

특징

- 데이터가 연속적으로 저장되지 않고, 각 노드가 다음 노드를 가리키는 참조(reference)를 가집니다.

- 데이터를 삽입하거나 삭제할 때는 참조만 변경하면 되므로 빠릅니다.

- 데이터를 검색하려면 처음부터 순차적으로 탐색해야 하기 때문에 느립니다.

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        System.out.println(linkedList); // 출력: [A, B, C]

        linkedList.remove(1); // B 삭제
        System.out.println(linkedList); // 출력: [A, C]
    }
}

언제 ArrayList, LinkedList를 사용할까?

 

ArrayList를 사용해야 하는 경우는 데이터의 검색이 빈번한 경우, 데이터 삽입 / 삭제가 리스트의 끝에서 주로 사용하는 경우, 메모리 사용량이 매우 중요한 경우 사용합니다. LinkedList를 사용하는 경우에는 중간에 데이터를 자주 삽입 / 삭제해야 하는 경우나 데이터를 순차적으로 처리하는 경우에 사용하면 좋습니다.

하지만 그럼에도 불구하고..

LinkedList는 잘 사용되지 않습니다.

보통 ArrayList와 LinkedList 중에 어느 걸 사용하면 되냐고 묻지만, 사실 성능면에서 둘은 큰 차이가 없습니다.

 

예를 들어 ArrayList는 리사이징 과정에서 배열 복사하는 추가 시간이 들지만, 배열을 새로 만들고 for 문을 돌려 기존 요소를 일일이 대입하는 그러한 처리가 아니라, 내부적으로 잘 튜닝이 되고 최적화되어있어 우리가 생각하는 것처럼 전혀 느리지가 않습니다.

 

아래의 성능 코드 예시 역시 두각을 나타내기 위해 극단적으로 나노초로 비교해서 차이가 확연히 보여서 그렇지 체감상 차이가 그리 큰 편도 아닙니다.

 

또한 외국 사례를 검색하여 살펴보면 LinkedList를 사용하는 사례보다 그냥 ArrayList를 사용하는 사례가 많은데, 자바의 컬렉션 프레임워크 등 자바 플랫폼의 설계와 구현을 주도한 조슈아 블로치 본인도 자신이 설계했지만 사용하지 않는다고 합니다.

 

실제로 성능 측정을 해도 아래와 같은 결과가 나오는 것을 볼 수 있습니다.