Programming Language/Java

[Java] 29. 컬렉션- ArrayList, LinkedList, List

lumana 2025. 1. 19. 17:26

컬렉션- ArrayList, LinkedList, List

#Java

C 스타일 배열

데이터 조회

배열의 인덱스 사용: O(1)
배열의 순차 검색: O(n)

데이터 추가

배열의 첫번째 위치에 추가
- 배열의 첫번째 위치를 찾는데는 인덱스를 사용하므로 O(1)이 걸린다.
- 모든 데이터를 배열의 크기만큼 한 칸씩 이동해야 한다. 따라서 O(n) 만큼의 연산이 걸린다.
- O(1 + n) O(n)이 된다.
배열의 중간 위치에 추가
- 배열의 위치를 찾는데는 O(1)이 걸린다.
- index의 오른쪽에 있는 데이터를 모두 한 칸씩 이동해야 한다. 따라서 평균 연산은 O(n/2)이 된다.
- O(1 + n/2) O(n)이 된다.
배열의 마지막 위치에 추가
- 이 경우 배열이 이동하지 않고 배열의 길이를 사용하면 마지막 인덱스에 바로 접근할 수 있으므로 한번의 계산으로 위치를 찾을 수 있고, 기존 배열을 이동하지 않으므로 O(1)이 된다.

private static void addLast(int[] arr, int newValue) {
	arr[arr.length - 1] = newValue;
}
private static void addFirst(int[] arr, int newValue) {
	for (int i = arr.length - 1; i > 0; i--) {
		arr[i] = arr[i - 1];
	}
	arr[0] = newValue;
}
private static void addAtIndex(int[] arr, int index, int newValue) {
	for (int i = arr.length - 1; i > index; i--) {
		arr[i] = arr[i - 1];
	}
	arr[index] = newValue;
}

배열의 한계
배열의 크기를 배열을 생성하는 시점에 미리 정해야 한다. 미리 정해둔 배열의 크기 이상의 데이터를 저장하려고 하면 문제가 발생하게 된다.

배열처럼 처음부터 정적으로 길이가 정해져있는 것이 아니라, 동적으로 언제든지 길이를 늘리고 줄일 수 있는 자료 구조를 설계해보자.

배열 리스트 - 직접 구현

배열의 경우 다음 2가지 불편함이 있다.

배열의 길이를 동적으로 변경할 수 없다.
데이터를 추가하기 불편하다. (데이터 이동 필연적)

배열의 이런 불편함을 해소하고 동적으로 데이터를 추가할 수 있는 자료 구조를 List(리스트)라 한다.

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

일반적으로 배열과 리스트는 구분해서 이야기한다. 리스트는 배열보다 유연한 자료 구조로, 크기가 동적으로 변할 수 있다.

배열: 순서가 있고 중복을 허용하지만 크기가 정적으로 고정된다.
리스트: 순서가 있고 중복을 허용하지만 크기가 동적으로 변할 수 있다.

List 자료 구조를 직접 구현하는 과정은 생략! 최종적으로 완성된 코드만 작성하겠습니다.
(자료구조에 대한 자세한 내용은 자료구조 카테고리의 게시글을 참고해주세요. C 언어 기반으로 정리되어 있긴 하지만, 자료구조를 공부할 때는 C 기반으로 공부하는게 좋다고 생각합니다)

package collection.array;

import java.util.Arrays;

public class MyArrayListV4<E> {
    private static final int DEFAULT_CAPACITY = 5;

    private Object[] elementData;
    private int size = 0;

    public MyArrayListV4() {
        elementData = new Object[DEFAULT_CAPACITY];
    }

    public MyArrayListV4(int initialCapacity) {
        elementData = new Object[initialCapacity];
    }

    public int size() {
        return size;
    }

    public void add(E e) {
        if (size == elementData.length) {
            grow();
        }
        elementData[size] = e;
        size++;
    }

    public void add(int index, E e) {
        if (size == elementData.length) {
            grow();
        }
        shiftRightFrom(index);
        elementData[size] = e;
        size++;
    }

    private void shiftRightFrom(int index) {
        for (int i = size; i > index; i--) {
            elementData[i] = elementData[i - 1];
        }
    }

    @SuppressWarnings("unchecked")
    public E get(int index) {
        return (E) elementData[index];
    }

    public E set(int index, E element) {
        E oldValue = get(index);
        elementData[index] = element;
        return oldValue;
    }

    public E remove(int index) {
        E oldValue = get(index);
        shiftLeftFrom(index);

        size--;
        elementData[size] = null;
        return oldValue;
    }

    private void shiftLeftFrom(int index) {
        for (int i = index; i < size - 1; i++) {
            elementData[i] = elementData[i + 1];
        }
    }

    public int indexOf(E o) {
        for (int i = 0; i < size; i++) {
            if (o.equals(elementData[i])) {
                return i;
            }
        }
        return -1;
    }

