[Java] 배열(Array) vs. 배열리스트(ArrayList) vs. 연결리스트(LinkedList)

들어가며

본 글에서는 같은 타입의 데이터를 많이 다룰 때 사용하는 자바의 순차적 자료구조 배열(Array)과 리스트(List), 특히 배열 리스트(ArrayList)와 연결 리스트(LinkedList)에 대해 비교해보겠습니다. 자료구조 측면에서 접근하는 글이므로 코드로 배열이나 리스트를 어떻게 사용하는지는 구체적으로 적지 않겠습니다. 아울러 메모리 구조나 물리적/논리적 주소, 시간복잡도 등에 대한 내용이 나오는데, 분량이 너무 많아질 것 같아서 구체적인 설명은 기재하지 않은 점 참고 바랍니다.

 

글 내용에서 잘못된 점이 있을 경우 언제든 피드백을 남겨주세요. 언제든 피드백 대환영입니다 :)

 

 

 

배열 (Array)

| 기본 개념

• 배열이란 같은 데이터 타입의 변수들로 이루어진 자료구조로, 자바에서 기본적으로 지원하는 자료구조입니다.
• 배열을 구성하는 각각의 값은요소 혹은 원소(element)라고 부릅니다.
• 배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 부릅니다.
• 대부분의 언어에서 배열의 인덱스는 0부터 시작하며, 자바에서도 0부터 시작합니다. 참고로 파이썬의 경우 배열과 비슷한 list에서 리스트 맨 끝의 원소를 가리키는 인덱스 -1도 존재하는데, Java에서 배열의 인덱스는 0을 포함한 양의 정수만 가질 수 있습니다.
• 배열은 참조 객체이므로 배열을 가리키는 참조 변수는 스택 영역에 할당되며, 이 참조 변수가 가리키고 있는 주소값은 실제 힙 영역에 생성되는 배열의 주소값입니다.

 

| 특징

• 배열을 선언하는 순간에 배열의 크기를 지정하는데, 그 크기는 선언 이후 변경할 수 없습니다. 즉, 배열의 크기가고정적입니다.
• 선언할 때 별도의 초기화를 해주지 않는다면 배열에는 배열의 크기만큼 기본값이 채워집니다.
• 배열의 물리 주소와 논리 주소는동일합니다. 이러한 특성 덕분에 인덱스 연산자를 사용할 수 있습니다.
• 메모리 공간이연속적으로 구성됩니다.
• 기본적으로 특정 원소에 대한 읽기와 쓰기, 배열의 길이에 대한 것만 지원합니다. 물론 java.util.Arrays클래스에 구현되어 있는 배열을 위한 추가적인 기능들은 있지만 순수한 배열만 놓고 보면 특별한 기능은 따로 제공되지 않습니다.

 

| 장점

• 인덱스 연산자를 사용할 수 있기 때문에, 특정 위치에 있는 원소에 대한 접근의 시간복잡도가 O(1)입니다.
• 인덱스 연산자를 사용할 수 있기 때문에, 특정 위치에 있는 원소를 수정하는 시간복잡도는 O(1)입니다.

 

| 단점

