[면접 질문 정리] Array , ArrayList , LinkedList 를 이해해보자

요약

• Array: 크기가 정해져 있고, 빠른 읽기와 단순 구조가 필요할 때
• ArrayList: 읽기/탐색이 많고, 크기가 동적으로 바뀔 때
• LinkedList: 삽입/삭제가 자주 일어날 때 (특히 앞/중간에서)

작업 Array ArrayList LinkedList

인덱스 접근	✅ O(1)	✅ O(1)	❌ O(n)
끝에 추가	❌ 불가	✅ 빠름 (O(1)*)	✅ 빠름 (O(1))
중간 삽입/삭제	❌ 느림 (O(n))	❌ 느림 (O(n))	✅ 빠름 (O(1))
메모리 사용	✅ 적음	✅ 보통	❌ 많음 (노드 포인터 포함)

간단히 정리한 요약그림

 

Array란?

예제 코드

public class ArrayExample {
    public static void main(String[] args) {
        int[] numbers = new int[3];  // 크기 3짜리 배열 생성
        numbers[0] = 10;
        numbers[1] = 20;
        numbers[2] = 30;

        // 배열 출력
        for (int i = 0; i < numbers.length; i++) {
            System.out.println("Index " + i + ": " + numbers[i]);
        }
    }
}

특징

1. 선언시 크기를 할당하고 사용한다. Tip.고정 크기
2. 동일한 형만 저장할 수 있다. Tip.Int형으로 선언했다면 int형만 저장할 수 있다. 만약 다른 형을 넣을려면 형변환을 통해 바꿔서 넣어줘야한다.
3. 인덱스를 통한 요소접근이 빠름 → 0번은 뭐야? 45번은 뭐야 이런식으로 접근한다는 의미이다.

장점

1. O(1)로 선언된 인덱스를 찾아 가면 매우 빠르게 조회할 수 있다.
2. 형이 처음에 선언되기 때문에 안정적인 자료구조를 사용할 수 있다.

단점

1. 고정크기기 때문에 선언 후에 크기를 바꿀 수 없다. 만약 요소를 추가하거나 삭제한다면 조정과정이 필요하며만약 1~10까지 선언되어있고 5번자리에 추가로 수정한다고 한다면 5~10까지의 데이터를 하나씩뒤로 밀어내야하며, 삭제또한 같은 과정이 필요하게된다.
2. 이때 O(n)만큼 필요하다.

LinkedList란?

예제코드

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Rabbit");

        // 맨 앞에 추가
        animals.addFirst("Tiger");
        // 맨 뒤에 추가
        animals.addLast("Elephant");

        // 요소 출력
        for (String animal : animals) {
            System.out.println(animal);
        }

        // 중간 삭제
        animals.remove(2);  // 인덱스 2 요소 제거
        System.out.println("삭제 후: " + animals);
    }
}

특징

각 노드들끼리 서로를 연결한 형태로 노드기준 이전/이후 노드를 참고해 순서를 보장한다는 개념이다.

예를들어 3번노드라면 2번과 4번 노드의 주소를 참고하여 구성이 되어있다고 생각하면된다.

이게 나온게 만약 로직상 데이터의 변경이 잦을경우 LinkedList 자료구조가 유리하게 된다.

대신, Array 자료구조에 비해 검색속도가 느리다는 단점이 있다.

실제로는 이렇게 형식을 가지게된다.

null ← [prev | data | next] ↔ [prev | data | next] ↔ [prev | data | next] → null

하나의 구조에는 데이터와 앞선 노드의 정보와 후발 노드의 정보를 가지게 되어 처리가된다.

자바내부에 구현되어 있는 소스를 간단히 요약하면 다음처럼 구성되어 있다.

public class LinkedList<E> extends AbstractSequentialList<E> {
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

    private Node<E> first;  // 첫 번째 노드
    private Node<E> last;   // 마지막 노드
    private int size = 0;
}

상당히 재미있는 형식으로 되어 있다는걸 볼 수 있다.

장점

1. 중간삽입 , 수정, 삭제등의 용의하며 후발노드에 대한 추가도 편리하다
2. 동적크기이기 때문에 자료 양의 상관없이 사용이 가능하다. (단, 자바메모리상 일정 수준이 넘어가면 아웃오브 메모리가 발생할 수 있기 때문에 이에 대한 조치는 꼭 해두어야 한다.)

단점

1. 인덱스 접근이 느리다. 포인트라는 개념을 통해 인덱스에 접근하기 때문에 O(n)만큼 필요하다.
2. 포인트 구조 자체가 앞,후 노드의 정보를 가지기 때문에 메모리를 타구조에 비해 많이 사용한다.

ArrayList

예제코드

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<String> fruits = new ArrayList<>();
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Cherry");

        // 특정 요소 접근
        System.out.println("첫 번째 과일: " + fruits.get(0));

        // 전체 출력
        for (String fruit : fruits) {
            System.out.println(fruit);
        }

        // 중간에 삽입
        fruits.add(1, "Orange");
        System.out.println("삽입 후: " + fruits);
    }
}

특징

• 내부적으로 배열 사용
• 크기 자동 증가
• 인덱스를 이용한 빠른 접근 가능

장점

1. 인덱스를 통해 접근하면서 동적 크기를 사용할 수 있다.
2. 배열을 이용하기 때문에 구조자체가 LinkedList에 비해 안정적이다.

단점

1. 중간 삽입/삭제에 대해서는 성능이 떨어진다. O(n)
2. 동적크기를 사용하기 때문에 데이터양이 많아지면 아웃오브메모리가 발생할 가능성이 있다.