ArrayList VS LinkedList

홍예석·2023년 4월 24일
0

기술면접을 위한 개념 정리 - Mockterview의 50문 50답

#1 배열, 링크드리스트를 비교하여 설명해주실 수 있을까요?

사실 자바의 자료 구조에 대한 공부를 언젠가 끝까지 해야겠다는 마음을 가진 채 계속 미뤄두고만 있었다. 하지만 토이 프로젝트를 완성하고 취업 지원을 위한 준비를 시작하자 기술 면접과 꼬리 물기 질문에 대비해야 했고, 이를 위해 목터뷰의 질문에 답안을 작성해 보기로 했다.
그런데 첫 번째 질문이 이 질문인 것을 보고 조금 당황했다. 배열, List, Set 자료 구조는 많이 썼지만 LinkedList는 List의 구현체 중에서는 써 본 적이 없는 자료형이었기 때문이다. 따라서 첫 번째 질문에 답도 작성할 겸, 자료 구조 공부도 할 겸 개념을 정리해 보기로 했다.

Array

가장 먼저 배열의 경우 이미 너무나 익숙한 자료형이다. 배열은 데이터를 순서대로 저장하고, index를 통해 접근할 수 있도록 되어 있는 자료형이다. 처음 생성할 때 배열의 크기는 고정되어 있으며 따라서 고정된 크기의 배열 안에서의 데이터 가공은 가능하지만 크기를 늘리거나 줄이기 위해서는 그 자체를 변경시키는 것은 불가능하고 해당 배열의 데이터를 복사한 새로운 배열을 만들어야 한다.
즉, 배열의 가장 핵심적인 특성은 아래의 3가지로 요약된다.

  • 순서가 있다.
  • 데이터에 접근할 때 index를 통해 접근한다.
  • 크기가 고정되어 있다.

ArrayList

ArrayList는 List 인터페이스의 구현체다. 이름에서부터 이미 알 수 있듯이, ArrayList는 내부적으로 Array로 구현된 List로 이해할 수 있다. 이미 자바의 자료 구조에서 Collection을 한 번이라도 공부한 사람들에게 있어 ArrayList는 너무나 친숙한 자료형일 수밖에 없는데, 아래와 같은 형태로 가장 빈번하게 쓰이기 때문이다.

List<T> dataList = new ArrayList<>();

여기서 한 가지 의문이 들 수 있는 점은, 분명 배열은 크기가 고정되어 있다는 특징이 있었는데, 우리가 ArrayList를 쓸 때는 크기를 고정해 두고 쓰지 않고 위의 코드 조각처럼 한 번 선언한 이후에는 얼마든지 크기를 변경할 수 있다.

그 이유는 ArrayList가 배열의 크기가 변경될 때마다, 즉 add, remove 등의 메서드를 활용할 때마다 배열을 복사해서 return하고 있기 때문이다. 그렇다면 add와 remove를 할 때마다 배열을 복사한다면 데이터를 추가할 때마다 새로운 배열이 만들어진다는 말인데, 그러면 그 때마다 메모리가 재할당되므로 성능상 불리할 수밖에 없지 않을까?

remove의 경우 어쩔 수 없이 해당 index의 데이터를 제외하고 그 뒤의 데이터의 index를 1씩 감소시키는 작업을 거치는 로직으로 구성되어 있긴 하다. 하지만 add의 경우 만약 새로운 데이터를 집어넣을 공간이 부족하다면 해당 배열의 50%의 길이만큼 한 번에 증가시키도록 구성되어 있기 때문에 remove에 비해서는 성능상 조금은 덜 불리하도록 되어 있다.

그렇다곤 해도 데이터의 추가 및 삭제가 빈번하다면 그 때마다 메모리가 재할당되는 것 자체는 부정할 수 없는 사실이다. 따라서 이러한 경우에는 LinkedList를 활용할 수 있게 된다.

LinkedList

LinkedList 역시 ArrayList와 마찬가지로 List 인터페이스의 구현체다. 하지만 내부적으로는 Array가 아닌 Node로 구성되어 있다는 점에서 차이가 있다.
Node는? 노드가 뭐지? 분명 ArrayList까지의 내용을 작성할 때까지는 막힘 없이 편하게 작성했는데, LinkedList에 대해 쓰려고 하니 말문이 막혀 여기서 고민을 많이 했다. 구글링도 하고 gpt에게 물어도 보고 하면서 이해한 내용이라 정확하지 않을 수는 있다.