• 배열의 크기가 고정적이라 더 많은 데이터를 저장하기 위해서 더욱 큰 배열을 만들고 이전 배열의 데이터를 새로 만든 배열로 복사해야 하는 불편함이 있습니다. 결국 새로운 배열로 데이터를 이동시키는 데에는 O(n)만큼의 시간복잡도가 소요되므로 다뤄야 할 데이터의 개수가 가변적이고 예상하기 어렵다면 배열의 사용을 지양해야 합니다.
• 배열 중간에 있는 원소를 제거해야 하는 경우, 삭제하고자 하는 위치의 인덱스 뒤에 있는 원소부터 배열의 맨 끝에 있는 원소까지 앞으로 한 칸씩 직접 재할당해줘야 합니다. 앞으로 한 칸씩 민 원소의 개수가 k라고 할 때 이 작업은 k만큼의 연산 시간이 소요되며, k는 최대 n-1이 될 수 있으므로 시간복잡도는 O(n)이라고 할 수 있습니다.
• 배열 중간에 원소를 삽입해야 하는 경우, 삽입하고자 하는 위치의 인덱스 뒤에 있는 원소부터 배열의 맨 끝에 있는 원소까지 뒤로 한 칸씩 직접 재할당해줘야 합니다. 뒤로 한 칸씩 민 원소의 개수가 k라고 할 때 이 작업은 k만큼의 연산 시간이 소요되며, k는 최대 n-1이 될 수 있으므로 시간복잡도는 O(n)이라고 할 수 있습니다.
• 추가적으로 말씀드리고 싶었던 것이 있습니다. 많은 블로그에서 배열 중간에 있는 원소를 제거하는 방법으로 원소가 제거되었다고 표시하기 위해 null을 할당해놓는 방법을 기재해주셨습니다. 그런 글들의 정보의 출처를 보니 생활코딩 영상이더라고요. 저는 생활코딩님을 굉장히 존경하고 항상 많이 배웠지만, 엄연히 따져보자면 이 방법은 매우 좋지 않은 방법이며 실무에서 이렇게 하는 경우는 없다고 생각합니다.
  
  위 방법을 사용했을 경우 조건문을 통해 배열의 원소가 null인 부분은 로직에서 제외시킬 수 있겠지만, 불필요한 데이터가 메모리 공간을 차지하고 있다는 단점이 있습니다. 즉 메모리 낭비가 발생한다는 것입니다. 많은 블로그에 이 방법이 기재되어 있던 이유도 배열이 연속된 메모리 공간으로 이루어져 있기 때문에 불필요한 데이터가 메모리 공간을 차지할 수 있다는 점과 리스트는 빈 공간을 허용하지 않는다는 특징을 언급하기 위해 이 방법을 기재해주신 것 같습니다.
  
  근데, 이 좋지 않은 방법은 한계점까지 존재합니다. 배열에 저장하고자 하는 데이터의 자료형이 기본 타입(Primitive Type)인 경우 null을 사용할 수 없다는 것입니다. 가령 int형 배열을 선언했을 경우 해당 인덱스의 원소가 삭제되었음을 알리기 위해 어떤 값을 할당해줘야 할까요? 0? 음수? 어떠한 값이 되든 플래그로서 사용하는 그 값이 실제로 들어올 수 있다는 가능성이 있습니다. 그 값이 실제값인지, 삭제되었음을 알리는 플래그인지 알 수 없게 될 수 있다는 말입니다. 생활코딩님의 강의에서는 배열의 데이터 타입이 참조 타입(Reference Type)이었기 때문에 null을 할당하는 것이 가능했던 겁니다. 그렇다고 null을 삽입하기 위해 기본 타입을 wrapper 클래스로 boxing하는 것도 딱히 좋아 보이지는 않습니다. 애초에 좋은 방법은 아니라고 생각하기 때문입니다. 

 

 

 

리스트 (List)

| 기본 개념

