개발 학습 실습실

이 사이트의 실습은 자바스크립트를 켜야 움직입니다. 아래는 같은 내용을 글로 적은 것입니다.

공부 › Java › 컬렉션

ArrayList와 LinkedList

같은 연산인데 드는 일의 양이 다르다

ArrayList는 배열 한 덩어리에 원소를 붙여 저장하고, LinkedList는 원소마다 노드를 만들어 앞뒤로 연결합니다. 조회, 삽입, 삭제를 위치를 바꿔 가며 해 보면 한쪽은 원소를 옮기느라, 다른 쪽은 노드를 따라가느라 일을 합니다.

실행으로 대조 · JDK 21의 실제 ArrayList 내부 배열과 대조

이 실습에 나오는 개념

ArrayList
내부에 배열을 두고 가득 차면 더 큰 배열로 옮겨 담는 리스트다. 인덱스로 원소에 접근하는 속도가 O(1)로 빠르고, 끝에 추가하는 것도 분할 상환으로 O(1)이다. 중간에 삽입하거나 삭제하면 뒤의 원소들을 한 칸씩 옮겨야 해서 O(n)이 걸린다.
LinkedList
각 원소(노드)가 앞뒤 원소의 위치를 가리키는 방식으로 연결된 리스트다. 특정 위치를 알고 있으면 삽입과 삭제가 O(1)이지만, n번째 원소를 찾으려면 처음부터 따라가야 해서 O(n)이다. 노드마다 추가 메모리가 들고 메모리상에 흩어져 있어 실제 순회 성능은 배열 기반보다 떨어지는 경우가 많다.
시간 복잡도(Big-O)
입력 크기 n이 커질 때 알고리즘의 연산 횟수가 얼마나 빠르게 늘어나는지를 나타내는 표기다. O(1)은 크기와 무관하게 일정, O(log n)은 크기가 두 배가 되어도 한 단계만 늘어남, O(n)은 크기에 비례, O(n²)은 크기의 제곱에 비례함을 뜻한다. 데이터가 많아질 때 어떤 방식이 버티는지 판단하는 기준이다.
분할 상환 분석
가끔 비용이 큰 연산이 있더라도 연속된 연산 전체의 비용을 연산 횟수로 나눈 평균으로 평가하는 방법이다. ArrayList의 끝에 추가하는 연산은 배열이 가득 찼을 때 O(n)의 복사가 일어나지만, 그런 일은 드물어서 연산당 평균 비용은 O(1)이다.

이렇게 바꿔 보세요

처음 설정으로 실행하면

  1. add(0, 99): 0번 칸에 넣으려면 자리를 비워야 합니다. 0번부터 끝까지 원소 10개가 옮겨질 대상입니다.
  2. 원소 10개를 한 칸씩 뒤로 복사해 옮긴 뒤, 빈 0번 칸에 99를 넣었습니다.

실행 결과

코드

List<Integer> list = new ArrayList<>();
// ... 원소 10개가 들어 있는 상태 (인덱스 0 ~ 9)

list.add(0, 99);        // 맨 앞

이 모형의 전제

삽입 한 번을 볼 때는 ArrayList 내부 배열에 빈 칸이 남아 있다고 가정했습니다. 꽉 찬 경우는 "맨 뒤로 계속 추가"에서 따로 보여 줍니다. ArrayList의 용량이 10에서 시작해 1.5배씩(10 → 15 → 22 → 33 → 49) 늘어나는 것과, LinkedList가 인덱스 위치에 따라 앞이나 뒤 중 가까운 쪽에서 출발하는 것은 JDK 구현과 같습니다. 용량이 늘어나는 시점과 복사량은 이 PC의 JDK 21에서 실제 ArrayList 내부 배열을 꺼내 확인한 값과 일치합니다(40개 추가 시 4번 늘리고 80개 복사). 실제 속도는 칸 수만으로 정해지지 않습니다. 배열은 원소를 가리키는 참조가 메모리에 연속으로 놓여 있어 CPU 캐시에 유리하므로, 옮기는 양이 많아도 LinkedList보다 빠른 경우가 흔합니다.

앞 실습: 애너테이션 · 다음 실습: HashMap 내부

이 실습에 나오는 개념

이 실습에서 보는 것

설정

코드


      
    


    

      
그림

      

      

    


    

      

      

      

    


  


  

    

      
실행 비교

      

      

    

    

      
이렇게 바꿔 보세요