🚂 배열 · 동적 배열 · 연결 리스트 구조 정리

데이터를 저장하는 방식은 프로그램의 성능에 직접적인 영향을 미친다.

배열(Array)과 동적 배열(Dynamic Array) 그리고 연결 리스트(Linked List)는 대표적인 선형 자료구조이지만, 구조가 다르기 때문에 조회 / 삽입 / 삭제와 같은 연산 성능에서 차이가 발생한다.

각 자료구조의 특징과 장단점을 이해하면 상황에 맞는 자료구조를 선택해 프로그램 성능을 향상시킬 수 있다.

선형 자료구조(Linear Data Structure)란 데이터가 논리적인 순서를 가지는 자료구조를 뜻한다. 각 데이터는 앞뒤 순서를 가지며, 처음부터 끝까지 순차적으로 탐색할 수 있다.

1. 배열(Array) 

배열은 동일한 타입의 데이터를 연속된 메모리 공간에 저장한다. 각 요소는 인덱스(Index)를 통해 구분되며, 인덱스는 0부터 시작한다.

데이터의 타입이 같기 때문에 모든 요소의 크기(Byte)가 같다. 따라서 시작 주소 + (요소의 크기 x 인덱스)을 계산하면 특정 요소의 메모리 주소를 바로 계산할 수 있다. 이처럼 인덱스를 이용해 원하는 요소에 바로 접근하는 방식을 임의 접근(Random Access)이라고 한다.

public class ArrayExample {
    public static void main(String[] args) {
        int[] numbers = {10, 20, 30, 40, 50};
        
        // 인덱스를 이용한 요소 접근
        System.out.println(numbers[2]); // 30 출력
    }
}​

정적 할당

배열은 데이터를 연속된 메모리 공간에 저장하기 때문에 생성 시 크기를 지정하고 해당 크기만큼의 메모리 공간을 미리 확보해야 한다. 따라서 생성 이후에는 크기를 변경할 수도 없다.

public class ArraySizeExample {
    public static void main(String[] args) {
        int[] arr = new int[3];
        
        arr[0] = 10;
        arr[1] = 20;
        arr[2] = 30;
        
        // 배열의 크기를 변경하려고 하면 컴파일 오류가 발생한다.
        // The final field array.length cannot be assigned
        arr.length = 5;
    }
}

크기를 늘려야 하는 경우에는 새로운 배열을 생성하고 기존 데이터를 복사해야 한다.

public class ArrayCopyExample {
    public static void main(String[] args) {
        int[] arr = new int[3];
        
        arr[0] = 10;
        arr[1] = 20;
        arr[2] = 30;
        
        // 원하는 크기의 배열 생성
        int[] newArr = new int[5];
        
        // 기존 데이터 복사
        for (int i = 0; i < arr.length; i++) {
            newArr[i] = arr[i];
        }
        
        arr = newArr;
    }
}​

조회 / 삽입 / 삭제

배열은 인덱스를 이용한 임의 접근이 가능하기 때문에 데이터의 개수와 관계없이 원하는 위치의 요소를 바로 조회할 수 있다. 따라서 조회 연산은 O(1)의 시간 복잡도를 가진다.

public class ArrayAccessExample {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        
        // 인덱스를 이용해 원하는 요소에 접근
        int value = arr[2];
        
        System.out.println(value); // 30 출력
    }
}

반면 배열의 중간에 새로운 요소를 삽입하거나 삭제하려면 연속된 메모리 구조를 유지하기 위해 기존 요소들을 이동해야 한다.

import java.util.Arrays;​

public class ArrayInsertDeleteExample {
    public static void main(String[] args) {
        int[] arr = new int[6];
        
        arr[0] = 10;
        arr[1] = 20;
        arr[2] = 30;
        arr[3] = 40;
        arr[4] = 50;
        
        // 삽입
        int insertIndex = 2;
        int insertValue = 25;
        
        for (int i = 4; i >= insertIndex; i--) {
            arr[i + 1] = arr[i];
        }
        
        arr[insertIndex] = insertValue;
        
        // [10, 20, 25, 30, 40, 50]
        System.out.println(Arrays.toString(arr));

        // 삭제
        int deleteIndex = 2;
        
        for (int i = deleteIndex; i < arr.length - 1; i++) {
            arr[i] = arr[i + 1];
        }
        
        // [10, 20, 30, 40, 50, 50]
        // 삭제하더라도 배열의 크기는 유지되므로 마지막 요소는 남아있다. 
        System.out.println(Arrays.toString(arr));
    }
}