• 리스트를 설명하기 전에 컬렉션 프레임워크를 설명하지 않을 수 없습니다. 간단하게라도 설명하겠습니다. 자바에서 다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스의 집합을 컬렉션 프레임워크(collection framework)라고 합니다. 이러한 컬렉션 프레임워크는 자바의 인터페이스(interface)를 사용하여 구현되며, 리스트(List)는 컬렉션 프레임워크의 주요 인터페이스 중 하나입니다.
• 리스트 인터페이스는 순서가 있는 데이터의 집합으로, 데이터의 중복을 허용합니다. 참고로 대표적인 컬렉션 프레임워크의 주요 인터페이스 중 Set은 순서가 없는 데이터의 집합으로, 데이터의 중복을 허용하지 않습니다. Set에 대한 구체적인 설명은 생략하겠습니다.
• 이 글에서는 배열과 리스트의 비교를 핵심 주제로 둔 만큼, 잘 모르시는 분들이라면 일단 배열(Array)과 유사하게 순차적이며, 같은 데이터 타입의 변수들로 이루어진 자료구조라고 생각해주시면 됩니다.
• 배열과 다른 점은 저장 공간의 크기가 고정되지 않고 가변적이라는 점, 중간에 빈 공간을 허용하지 않는다는 점입니다.
• 컬렉션 프레임워크에 속하는 인터페이스를 구현한 클래스를 컬렉션 클래스(Collection Class)라고 부릅니다. 리스트(List) 인터페이스를 구현한 List 컬렉션 클래스는 여기에 'All known Implementing Classes' 하단에 있는 것들을 보시면 됩니다. 상당히 많지만 이 글에서 다 다룰 수는 없고, 가장 많이 쓰고 비교할 만한 특징이 있는 ArrayList와 LinkedList에 대해 다루겠습니다.

 

 

1. 배열 리스트 (ArrayList)

| 개념 및 특징

• 내부적으로 배열(Array)을 이용하여 요소를 저장하는 자료구조로, 배열의 정적인 크기라는 한계점을 극복하기 위해 탄생한 자료구조입니다.
• 내부적으로 배열을 사용함에도 불구하고 배열 리스트를 선언할 때 별도의 크기는 지정해 줄 필요가 없고 크기를 관리해줄 필요도 없습니다. 배열 리스트에서 데이터를 삽입하거나 삭제할 때, 연산 이후 가지고 있어야 할 원소의 개수만큼 딱 맞게 배열의 크기를 조정하여 줍니다. 이는 리스트의 중간에 빈 공간을 허용하지 않는다는 특징을 구현체에서 구현해낸 모습입니다.
• 위 특징처럼 배열 리스트의 저장 공간 크기는 가변적입니다. 하지만 배열을 사용할 때 사용자가 겪어야 할 복잡한 과정을 숨겨놓은 것일 뿐, 배열의 요소를 복사하여 새로운 배열로 옮기는 과정은 동일하며 그에 따른 시간 소요도 동일합니다. 배열 리스트를 사용하는 사용자 입장에서만 가변적인 것처럼 느끼게 만든 것일 뿐입니다.
• 내부적으로 배열을 사용하기 때문에 배열 리스트 또한 물리 공간과 논리 공간이 동일하며, 그에 따라 인덱스 연산자를 활용할 수 있습니다. 다만, 배열에서 사용했던 것처럼 인덱스 연산자를 직접 활용하는 것이 아니라 get 혹은 set 메서드를 활용합니다.
• 배열과의 가장 큰 차이점은 (1) 배열 리스트의 저장 공간 크기가 가변적인 것처럼 만들어준 점, (2) 배열에서는 지원하지 않는 List 인터페이스에서 정의한 다양한 메서드를 사용할 수 있다는 점, (3) 배열을 확장시키거나 중간에 원소를 삽입/삭제하여 발생하는 번거로운 일들을 메서드로 손쉽게 해결할 수 있다는 점입니다.

 

| 장점

