자바 ArrayList VS LinkedList VS Vector

by Dark Tornado

Oct 03, 2022

배열

자바에 있는 배열은 길이가 고정되어 있어요. 동적으로 길이가 변하는 선형 자료구조가 필요하다면 List 인터페이스를 implements하는 클래스들 중 하나를 사용하면 되는거에요.

ArrayList

JDK 1.2에서 추가되었으며, 동기화를 지원하지 않아요.
쓰레드가 하나 밖에 없는 경우와 같이 Thread Safe하게 구현할 필요가 없다면 ArrayList를 사용하는 것이 이후에 다룰 Vector를 쓰는 것보다 좋아요.

ArrayList는 내부에 배열을 하나 만들어두고, 그 배열에 값을 저장하고, 안에 있는 배열이 다 차면 배열의 길이를 1.5배 늘러요.
정확히는 1.5배 더 긴 배열을 만들고, 원래 있던 배열에 저장된 내용을 새로 만든 배열로 옮겨요.
원래 쓰던 배열은 버리고, 새로운 배열을 사용하기 시작해요.

.addAll(); 메서드 등이 호출되어서, 내부 배열을 1.5배 늘려도 그 안에 다 들어가지 않는다면 늘려야 할 만큼 늘러요.
내부 배열의 길이가 10이고, 이미 배열이 다 찬 상태라고 했을 때, 만약 값을 1개 추가한다면, 길이가 15인 배열을 새로 만들고 11번째 index로 값을 추가해요.

만약 값을 9개 추가한다면, 길이가 15인 배열을 새로 만들어도 안에 다 담지 못하니, 길이가 19인 배열을 만들고 그 배열 안에 값을 추가해요.
내부 배열의 초기 길이는 객체를 만들 때 정할 수 있어요.

public ArrayList(int initialCapacity);
//initialCapacity 내부 배열의 초기 길이

내부 배열의 초기 길이는 결정하지 않으면 10으로 설정될거에요.

내부 구현은 배열로 되어있기 때문에 index로 바로 접근할 수 있어서, 값에 접근하거나 값을 수정하기에 좋아요.
하지만, 중간에 새로운 값을 추가하면 그 뒤에 있는 값들이 다같이 뒤로 한 칸 밀려나고, 중간에 값을 아예 빼버리면 그 앞에 있는 값들이 다같이 앞으로 한 칸 밀려나야 하기 때문에, 삽입/삭제에는 영 좋지 못해요.

LinkedList

JDK 1.2에서 ArrayList와 함께 추가되었어요.
C언어 시간에 포인터와 구조체를 배운 뒤에 머리를 터트리면서 신나게 구현했던 그 LinkedList가 맞아요.

값을 저장할 변수와 다음 값이 어디에 있는지를 하나로 묶고, 그 묶음(노드)을 계속 연결하는 방식으로 구현하는 그거 맞아요.
내부 구현은 이중 연결 리스트로 되어있어요. 뒤로만 연결되어 있는게 아니라 앞으로도 연결되어있지요.

소스를 뜯어보면 어디서 많이 본 구조가 보여요. 노드에 저장할 값과, 이전 노드, 다음 노드의 위치.

새로 노드 만들어서 뒤에다가 붙이는 모습.

자바에는 포인터가 없는데, 어떻게 구현했는지 의문이 있을 수도 있지만, 포인터랑 비슷한건 있어요.
자바에서 new를 통해 만든 객체는 전부 힙 영역으로 들어가요. C/C++에서의 동적 할당이랑 같은 구조라고 보시면 될거에요.

C

Node* node = (Node*) malloc(sizeof(Node));
//힙 영역에 Node 구조체가 하나 들어갈 만큼 공간이 할당되고, 그 안에 구조체가 들어감
//그 구조체가 들어가있는 힙 영역이 어디인지 변수 node에 저장
//실제 주소로 저장되며, 나중에 free(node); 등을 통해 할당 해제를 해야 함

JAVA

Node node = new Node();
//힙 영역에 Node 객체가 하나 들어갈 만큼 공간이 할당되고, 그 안에 객체가 들어감
//그 객체가 들어가있는 힙 영역이 어디인지 변수 node에 저장
//포인터랑 비슷한 방식으로 저장되며, 나중에 다 쓰고나면 알아서 GC가 치움.

