[Java] 배열(array), ArrayList, LinkedList 차이점 + 사용 용도 정리

 

array, arraylist, linkedlist 각각의 차이점을 비교해 보고 어떤 상황에서 어떤 자료구조 사용이 적절한지 알아보자

 

배열(array) , ArrayList , LinkedList 언제 사용해야 하나?

 

Array 사용용도

• 데이터 개수가 고정적이고 삽입, 삭제가 빈번하지 않은 경우
• 데이터 접근이 빈번한 경우
• 기본 자료형(int, char, double..) 사용하고 싶은 경우

 

ArrayList 사용용도

• 데이터의 개수가 예상가능예상 가능하고삽입, 삭제가 빈번하지 않은 경우
• 데이터의 접근이 빈번한 경우

 

LinkedList 사용용도

• 데이터의 삽입, 삭제가 빈번한 경우
• 데이터의 접근이 빈번하지 않은 경우
• 데이터 개수가 많지 않은 경우
• (삽입, 삭제도 맨 앞, 맨 뒤 노드에 대한 것이 아닌 이상
• 일단 해당 위치로 접근해야 하기 때문에 데이터가 많은 경우 삽입, 삭제도 느려질 수 있음)

 

 

 

배열(array) vs ArrayList

ArrayList도 결국 배열. 실제로 ArrayList는 자바에서 내부적으로 array로 구현되어 있다.

차이점은 다음과 같다.

 

1) Resizable(크기의 고정, 가변 여부)

일단 배열의 크기는 고정적이다.

ArrayList 크기는 표면적으로는 가변적이다.하지만 실제로는 array로 구현되어 있어 크기가 넘는 데이터 추가는 내부적으로 보다 큰 배열을 생성하여 기존 배열의 내용을 복사한다.

 

따라서 ArrayList도 진정한 의미의 가변적 크기를 갖는 것은 아니다. 

 

2) Performance(성능)

Resizable과 같은 맥락으로 배열의 크기는 고정적이기에 동적으로 메모리를 할당하지 않아도 되기에 성능이 빠르다.

반면 ArrayList의 경우 크기가 가변적이라는 기능을 수행하기 위해 별도로 배열을 생성하고 복사하는 과정이 필요하기에

비교적 성능이 느리다.

 

3) 사용 가능한 자료형

배열은 기본 자료형(Primitive type)과 참조 자료형(Reference type)으로 모두 선언 가능하다.

arrayList는 참조 자료형으로만 선언 가능하다. 이는 arrayList가 Object배열로 구현되어 있고 모든 참조 자료형은 Object를 상속받기 때문이다.

 

4) 반복문(Iteration)

배열은 for문, for-each문 등을 통해 반복적인 접근을 한다.

arrayList의 경우 iterator를 이용하여 반복적인 접근을 한다.

 

 

이외 보다 자세한 사항은 다음 사이트에 잘 정리되어 있다.

https://www.javatpoint.com/difference-between-array-and-arraylist

 

ArrayList vs LinkedList

 

	접근	순차적 추가/삭제	비순차적 추가/삭제	메모리 효율성
ArrayList	빠르다	아주 빠르다	느리다	비효율적
LinkedList	느리다	빠르다	빠르다	효율적

 

(비순차적 추가/삭제: 맨 앞 혹은 맨 뒤가 아닌 요소를 수정하는 것이 아니라 중간 index를 갖는 데이터를 추가하거나 삭제하는 행위)

 

 

자바에서 ArrayLists는 내부적으로 array로 구현되어 있기에 배열의 문제점을 그대로 갖는다.

 

    1. 크기를 변경할 수 없다.

 

겉으로는 크기를 변경하는 것 처럼 보이지만 ArrayList 크기를 넘어가는 데이터 삽입은 내부적으로 array를 지웠다가 다시 크기가 큰 array를 생성한다. 따라서 연산에 시간이 많이 걸린다

 

    2. 비순차적인 데이터 추가, 삭제에 시간이 많이 걸린다.

 

여기서 '비순차적'이란 데이터를 모두 추가한 후 삭제를 하는 것이 아니라 중간 index를 갖는 데이터를 추가하거나 삭제하는 행위를 의미한다. 이렇게 중간에 있는 데이터를 수정하는 경우 그 이후 index 데이터들을 모두 복사하고 데이터를 수정하고 다시 복사시킨다.

 

 

 

자바의 LinkedList는 '이중 원형 리스트'로 구현되어 있어

 

   1. 순차적, 비순차적 데이터 추가, 삭제가 간단하다. 단순히 앞뒤 node들의 연결만 수정해주면 된다.

 

   2.  반면 접근 연산은 아주 느리다

 

 

배열은 크기가 고정되어 값들을 연속적인 주소 값으로 저장이 가능하지만 

연결 리스트는 크기가 고정되어 있지 않기에 선행 노드와 후행 노드의 주소 값이 불연속적이다.

따라서 연결리스트는 배열처럼 단순히 index크기만큼 값을 더하여 접근하는 연산이 불가능하다.

 

배열이 그림과 같이 0번째 주소 값에서 index크기만큼 더하기 연산으로 접근하기에 접근 연산이 O(1)인 반면

연결리스트는 그림과 같이 노드의 순서에 따라 하나씩 이동을 하여 접근한다.

 

 

---

참고

 

Java의 정석 3rd Edition - 남궁성 지음

 

https://www.javatpoint.com/difference-between-array-and-arraylist