• 인덱스 연산자를 활용하는 get 메서드가 지원되므로, 특정 위치에 있는 원소에 대한 접근의 시간복잡도가 O(1)입니다. 사실 get 메서드 내부적으로 배열의 인덱스를 벗어난 곳에서 원소를 가져오려고 시도하는지 bound를 체크하지만, 이 체크하는 메서드의 수행 시간 또한 내부 데이터의 개수에 선형적으로 비례하는 게 아니고 상수 시간이므로 결국엔 O(1)이라고 할 수 있습니다.
• 인덱스 연산자를 활용하는 set 메서드가 지원되므로, 특정 위치에 있는 원소에 대한 수정의 시간복잡도가 O(1)입니다. 위와 동일하게 bound를 체크하지만, 같은 이유로 결국엔 O(1)입니다.
• 배열 리스트의 저장 공간은 가변적이므로 사용자는 저장 공간의 크기에 신경을 쓰지 않아도 됩니다. 하지만 번거로운 배열의 확장 및 복사 과정을 숨겨놓은 것일 뿐, 시간복잡도 측면에서는 배열과 큰 차이가 없습니다.
• 배열 리스트 중간에 원소를 삽입/삭제하여 그 뒤의 원소를 밀어주거나 당겨주는 과정은 배열 리스트의 메서드를 통해 손쉽게 해결할 수 있습니다. 하지만 시간복잡도 측면에서는 배열과 차이가 없습니다.
• 배열 리스트의 중간에 빈 공간을 허용하지 않기 때문에 배열에 비해 메모리 공간의 낭비가 없습니다.

 

| 단점

• 여전히 배열 리스트 중간에 원소를 삽입/삭제하는 시간복잡도는 O(n)입니다.
• 여전히 배열 리스트의 저장 공간을 확장 및 복사하는 과정의 시간복잡도는 O(n)입니다.

 

 

2. 연결 리스트 (LinkedList)

| 개념 및 특징

• 배열 리스트는 배열의 정적인 크기라는 한계를 극복하기 위해 탄생했지만 아직 원소를 삽입하거나 삭제할 때 새로운 저장 공간을 재할당하여 시간복잡도가 O(n)이라는 한계가 있습니다. 연결 리스트는 그러한 한계점을 극복하기 위해 탄생한 자료구조입니다.
• 일반적인 자료구조에서 연결 리스트는 단방향 연결 리스트(Singly Linked List)와 양방향 연결 리스트(Doubly Linked List)가 존재합니다. 자바에서 LinkedList 컬렉션 클래스는 양방향 연결 리스트로 만들어져 있습니다.
• 연결 리스트의 저장 공간 크기 또한 가변적입니다. 노드를 활용하기 때문인데, 이는 장점을 서술할 때 더욱 자세히 말씀드리겠습니다.
• 물리 공간과 논리 공간이 일치하지 않으며 메모리 공간이 연속적으로 구성되어 있지 않습니다. 그에 따라 인덱스 연산자는 활용할 수 없습니다. 다만, List 인터페이스의 구현체인 만큼 get과 set 메서드를 활용할 수는 있습니다. 배열 리스트의 get과 set 메서드와 차이점은 연결되어 있는 노드를 따라가서 n번째에 있는 노드를 찾아간다는 것입니다.

 

| 장점

• 배열이나 배열 리스트와 달리 저장 공간 맨 앞에 원소를 삽입하는 시간복잡도가 O(1)입니다. 가장 첫 노드와 가장 첫 노드의 다음 노드가 참조하고 있는 next 노드, prev 노드의 링크만 변경해주면 되기 때문입니다.
• 양방향 연결 리스트이기 때문에 맨 뒤에 원소를 삽입하는 시간복잡도도 O(1)입니다. 위와 동일한 원리로 가장 마지막 노드와 가장 마지막 노드의 전 노드가 참조하고 있는 prev 노드, next 노드의 링크만 변경해주면 되기 때문입니다.
• 배열이나 배열 리스트와 달리 저장 공간에 새로운 원소가 삽입되거나 삭제될 때, 저장 공간을 확장하거나 축소하여 재할당해줄 필요가 없습니다. 각 노드의 next, prev라는 링크만 수정해주면 되기 때문입니다. 이 덕분에 데이터 추가/삭제에 대한 효율이 굉장히 높아집니다.

 

| 단점