중간에 새로운 값을 추가하거나 삭제하여도 그냥 중간에 연결만 해주면 되는지라 삽입/삭제에는 유리해요.
하지만, index로 접근하기 위해서는, 앞에서부터 index만큼 이동하면서 가야 해서 값에 접근하거나 수정하기에는 영 좋지 못해요.

Vector

JDK 1.0 시절부터 있던 친구로, 완전 초기에는 ArrayList도 없고 LinkedList도 없었어요. 구버전 호환을 위해 남아있다는 소문도 있지만, JDK 내부에서도 Vector가 사용되는지라 확실한 소문인지는 모르겠어요.

동기화를 보장해요. 쓰레드가 여러 개 돌아가는 환경이라면 좋을 수도 있지만, 쓰레드가 하나만 돌아가는 환경이라면 오히려 성능 저하가 발생할 수도 있어요.
물론 동기화를 보장하기에 Thread Safe해요.

ArrayList처럼 내부는 배열로 되어있고, 내부 배열이 다 차면 배열의 길이를 두 배 늘려요.
정확히는 2배 더 긴 배열을 만들고, 원래 있던 배열에 저장된 내용을 새로 만든 배열로 옮겨요. 원래 쓰던 배열은 버리고, 새로운 배열을 사용하기 시작해요.

.addAll(); 메서드 등이 호출되어서, 내부 배열을 2배 늘려도 그 안에 다 들어가지 않는다면 늘려야 할 만큼 늘러요. 내부 배열의 길이가 10이고, 이미 배열이 다 찬 상태라고 했을 때,

만약 값을 1개 추가한다면, 길이가 20인 배열을 새로 만들고 11번째 index로 값을 추가해요.
만약 값을 14개 추가한다면, 길이가 20인 배열을 새로 만들어도 안에 다 담지 못하니, 길이가 24인 배열을 만들고 그 배열 안에 값을 추가해요.

내부 배열의 초기 길이는 객체를 만들 때 정할 수 있어요. ArrayList와는 달리, 내부 배열이 다 차면 얼마나 늘릴지도 정할 수 있어요.

public Vector(int initialCapacity, int capacityIncrement);
//initialCapacity 내부 배열의 초기 길이
//capacityIncrement 그 배열이 다 차면 늘어날 배열의 길이

내부 배열의 초기 길이를 따로 정하지 않는다면 10으로 생성될 것이고, 늘어갈 길이도 따로 정하지 않는다면 두 배로 늘어날꺼에요.
물론, 늘리라고 한 만큼 늘려도 추가하려는 값이 내부 배열 안에 다 들어가지 않는다면, 늘려야 할 만큼 늘러요.

내부 구조는 ArrayList와 사실상 동일하기 때문에, 장단점도 똑같아요.

Stack

사실 Stack 클래스도 List를 implements 해요.
정확히는 List를 implements한 Vector를 상속받아요.

.push();나 .pop();과 같은 스택에 있을 법할 메서드들이 추가로 존재할 뿐, 내부 구조는 Vector와 같아요.

Vector와 ArrayList는 어디까지 늘어날까?

안에 들어있는 내부 배열의 길이는 SOFT_MAX_ARRAY_LENGTH까지 늘어나요.
내부 배열의 길이를 1.5배든 2배든 사용자가 지정한 만큼이든 늘렸을 때, SOFT_MAX_ARRAY_LENGTH보다 더 크게 늘려야 한다면 SOFT_MAX_ARRAY_LENGTH까지만 늘러요.

SOFT_MAX_ARRAY_LENGTH는 int형 최대값에서 8을 뺀 값인 2147483639에요.

보시다싶이 이미 최대치로 늘어난 상태에서 더 늘리는 것을 시도하면 OutOfMemoryError가 발생해요.

Vector와 ArrayList에 저장되어 있는 요소를 삭제하면 내부 배열의 길이도 줄어들까?

ArrayList나 Vector 안에 있는 값을 뺀다고해서 내부 배열의 길이도 줄어들지는 않아요.

그냥 null만 넣고 끝나요. 원래 있던 객체는 GC가 알아서 치워줄거에요.
.clear(); 메서드를 호출하여도 내부 배열의 길이는 변하지 않고, 전부 null로 채워버려요.

.trimToSize(); 메서드를 동해 내부 배열 뒤에 있는 빈 공간들을 삭제하여, 내부 배열의 길이를 줄일 수는 있어요.