ArrayList 와 LinkedList +@

2017-02-19

2021-10-07

ArrayList, Collections, LinkedList, java

이 포스트에서는 ArrayList와 LinkedList에 대해 알아 보겠습니다.

List는 특정 타입 값들이 순차적으로 정렬된 컬렉션Collection 입니다.

리스트는 크기 지정에 한계가 없으므로 아래 코드에서와 같이 리스트를 사용하기 전에 크기를 지정할 필요가 없습니다.

@Test
public void arrayAndList() {
    // 배열의 명시적 크기 지정
    int[] integers = new int[10];
    // 배열의 암시적 크기 지정
    String[] strings = new String[]{"one","two","three"};
    // 리스트 선언
    List<String> stringList = new ArrayList<String>();
}

공식 문서는 한번씩 훑어보는 습관을 들이는게 좋습니다.

ArrayList (Java Platform SE 8 )

LinkedList (Java Platform SE 8 )

사실 ArrayList와 LinkedList 말고도 List 인터페이스를 implements 한 클래스들은 아래와 같이 더 있습니다

AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector

하지만 이런것들은 잘 쓰이지 않으니 한번씩 눌러서 훑어 보고 지나가도 좋을것 같습니다.
(RoleList, RoleUnresolvedList 는 저런게 있는지도 몰랐네요)

2018-01-11 추가 : CopyOnWriteArrayList의 경우 Concurrent programming에서 많이 쓰이니 나중에 다시 한번 다뤄보도록 하겠습니다.

ArrayList와 Linked 리스트의 차이점과 특징

ArrayList 는 이름 그대로 Array(배열) 의 특징을 가지고 있는 리스트 입니다.

Pros: Random Access 가 가능하다는 점
Cons: ArrayList의 처음이나 중간에 값을 insert 하는 경우
메모리 상에서는 insert한 이후의 모든 값들을 뒤로 한칸씩 이동하는 작업이 일어 납니다. 리스트의 크기가 매우 큰 경우 이 작업은 굉장히 비싼 작업이 될 수 있습니다. (내부적으로는 실제로 한칸씩 미루는 작업은 새로운 배열을 만드는 작업으로 이뤄집니다. )

LinkedList는 객체에 이전노드와 다음노드의 주소를 가지고 있는 공간을 추가로 할당해서 가지고 있습니다.

Pros: 리스트의 크기가 클 경우 중간에 삽입이나 삭제를 하는 작업이 훨씬 빠르고 임시공간을 필요로 하지 않습니다.
Cons: 이전노드와 다음노드의 주소를 가지고 있는 공간 때문에 일반적으로 ArrayList보다 메모리를 더 많이 사용합니다. RandomAccess가 불가 합니다.

Java는 기본적으로 Doubly linked 되어 있는 구조를 가져가기 때문에 이전과 다음값 모두의 주소를 가지고 있습니다.

5라는 값을 리스트에서 삭제한 경우 33 이 가지고 있던 다음값의 주소에 7을 넣고, 7이 가지고 있던 이전값의 주소에 33의 주소값을 넣게되면 5는 아무곳에서도 참조되지 않는 쓰레기 객체가 됩니다.

삽입이 일어나는 경우에도 마찬가지로 이전값, 다음값의 주소값만 변경 되기 때문에 ArrayList에서처럼 삽입된 값 이후의 모든 값이 한칸씩 밀릴 필요가 없습니다.

위의 그림과 설명만 봐서는 ArrayList가 LinkedList 보다 나은 점이 없는것 같아 보입니다.

ArrayList 는 내부 인덱스를 가지고 있어 Random Access가 가능 하지만
LinkedList는 내부 인덱스는 가지고 있지 않으므로 원하는 값을 찾으려면 앞에서 부터 순차적으로
다음값의 주소를 찾아가야 합니다.

@Test
public void randomAccess() {

	List<String> arrayList = new ArrayList<>();
	arrayList.add("first");
	arrayList.add("second");
	arrayList.add("third");

	assertEquals("first", arrayList.get(0));
	assertEquals("second", arrayList.get(1));

	List<String> linkedList = new LinkedList<>();
	linkedList.add("first");
	linkedList.add("second");
	linkedList.add("third");

	assertEquals("first", linkedList.get(0));
	assertEquals("second", linkedList.get(1));

}

위 테스트 케이스의 결과를 보면 LinkedList도 RandomAccess가 가능한것 처럼 보입니다. (linkedList.get(0)등을 통해)

하지만 RandomAccess (Java Platform SE 8 ) 페이지를 통해 알 수 있듯이 하지만 위의 문서에 나와 있듯이

Interface RandomAccess

All Known Implementing Classes:

ArrayList, AttributeList, CopyOnWriteArrayList, RoleList, RoleUnresolvedList, Stack, Vector

LinkedList는 RandomAccess를 implementing 하고 있지 않습니다.
결국 get(index)를 호출 하더라도 내부적으로는 위에서 설명한 방식대로 순차적으로 탐색하여 그 결과를 가져 옵니다.

+@ : Vector

Vector는 JDK1.0 때부터 존재했던 고전 List 입니다.
Vector (Java Platform SE 8 )
기본적으로 자바의 배열이 고정 길이를 사용하기 때문에 사이즈를 미리 예측 할 수 없는 자료를 담기 위해 만들어진 클래스 이라고 할 수 있습니다.
이후 JDK1.2에서 ArrayList가 소개되면서 Vector는 사실상 사용되지 않는 클래스라고 봐도 무방합니다.
Vector는 Serializable을 implementing 하고 있습니다. 그 말인 즉슨 내부적으로 동기화가 되어 있다는 말이고 동기화가 되어 있다는 말은 Thread safe 하다는 말이기도 하지만 동기화를 하고 있기 때문에 속도가 느립니다.
싱글 스레드를 사용하는 프로그램에서는 쓰면 안되겠고, 병렬 프로그래밍을 하더라도 java.util.concurrent 패키지에 포함되어 있는 CopyOnWriteArrayList 등을 사용하는게 바람직 합니다.
(이 부분은 나중에 기회가 되면 좀 더 자세히 다루도록 하겠습니다.)

Developmentjava

ArrayList와 Linked 리스트의 차이점과 특징

+@ : Vector