우선 LinkedList는 Node로 구성되어 있고, Node는 다시 element와 다음 Node로 구성되어 있다. 이 부분에서 조금 헷갈렸던 부분은, 대부분의 블로그에서 요소와 다음 Node에 대한 참조로 구성되어 있다고 설명하고 있는데, 처음에 참조라고 하길래 다음 Node에 대한 특정 정보를 갖고 있는 줄 알았다. 하지만 gpt로부터 Node가 어떻게 구현되어 있는지를 보고 바로 이해할 수 있었다.

private static class Node<E> {
    E item; // 데이터
    Node<E> next; // 다음 노드의 참조

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

이 Node클래스를 보면 알 수 있듯이, Node는 해당 제네릭 타입의 데이터만 갖고 있는 것이 아니라 또다른 Node 객체 그 자체를 갖고 있다.

Node = element + Node
-> Node = element + (element + Node)
-> Node = element + (element + (element + Node))
-> ...(반복)

따라서 Node element + Node, 두 번째 Node 안에 다시 elemet + Node가 있는 것이고, 참조라고 표현하는 이유는 자바에서 클래스 내부의 변수에 접근하는 행위 자체를 '참조'한다고 표현하기 때문이었다.

따라서 LinkedList 역시 List의 구현체이긴 하지만 ArrayList와 그 메서드들이 다른 로직으로 구현되어 있고, 그 차이는 Array와 Node의 차이로부터 기인하는 것.
한 번 예시를 통해 차이를 파악해 보자

ArrayList : {0,1,2,3}
LinkedList : {0, Node1 : {1,Node2 : {2, Node3 ...}}}

위와 같이 ArrayList LinkedList 있을 때, 데이터의 추가(add), 조회(get), 수정(set), 삭제(remove)가 일어난다고 해 보자

  • 추가 (add)
    • ArrayList : 배열의 길이가 6인 배열을 만들어 복사 후 5번 index에 값을 삽입하여 대체
    • LinkedList : next가 null상태인 마지막 Node에 Node 삽입
  • 조회 (get)
    • ArrayList : index의 element를 반환
    • LinkedList : index 숫자만큼 참조 후 element 반환
  • 수정 (set)
    • ArrayList : index의 element를 수정
    • LinkedList : index 숫자만큼 참조 후 element 수정
  • 삭제 (remove)
    • ArrayList : index의 element를 제거 후 index 이후의 element를 하나씩 앞으로 이동
    • LinkedList : index 숫자만큼 참조 후 제거하고 index의 prev와 next를 연결
  • ArrayList와 LinkedList의 add, get, set, remove의 시간 복잡도
연산ArrayListLinkedList
add(E e)O(1) (average), O(n) (worst case)O(1)
add(int index, E e)O(1) (average), O(n) (worst case)O(n)
get(int index)O(1)O(n)
set(int index, E element)O(1)O(n)
remove(int index)O(n)O(n)

ArrayList vs LinkedList의 결론

시간 복잡도에서 알 수 있듯이 배열의 복제가 이루어질 여지가 높은지 여부가 두 List 구현체 중 어느 구현체를 사용할 지의 기준이 된다. 아래는 그러한 경우의 구체적인 예시다.

ArrayList를 사용하는 경우:

데이터를 순차적으로 추가하거나 삭제하지 않고, 데이터 조회가 주된 용도인 경우
데이터의 개수가 상대적으로 적은 경우 (복제하는 데이터의 수가 적음)
데이터의 크기가 일정한 경우 (배열은 연속된 메모리에 데이터가 할당되기 때문)

LinkedList를 사용하는 경우:

데이터를 중간에 삽입하거나 삭제하는 경우
데이터의 개수가 많은 경우
데이터의 크기가 다양한 경우 (데이터 크기가 자주 변하는 경우)

profile
잘 읽어야 쓸 수 있고 잘 들어야 말할 수 있다

0개의 댓글