• 특정 위치에 있는 원소에 대한 접근의 시간복잡도는 O(n)입니다. 배열이나 배열 리스트의 경우 연속된 메모리 공간으로 구성되어 있고, 물리적/논리적 공간이 일치하기 때문에 인덱스 연산자를 활용할 수 있었고 그 덕분에 특정 위치에 있는 원소에 대한 접근은 O(1)만에 가능했습니다. 하지만 연결 리스트의 경우 맨 처음 노드인 first 노드나 맨 마지막 노드 last 노드부터 찾고자 하는 위치를 향해 next 혹은 prev를 타고 가며 참조를 따라갑니다. 찾고자 하는 원소의 인덱스에 따라 찾아가기 시작하는 지점이 달라지므로 엄밀히 따지면 n/2 시간이 소요되지만, Big-O 표기법에 따라 O(n)이라고 할 수 있습니다.
• 특정 위치에 있는 원소에 대한 수정의 시간복잡도는 O(n)입니다. 위와 동일한 이유입니다.
• 연결 리스트 중간에 원소를 삽입하거나 삭제하는 시간복잡도는 O(n)입니다. 결국 삽입하거나 삭제할 위치를 찾아가기 위해 탐색을 수행해야 하는데, 이 탐색의 시간복잡도가 O(n)이기 때문입니다. 이 탐색 또한 위에서 언급했던 것처럼 n/2 시간이 소요되지만 Big-O 표기법에 따라 O(n)이라고 할 수 있습니다. 참고로 실제로 삽입하거나 삭제하는 동작은 앞 노드와 뒤 노드의 링크만 재연결해주면 되는 것이기 때문에 시간복잡도가 O(1) 입니다. 이 메서드의 시간복잡도가 O(n) 이유는 결국 탐색 때문이라고 할 수 있습니다.

 

 

 

결론

특징 및 시간복잡도 ＼ 자료구조	배열 (Array)	배열리스트 (ArrayLIst)	연결리스트 (LinkedList)
저장공간 크기	고정적	가변적	가변적
물리주소와 논리주소의 동일 여부	O	O	X
메모리 공간의 연속성	O	O	X
특정 위치에 있는 원소에 대한 접근	O(1)	O(1)	O(n)
특정 위치에 있는 원소에 대한 수정	O(1)	O(1)	O(n)
특정 원소를 탐색	O(n)	O(n)	O(n)
맨 앞에 원소 추가	O(n)	O(n)	O(1)
맨 뒤에 원소 추가	O(1)	Amortized O(1)	O(1)
중간에 원소 삽입	O(n)	O(n)	O(n)
맨 앞의 원소 삭제	O(n)	O(n)	O(1)
맨 뒤의 원소 삭제	O(1)	remove(int index): O(1) remove(Object o): O(n)	O(1)
중간에서 원소 삭제	O(n)	O(n)	O(n)

사실 위 내용은 자바에 국한된 것은 아닙니다. 많은 프로그래밍 언어에서 배열, 리스트, 연결 리스트 자료구조를 지원해주고 있으며, 특별한 경우가 아니라면 위의 특징 및 시간복잡도는 동일하게 적용됩니다.

 

위의 세 개 자료구조 중 배열과 배열 리스트를 하나로 묶어서 '배열'이라고 표현하고, 연결 리스트와 비교해보겠습니다.

• (이미 데이터셋이 만들어진 상태에서) 데이터에 대한 접근이 잦은 경우: 배열 vs. 연결 리스트
• (이미 데이터셋이 만들어진 상태에서) 데이터 수정이 잦은 경우: 배열 vs. 연결 리스트
• 데이터의 추가가 잦은 경우: 배열 vs. 연결 리스트
• 데이터의 삽입이 잦은 경우: 배열 vs. 연결 리스트
• 데이터의 삭제가 잦은 경우: 배열 vs. 연결 리스트

 

 

덩그러니 비교만 하고 끝내기에는 조금 심심한 감이 있어서 하나만 더 써보겠습니다. 위의 표에서 삽입의 시간 복잡도는 셋 다 O(n)인데 왜 연결 리스트가 더 좋다고 할 수 있을까요? 그건 삽입하는 과정을 살펴보면 알 수 있습니다.

 

