ArrayList, LinkedList 정리 및 비교

ArrayList와 LinkedList는 모두 List 인터페이스를 구현하는 클래스들이다. (List 인터페이스는 자바의 컬렉션 프레임워크에서 Collection 인터페이스를 구현하는 인터페이스이다. 프레임워크와 Collection 인터페이스에 대해 궁금하다면 아래에 링크를 걸어 놓을테니 참고하길 바란다.)

ckprk.tistory.com/27

[자바] 컬렉션 프레임워크 [Collection 인터페이스]

 

List 인터페이스를 구현하는 대표적인 제네릭 클래스인 ArrayList와 LinkedList는 다음 두가지 특성을 공통으로 지닌다.

 

▶동일한 인스턴스의 중복 저장을 허용한다.

▶인스턴스의 저장 순서가 유지된다.

 

이 둘의 사용방법은 거의 동일하다. 다만 데이터를 저장하는 방식에서 큰 차이를 보인다. 이와 관련해서는 ArrayList와 LinkedList 사용방법을 각각 살펴보고 설명하겠다.

 

import java.util.ArrayList;

public class IntroArrayList {

	public static void main(String[] args) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		System.out.println("1차 참조");
		list.add(1);
		list.add(2);
		list.add(3);
		System.out.println(list);
		
		System.out.println("2차 참조");
		list.remove(0);
		System.out.println(list);
	}
}

1차 참조
[1, 2, 3]
2차 참조
[2, 3]

Integer를 기반으로 ArrayList의 인스턴스를 생성하고 있다. 따라서 생성한 list라는 인스턴스는 Integer형의 인스턴스를 받는 저장소로 사용된다.

또한 add 메서드를 통해 세개의 인스턴스를 저장하고 있는 것을 볼 수 있다. 1차 참조 출력값을 보면 알 수 있듯이 순차적으로 저장된다는 것이다. 즉, 저장 순서가 ArrayList<Integer> 인스턴스 내에서 유지된다고 할 수 있다.

 

기본적으로 알고 있어야 하는 데이터의 저장, 참조 및 삭제 방법을 간단히 보였다. 이와 같이 ArrayList 클래스는 배열과 상당히 유사하다 하지만 데이터의 저장을 위해서 인덱스 정보를 별도로 관리할 필요가 없고, 데이터의 삭제를 위한 추가적인 코드의 작성이 전혀 필요 없다. 또한 저장되는 인스턴스의 수에 따라서 그 크기도 자동으로 늘어나고 줄어들기 때문에 이러한 면에서는 배열보다 편이하다고 할 수 있다.

 

이번에는 LinkedList 클래스의 사용방법을 살펴보겠다.

import java.util.LinkedList;

public class IntroArrayList {

	public static void main(String[] args) {
		LinkedList<Integer> list = new LinkedList<Integer>();
		
		System.out.println("1차 데이터");
		list.add(1);
		list.add(2);
		list.add(3);
		System.out.println(list);
		
		System.out.println("2차 데이터");
		list.remove(0);
		System.out.println(list);
	}
}

1차 데이터
[1, 2, 3]
2차 데이터
[2, 3]

 

ArrayList와 유일한 차이점은 import선언 부분과 LinkedList<Integer> list = new LinkedList<Integer>(); 이부분임을 알 수 있다. 이렇듯 ArrayList와 LinkedList 클래스 사이에서의 선택 기준은 사용방법 차이가 아닌, 내부적으로 인스턴스를 저장하는 방식의 차이에 있다.

 

LinkedList는 배열을 사용하는 대신에 서로서로 연결하는 방식으로 데이터를 저장한다. 이는 이해하기 위해 다음 코드를 제시한다. 이 코드는 LinkedList를 사용하는 것이 아닌 LinkedList의 데이터 저장방식을 이해하기 위한 코드이다.

class Box<T>{ //인스턴스를 담을 '상자' 클래스 (배열을 대신함)
	public Box<T> nextBox; //상자들을 연결하기 위한 참조변수. 이 변수를 이용해서 Box<T>의 인스턴스는 동일한 자료형의 인스턴스를 참조하게 된다.
	T item;
	
	public void store(T item) {this.item=item;} //인스턴스를 저장하기 위한 메서드
	public T pullOut() {return item;} //받은 인스턴스를 반환하는 메서드
}

public class LinkedListEx {

	public static void main(String[] args) {
		Box<String> box = new Box<String>(); //box를 생성
		box.store("First thing"); //만든 box에 문자열을 담음
		
		box.nextBox = new Box<String>(); // 두번째 box 생성
		box.nextBox.store("Second thing"); // 두번째 box에 문자열 담음
		
		box.nextBox.nextBox = new Box<String>(); //세번째 box 생성
		box.nextBox.nextBox.store("Third thing"); // 세번째 box에 문자열 담음
		
		System.out.println(box.pullOut());  //첫번째 박스에 담긴 인스턴스 출력
		System.out.println(box.nextBox.pullOut()); //두번째 박스에 담긴 인스턴스 출력
		System.out.println(box.nextBox.nextBox.pullOut()); //세번째 박스에 담긴 인스턴스 출력
	}
}

First thing
Second thing
Third thing

 

이렇게 연결 되어있는 상자들에 데이터가 저장되는 모습을 볼 수 있다. 이를 통해 LinkedList의 특성을 파악할 수 있다.

저장소를 늘리는 것은 마치 블록을 하나 연결하는 것과 마찬가지로 그 과정이 간단하고 데이터의 삭제 역시 매우 간단하다. 위의 코드에서는 보이진 않았지만 중간에 위치한 상자하나를 삭제하는 것은 어려운 일이 아니다. 하지만 데이터의 참조는 불편하다. 참조를 위해서는 위와 같이 연결되어있는 상자들을 통해 이동을 해야하기 때문이다.

 

따라서 총 정리해 보면, ArrayList는 배열을 기반으로 하지만 LinkedList는 배열이 아닌 연결방식이다.

 

ArrayList

▶장점 : 데이터의 참조가 용이해서 빠른 참조가 가능하다.

▶단점 : 저장소의 용량을 늘리는 과정에서 많은 시간이 소요된다.

                  데이터의 삭제에 필요한 연산과정이 매우 길다.

 

LinkedList

▶장점 : 저장소의 용량을 늘리는 과정이 간단하다.

                  데이터의 삭제가 매우 간단하다.

▶단점 : 데이터의 참조가 다소 불편하다.

 

 

그러면 마지막으로 다음의 상황에서 둘중 어떤 클래스를 사용해야하는지 판단해보자

 

상황1 : 저장하게 되는 데이터의 수가 대략적으로 예측 가능하며, 빈번한 데이터의 참조가 일어나는 상황에서 유용하게 사용할 수 있는 컬렉션 클래스는 무엇인가?

 

상황2 : 저장하게 되는 데이터의 수가 예측 불가능하며, 빈번한 데이터의 저장 및 삭제가 일어나는 상황에서 유용하게 사용할 수 있는 컬렉션 클래스는 무엇인가?

 

 

답

상황1 : ArrayList 클래스

상황2 : LinkedList 클래스