배열 중간 위치의 삽입과 삭제는 이동해야 하는 요소가 많을수록 성능이 떨어지며, 최악의 경우 O(n)의 시간이 필요하다.

반면 배열의 끝 위치에서의 삽입과 삭제는 요소 이동이 필요하지 않기 때문에 O(1)의 시간 복잡도를 가진다.

2. 동적 배열(Dynamic Array)

동적 배열은 크기를 미리 정하지 않아도 되는 배열이다. 내부적으로는 일반 배열과 비슷하지만, 공간이 부족해지면 더 큰 배열을 새로 만들어 기존 데이터를 복사하는 과정을 알아서 처리한다.

즉, 앞에서 직접 구현했던 배열 복사 과정을 내부에 감춘 것이 동적 배열이다. 대표적으로 Java의 ArrayList, C++의 vector, Python의 list 등이 있다.

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

public class DynamicArrayExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        
        // 크기를 지정하지 않아도 계속 삽입할 수 있다.
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        
        // 인덱스를 이용한 접근
        System.out.println(numbers.get(2)); // 30 출력
    }
}

동적 할당

동적 배열은 두 크기를 구분해서 관리한다. 실제로 확보한 메모리 공간을 의미하는 용량(Capacity)과 현재 데이터의 개수인 크기(Size)다.

데이터를 삽입하다가 크기가 용량에 다다르면, 더 큰 배열을 새로 만들고 기존 데이터를 복사한다. 이 과정을 리사이징(Resizing)이라고 한다.

import java.util.Arrays;

public class SimpleDynamicArray {
    private int[] elements;
    private int size;
    
    public SimpleDynamicArray() {
        this.elements = new int[4]; // 임의의 초기 용량
        this.size = 0;
    }
    
    public void add(int value) {
        // 용량이 가득 차면 확장
        if (size == elements.length) {
            grow();
        }
        
        elements[size] = value;
        size++;
    }
    
    private void grow() {
        // 기존 용량의 2배
        int newCapacity = elemtns.length * 2;
        
        // 더 큰 배열을 만들고 기존 데이터를 복사
        elements = Arrays.copyOf(elements, newCapacity);
    }
}​

일반적으로 용량을 늘릴 땐 배수로 늘리는데, 이유는 리사이징 횟수를 줄이기 위해서다. 만약 데이터를 삽입할 때마다 크기를 늘린다면 전체 복사가 발생해 n 개의 데이터를 넣는 데 O(n²)의 시간이 필요하다.

반면 배수로 늘리는 경우 복사 비용을 전체 삽입 횟수에 나누어 계산했을 때 삽입 한 번당 평균 O(1)이 된다.

조회 / 삽입 / 삭제

동적 배열의 내부는 배열이기 때문에 인덱스를 이용한 임의 접근이 가능하다. 따라서 조회는 배열과 동일하게 O(1)의 시간 복잡도를 가진다.

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

public class DynamicArrayAccessExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>(List.of(10, 20, 30));
        
        // 인덱스를 이용한 임의 접근
        int value = numbers.get(2);
        
        System.out.println(value); // 30 출력
    }
}

삽입 역시 배열과 마찬가지로 끝 위치에 데이터를 삽입할 때는 요소 이동이 없으므로 O(1)이지만, 용량이 가득 차 리사이징이 발생하는 순간 전체 복사가 일어나 O(n)이 된다.

중간 위치의 삽입과 삭제는 연속된 메모리 구조를 유지하기 위해 뒤쪽 요소들을 모두 이동해야 하므로 O(n)의 시간이 필요하다.

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

public class DynamicArrayInsertDeleteExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>(List.of(10, 20, 30, 40, 50));
        
        // 끝 위치 삽입
        numbers.add(60);
        
        // [10, 20, 30, 40, 50, 60]
        System.out.println(numbers);
        
        // 중간 위치 삽입
        numbers.add(2, 25);
        
        // [10, 20, 25, 30, 40, 50, 60]
        System.out.println(numbers);
        
        // 중간 위치 삭제
        numbers.remove(2);
        
        // [10, 20, 30, 40, 50, 60]
        // 배열과 달리 삭제하면 크기(size)도 함께 줄어든다.
        System.out.println(numbers);
    }
}

배열에서는 요소를 삭제해도 크기가 유지되어 마지막 값이 남지만, 동적 배열은 크기를 함께 관리하므로 삭제한 만큼 크기가 줄어든다. 다만, 이때 줄어드는 것은 크기일 뿐 용량은 그대로이므로, 한 번 늘어난 메모리 공간은 계속 점유한다.

3. 연결 리스트(Linked List)