    private void grow() {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity * 2;
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    @Override
    public String toString() {
        return Arrays.toString(Arrays.copyOf(elementData, size)) + 
		" size=" + size + ", capacity=" + elementData.length;
    }
}

Object 배열을 사용한 이유
Object[] elementData 을 그대로 사용하는 이유

제네릭은 런타임에 이레이저에 의해 타입 정보가 사라진다. 따라서 런타임에 타입 정보가 필요한 생성자에 사용할 수 없다. 따라서 제네릭을 기반으로 배열을 생성하는 다음 코드는 작동하지 않고, 컴파일 오류가 발생한다. 참고로 이것은 자바가 제공하는 제네릭의 한계이다.
- new E[DEFAULT_CAPACITY]
대신에 다음과 같이 모든 데이터를 담을 수 있는 Object 를 그대로 사용해야 한다.
- new Object[DEFAULT_CAPACITY]

MyArrayList의 단점
배열을 사용한 리스트인 MyArrayList는 다음과 같은 단점이 있다.

정확한 크기를 미리 알지 못하면 메모리가 낭비된다. 배열을 사용하므로 배열 뒷 부분에 사용되지 않고, 낭비되는 메모리가 있다.
데이터를 중간에 추가하거나 삭제할 때 비효율적이다.
- 이 경우 데이터를 한 칸씩 밀어야 한다. 이것은 O(n)으로 성능이 좋지 않다.
- 만약 데이터의 크기가 1,000,000건이라면 최악의 경우 데이터를 추가할 때 마다 1,000,000건의 데이터를 밀어야 한다.

배열 리스트(ArrayList)의 빅오

데이터 추가
- 마지막에 추가: O(1)
- 앞, 중간에 추가: O(n)
데이터 삭제
- 마지막에 삭제: O(1)
- 앞, 중간에 삭제: O(n)
인덱스 조회: O(1)
데이터 검색: O(n)

배열 리스트는 보통 데이터를 중간에 추가하고 삭제하는 변경하는 경우는 성능이 좋지 않고, 데이터를 순서대로 입력하고(데이터를 마지막에 추가하고), 순서대로 출력하는 경우에 가장 효율적이다.

LinkedList - 직접 구현

노드와 연결

낭비되는 메모리 없이 딱 필요한 만큼만 메모리를 확보해서 사용하고, 또 앞이나 중간에 데이터를 추가하거나 삭제할 때도 효율적인 자료 구조가 있는데, 바로 노드를 만들고 각 노드를 서로 연결하는 방식이다.

이번에는 배열이 아닌 앞서 학습한 노드와 연결 구조를 통해서 리스트를 만들어보자. 이런 자료 구조를 연결 리스트(LinkedList )라 한다. 연결 리스트는 배열 리스트의 단점인, 메모리 낭비, 중간 위치의 데이터 추가에 대한 성능 문제를 어느정도 극복할 수 있다.

연결 리스트는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등이 존재한다. 자바가 제공하는 연결 리스트는 이중 연결 리스트다. 추가로 자바가 제공하는 연결 리스트는 마지막 노드를 참조하는 변수를 가지고 있어서, 뒤에 추가하거나 삭제하는 삭제하는 경우에도 O(1)의 성능을 제공한다.

연결리스트의 ADT와 구체적인 구현 방식 등 자료구조에 관한 자세한 내용은 자료구조 카테고리의 글을 참고하시면 됩니다.

참고로, 전에 배웠던 중첩 클래스를 이용하여 Node를 LinkedList 안에 선언해주면 클래스 선언을 숨길 수 있다.

List 추상화

인터페이스 도입

배열 리스트, 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트… 등 리스트의 ADT를 구현한 자료구조는 매우 많다. ADT의 명세를 우리는 인터페이스로 도입하여 OCP 원칙을 활용할 수 있다.
공통 기능을 인터페이스로 뽑아서 추상화하면 다형성을 활용한 다양한 이득을 얻을 수 있다.

package collection.list;
public interface MyList<E> {
	int size();
	void add(E e);
	void add(int index, E e);
	E get(int index);
	E set(int index, E element);
	E remove(int index);
	int indexOf(E o);
}

기존에 구현해뒀던 리스트 구현체가 이제 MyList 인터페이스를 구현하면 된다.
추가로 재정의한 메서드에 @Override 애노테이션도 넣어주자.

의존관계 주입

리스트를 MyList<E> 인터페이스로 추상화하였기 때문에, 구현체를 변경하더라도 MyList의 구현체를 변경하더라도 리스트를 사용하는 코드에는 변경이 전혀 없다.

기존에는 아래와 같이 LinkedList 구현체에 의존하고 있었다.

public class BatchProcessor {
	private final MyLinkedList<Integer> list = new MyLinkedList<>(); //코드 변경
	// 생략
}

만약 MyLinkedList가 변경된다면 BatchProcessor의 코드 또한 변경되어야 한다.
(이러한 결합 방식을 강한 결합이라고 말한다)

인터페이스를 도입해보자. 구체적인 클래스에 의존하는 대신 추상적인 MyList 인터페이스에 의존하게 하자.

public class BatchProcessor {
	private final MyList<Integer> list;
	public BatchProcessor(MyList<Integer> list) {
		this.list = list;
	}
	// 생략
}

BatchProcessor 를 생성하는 시점에 생성자를 통해 원하는 리스트 전략(알고리즘)을 선택해서 전달하면 된
다. 이렇게 하면 MyList 를 사용하는 클라이언트 코드인 BatchProcessor 를 전혀 변경하지 않고, 원하는 리스트 전략을 런타임에 지정할 수 있다.

MyList의 인터페이스가 변경되지 않는 한, MyList의 생성자에 MyLinkedList가 전달되던, MyArrayList가 전달되던 간에 BatchProcessor의 코드는 영향을 받을 일이 없다. 즉, 구현체에 영향을 받지 않는다. (이러한 결합 방식을 약한 결합이라고 한다)

이것은 BatchProcessor 의 외부에서 의존관계가 결정되어서 BatchProcessor 인스턴스에 들어오는 것
같다. 마치 의존관계가 외부에서 주입되는 것 같다고 해서 이것을 의존관계 주입이라 한다.

컴파일 타임, 런타임 의존관계

의존관계는 크게 컴파일 타임 의존관계와 런타임 의존관계로 나눌 수 있다.

컴파일 타임 의존관계는 자바 컴파일러가 보는 의존관계이다. 클래스에 모든 의존관계가 다 나타난다.
BatchProcessor 클래스를 보면 MyList 인터페이스만 사용한다. 코드 어디에도 MyArrayList 나 MyLinkedList 같은 정보는 보이지 않는다. 따라서 BatchProcessor 는 MyList 인터페이스에만 의존한다.

런타임 의존관계는 실제 프로그램이 작동할 때 보이는 의존관계다. 주로 생성된 인스턴스와 그것을 참조하는 의존관계이다.
쉽게 이야기해서 프로그램이 실행될 때 인스턴스 간에 의존관계로 보면 된다.
런타임 의존관계는 프로그램 실행 중에 계속 변할 수 있다.

클라이언트 클래스는 컴파일 타임에 추상적인 것에 의존하고, 런타임에 의존 관계 주입을 통해 구현체를 주입받아
사용함으로써, 이런 이점을 얻을 수 있다.

전략 패턴(Strategy Pattern)

디자인 패턴 중에 가장 중요한 패턴을 하나 뽑으라고 하면 전략 패턴을 뽑을 수 있다. 전략 패턴은 알고리즘을 클라이언트 코드의 변경 없이 쉽게 교체할 수 있다. 방금 설명한 코드가 바로 전략 패턴을 사용한 코드이다.MyList 인터페이스가 바로 전략을 정의하는 인터페이스가 되고, 각각의 구현체인 MyArrayList ,MyLinkedList 가 전략의 구체적인 구현이 된다. 그리고 전략을 클라이언트 코드(BatchProcessor )의 변경없이 손쉽게 교체할 수 있다.

배열 리스트 vs 연결 리스트
대부분의 경우 배열 리스트가 성능상 유리하다. (자세한 이유는 자료구조 카테고리의 게시글을 참고하자.)
따라서 실무에서는 주로 배열 리스트를 기본으로 사용한다. 만약 데이터를 앞쪽에서 자주 추가하거나 삭제할 일이 있다면 연결 리스트를 고려하자.

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

Collection 인터페이스
Collection 인터페이스는 java.util 패키지의 컬렉션 프레임워크의 핵심 인터페이스 중 하나이다. 이 인터페이스는 자바에서 다양한 컬렉션, 즉 데이터 그룹을 다루기 위한 메서드를 정의한다. Collection 인터페이스는 List , Set , Queue 와 같은 다양한 하위 인터페이스와 함께 사용되며, 이를 통해 데이터를 리스트, 세트, 큐 등의 형태로 관리할 수 있다. 자세한 내용은 뒤에서 다룬다.

List 인터페이스
List 인터페이스는 java.util 패키지에 있는 컬렉션 프레임워크의 일부다. List 는 객체들의 순서가 있는 컬렉션을 나타내며, 같은 객체의 중복 저장을 허용한다. 이 리스트는 배열과 비슷하지만, 크기가 동적으로 변화하는 컬렉션을 다룰 때 유연하게 사용할 수 있다. List 인터페이스는 ArrayList , LinkedList 와 같은 여러 구현 클래스를 가지고 있으며, 각 클래스는 List 인 터페이스의 메서드를 구현한다.

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)`	리스트의 요소를 지정된 비교자에 따라 정렬한다.
`subList(int fromIndex, int toIndex)`	리스트의 일부분의 뷰를 반환한다.
`size()`	리스트의 요소 수를 반환한다.
`isEmpty()`	리스트가 비어있는지 여부를 반환한다.
`iterator()`	리스트의 요소에 대한 반복자를 반환한다.
`toArray()`	리스트의 모든 요소를 배열로 반환한다.
`toArray(T[] a)`	리스트의 모든 요소를 지정된 배열로 반환한다.

자바 ArrayList

java.util.ArrayList

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

데이터 추가 - 한 칸씩 이동하는 방식

데이터를 루프를 돌면서 하나씩 이동해야 하기 때문에 매우 느리다.

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

시스템 레벨에서 배열을 한 번에 아주 빠르게 복사한다. 이 부분은 OS, 하드웨어에 따라 성능이 다르기 때문에 정
확한 측정이 어렵지만, 한 칸씩 이동하는 방식과 비교하면 보통 수 배 이상의 빠른 성능을 제공한다.

자바 LinkedList

java.util.LinkedList

자바의 LinkedList 특징

이중 연결 리스트 구조
- 자세한 구현 방식은 자료구조 카테고리의 게시글 참조
첫 번째 노드와 마지막 노드 둘다 참조

성능 측정

직접 만든 배열 리스트와 연결 리스트 - 성능 비교 표

기능	배열 리스트	연결 리스트
앞에 추가(삭제)	O(n) - 1369ms	O(1) - 2ms
평균 추가(삭제)	O(n) - 651ms	O(n) - 1112ms
뒤에 추가(삭제)	O(1) - 2ms	O(n) - 2195ms
인덱스 조회	O(1) - 1ms	O(n) - 평균 438ms
검색	O(n) - 평균 115ms	O(n) - 평균 492ms

자바가 제공하는 배열 리스트와 연결 리스트 - 성능 비교 표

기능	배열 리스트	연결 리스트
앞에 추가(삭제)	O(n) - 106ms	O(1) - 2ms
평균 추가(삭제)	O(n) - 49ms	O(n) - 1116ms
뒤에 추가(삭제)	O(1) - 1ms	O(1) - 2ms
인덱스 조회	O(1) - 1ms	O(n) - 평균 439ms
검색	O(n) - 평균 104ms	O(n) - 평균 473ms

연결 리스트의 구현체로 이중 연결리스트를 사용하여 뒤에 추가(삭제) 성능이 O(1)으로 개선 되었음을 확인할 수 있다.

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

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

시간 복잡도와 실제 성능
이론적으로 LinkedList 의 중간 삽입 연산은 ArrayList 보다 빠를 수 있다. 그러나 실제 성능은 요소의 순차적 접근 속도, 메모리 할당 및 해제 비용, CPU 캐시 활용도 등 다양한 요소에 의해 영향을 받는다.
자세한 내용은 자료구조 카테고리를 참조하자.

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

참고) 김영한의 실전 자바 - 중급 2편

'Programming Language > Java' 카테고리의 다른 글

[Java] 31. HashSet (0)	2025.01.19
[Java] 30. Hash (0)	2025.01.19
[Java] 28. 제네릭 - Generic(2) (0)	2025.01.13
[Java] 27. 제네릭 - Generic(1) (0)	2025.01.13
[Java] 26. 예외 처리 - 실전 (0)	2025.01.13

현재글[Java] 29. 컬렉션- ArrayList, LinkedList, List

Brute force Study

배움을 나누는 공간 https://github.com/DawnGlow

Today :
Yesterday :

Brute force Study

[Java] 29. 컬렉션- ArrayList, LinkedList, List

컬렉션- ArrayList, LinkedList, List

C 스타일 배열

데이터 조회

데이터 추가

배열 리스트 - 직접 구현

LinkedList - 직접 구현

노드와 연결

List 추상화

인터페이스 도입

의존관계 주입

컴파일 타임, 런타임 의존관계

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

자바 ArrayList

자바 LinkedList

성능 측정

'Programming Language > Java' 카테고리의 다른 글

'Programming Language/Java'의 다른글

티스토리툴바

« 2025/02 »
일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28

[Java] 29. 컬렉션- ArrayList, LinkedList, List

컬렉션- ArrayList, LinkedList, List

C 스타일 배열

데이터 조회

데이터 추가

배열 리스트 - 직접 구현

LinkedList - 직접 구현

노드와 연결

List 추상화

인터페이스 도입

의존관계 주입

컴파일 타임, 런타임 의존관계

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

자바 ArrayList

자바 LinkedList

성능 측정

'Programming Language > Java' 카테고리의 다른 글

'Programming Language/Java'의 다른글

관련글

티스토리툴바