우선 배열의 삽입 과정을 의사 코드로 작성해보겠습니다. (따로 공식 문서를 참고한 건 아니라 틀릴 수도 있습니다. 일반적으로 통용되는 자료구조 지식에 기반하여 작성했습니다.)

if (삽입하고자 하는 인덱스 뒤에 모든 원소가 가득 차있을 경우) {
    1. 기존의 배열보다 큰 사이즈를 가진 배열을 선언
    2. 기존 배열의 원소를 새로운 배열에 복사하며 기존 삽입하고자 하는 인덱스에는 알맞은 값을 삽입
        => 확정적으로 N의 시간 소요
    3. 기존의 배열을 GC가 수거
    
} else {
    1. 삽입하고자 하는 인덱스 뒤에 있는 모든 원소를 뒤로 한 칸씩 밀면서 재할당
        => 최악의 경우 N의 시간 소요
    2. 삽입하고자 하는 인덱스에 원하는 값을 삽입
}

참고로 바운드 체크를 하는 등의 사소한 것들은 적지 않고 최대한 핵심이 되는 로직들만 작성했습니다. 배열 리스트의 삽입 과정은 위의 과정과 크게 다르지 않지만, 항상 내부에서 활용하고 있는 배열의 크기와 저장하고 있는 원소 개수를 동일하게 유지하고 있기 때문에 위의 과정에서 else를 제외하면 됩니다. 완전 정확한 말은 아니지만, 확정적으로 N의 시간이 소요된다는 점이 포인트입니다.

 

아울러 배열과 배열 리스트는 연속적인 메모리 영역을 할당받게 됩니다. 배열 혹은 배열 리스트에게 재할당해줘야 할 메모리 크기가 말도 안 되게 클 경우에는 OutOfMemoryError가 발생할 확률이 높아집니다.

 

 

반면 연결 리스트의 삽입 과정을 의사 코드로 작성해보겠습니다. (이것 또한 따로 공식 문서를 참고한 건 아니라 틀릴 수도 있습니다.)

if (원소를 삽입하려는 위치와 연결 리스트의 사이즈를 비교했을 때, first 노드에서 시작하는 게 좋을 때) {
    1. first 노드부터 next를 타고 흘러가며 원소를 삽입하려는 위치까지 이동한 후
    2. 해당 위치에 있는 기존 노드의 next와 prev, 삽입하고자 했던 노드의 next와 prev 수정
} else {
    1. last 노드부터 prev를 타고 흘러가며 원소를 삽입하려는 위치까지 이동한 후
    2. 해당 위치에 있는 기존 노드의 next와 prev, 삽입하고자 했던 노드의 next와 prev 수정
}

연결 리스트의 삽입 시간복잡도는 O(n)이지만, 사실 확정적으로 위 로직은 N/2 시간이 소요됩니다. first 노드에서 시작하는 게 좋을지, last 노드에서 시작하는 게 좋을지 판단하는 조건문이 그걸 가능하게 해 주죠. Big-O 표기법에 따라 배열 리스트의 삽입 시간복잡도와 연결 리스트의 삽입 시간복잡도가 같아 보일 수 있지만 엄밀히 따지면 2배의 가량의 속도 차이가 무조건 발생한다고 할 수 있습니다. 추가적으로 연결 리스트의 삽입에서는 GC가 수거해야 하는 일도 발생하지 않죠. 이 또한 이점이라고 할 수 있습니다.

 

 

 

 

 

참고 자료

1. Oracle 공식 문서 - Array

2. Oracle 공식 문서 - List

3. Oracle 공식 문서 - ArrayList

4. Oracle 공식 문서 - LinkedList 

5. TCP School - 컬렉션 프레임워크의 개념