연결 리스트는 데이터를 연속된 메모리 공간에 저장하지 않는다. 대신 데이터를 담은 노드(Node)를 만들고, 각 노드가 다음 노드의 주소를 참조하도록 연결한다.

노드는 저장할 값과 다음 노드를 가리키는 참조로 구성된다. 따라서 리스트 전체를 다루려면 첫 번째 노드를 가리키는 참조(head)부터 시작해 다음 노드를 순차적으로 조회해야 한다.

마지막 노드는 다음에 이어질 노드가 없으므로 참조 값으로 null이 들어간다.

public class LinkedListExample {
    static class Node {
        int data;
        Node next;
        
        Node(int data) {
            this.data = data;
        }
    }
    
    public static void main(String[] args) {
        Node head = new Node(10);
        head.next = new Node(20);
        head.next.next = new Node(30);
        
        // head부터 next를 따라가며 조회
        for (Node node = head; node != null; node = node.next) {
            System.out.println(node.data); // 10, 20, 30 출력
        }
    }
}

요소가 흩어져 있기 때문에 배열이나 동적 배열처럼 인덱스로 메모리 주소를 계산할 수 없다.

세 번째 값을 읽으려면 head에서부터 시작해 순서대로 참조를 따라가야 한다. 이와 같은 방식을 순차 접근(Sequential Access)이라고 한다.

노드 단위 할당

배열은 생성 시점에 전체 메모리 공간을 확보하지만, 연결 리스트는 노드를 하나 만들 때마다 그 노드에 필요한 공간만 확보한다.

따라서 크기를 미리 정할 필요가 없고, 동적 배열처럼 용량이 가득 차 전체를 복사하는 리사이징도 발생하지 않는다.

대신 노드마다 다음 노드를 가리키는 참조를 함께 저장하므로, 같은 개수의 값을 담아도 배열보다 메모리를 더 사용하게 된다.

조회 / 삽입 / 삭제

연결 리스트의 조회는 head부터 참조를 따라가야 하므로 O(n)의 시간 복잡도를 가진다.

public class LinkedListAccessExample {
    static class Node {
        int data;
        Node next;
        
        Node(int data) {
            this.data = data;
        }
    }
    
    public static void main(String[] args) {
        Node head = new Node(10);
        head.next = new Node(20);
        head.next.next = new Node(30);
        
        // 세 번째 값을 읽으려면 head부터 두 번 이동해야 한다.
        Node current = head;
        for (int i = 0; i < 2; i++) {
            current = current.next;
        }
        
        System.out.println(current.data); // 30 출력
    }
}

반면 삽입과 삭제는 참조만 바꾸면 되므로 요소를 이동할 필요가 없다. 삽입할 위치의 이전 노드를 알고 있다면 O(1)의 시간 복잡도를 가진다.

public class LinkedListInsertDeleteExample {
    static class Node {
        int data;
        Node next;
        
        Node(int data) {
            this.data = data;
        }
    }
    
    public static void main(String[] args) {
        Node head = new Node(10);
        head.next = new Node(20);
        head.next.next = new Node(30);
        
        // 삽입
        Node prev = head.next;
        Node newNode = new Node(25);
        
        newNode.next = prev.next;
        prev.next = newNode;
        
        // 10, 20, 25, 30
        print(head);
        
        // 삭제
        prev.next = prev.next.next;
        
        // 10, 20, 30
        print(head);        
    }
    
    private static void print(Node head) {
        for (Node node = head; node != null; node = node.next) {
            System.out.print(node.data + " ");
        }
        
        System.out.println();
    }
}

단일 / 이중 / 원형 연결 리스트

위와 같이 각 노드가 다음 노드만을 가리키는 형태를 단일 연결 리스트(Singly Linked List)라고 한다.

이외에도 이중 연결 리스트(Doubly Linked List)는 각 노드가 이전 노드를 가리키는 참조를 하나 더 가진다. 양방향으로 순회가 가능하며, 삭제할 노드 하나만 알면 앞뒤로 바로 이어붙일 수 있다. Java의 LinkedList가 이 방식이다.

원형 연결 리스트(Circular Linked List)는 마지막 노드가 null 대신 head를 가리킨다. 끝에 도달해도 다시 처음으로 돌아오므로 순번을 돌아가며 처리하는 작업에 적합하다.

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

public class JavaLinkedListExample {
    public static void main(String[] args) {
        LinkedList<Integer>​ numbers = new LinkedList<>(List.of(10, 20, 30));
        
        // 맨 앞 삽입도 요소 이동 없이 처리된다.
        numbers.addFirst(5);
        
        // [5, 10, 20, 30]
        System.out.println(numbers);        
    }
}