[Java] ArrayList와 LinkedList

ArrayList와 LinkedList를 알아보기 전에 두 가지를 묶어주는 상위 컬렉션인 List 컬렉션에 대해서 알아보자.

List 컬렉션은 배열과 비슷하게 객체를 인덱스로 관리한다.
배열과의 차이점은 저장 용량이 자동으로 증가하며, 객체를 저장할 때 자동으로 인덱스가 부여된다는 것이다.

List 컬렉션은 객체 자체를 저장하는 것이 아니라 객체의 번지를 참조한다. 그렇기 때문에 동일한 객체를 중복 저장할 수 있고, 이 경우 동일한 번지가 참조된다.
null 또한 저장이 되고, 이 경우 해당 인덱스는 객체를 참조하지 않는다.

객체를 저장함이 아니라 번지를 참조

List 컬렉션에 객체를 추가할 때는 add() 메소드를 사용하고
객체를 찾아올 때는 get() 메소드,
객체를 삭제할 때는 remove() 메소드를 사용한다.

List<String> list = ...;
list.add("홍성인");			//맨 끝에 객체 추가
list.add(1, "홍길동");			//지정된 인덱스에 객체 삽입
String str = list.get(1);		//인덱스로 객체 검색
list.remove(0);				//인덱스로 객체 삭제
list.remove("홍길동");			//객체 삭제

이제 기본적인 List의 사용 방법에 대해 알았으니 ArrayList부터 알아보도록 하자.

ArrayList

ArrayList는 List 인터페이스의 대표적인 구현 클래스이다.

List<E> list = new ArrayList<E>();	//E에는 타입 파라미터가 들어간다.(ex/ String, int, etc.)
List<E> list = new ArrayList<>();	//E에 선언된 타입이 ArrayList에도 동일한 파라미터를 지정해준다.

ArrayList는 생성할 때 E 객체 10개를 저장할 수 있는 초기 용량을 가진다.

ArrayList에 객체를 추가하면 0번 인덱스부터 차례대로 저장된다.
ArrayList에서 특정 인덱스의 객체를 제거하면 바로 뒤 인덱스부터 마지막 인덱스까지 모두 앞으로 1씩 당겨진다.
마찬가지로 특정 인덱스에 삽입을 하면 해당 인덱스부터 마지막 인덱스까지 모두 1씩 밀려진다.

인덱스가 삭제될 경우 앞으로 1씩 당겨진다.

이러한 동작 때문에 저장된 객체 수가 많고, 특정 인덱스에 객체를 추가/제거하는 일이 빈번하다면 LinkedList를 사용하는 것이 효율적이라 할 수 있다.
하지만 인덱스를 이용해 객체를 찾거나 맨 마지막에 객체를 추가하는 경우에는 ArrayList가 더 좋은 성능을 발휘한다.

 

LinkedList

LinkedList는 ArrayList와 사용 방법은 같지만 내부 구조는 완전히 다르다.
ArrayList는 내부 배열에 객체를 저장해서 관리하지만, LinkedList는 인접 참조를 링크해서 체인처럼 관리한다.

LinkedList의 구조

LinkedList에서 특정 인덱스의 객체를 제거하면 앞 뒤 링크만 변경되고 나머지 링크는 변경되지 않는다. 특정 인덱스에 객체를 삽입할 때도 마찬가지다.

중간의 객체 제거 시 앞 뒤 링크의 수정만 일어나게 된다.

위에서도 설명했듯이, 빈번하게 추가/삭제가 일어나는 경우에는 ArrayList보다 LinkedList가 좋은 성능을 발휘하게 된다.

List<E> list = new LinkedList<E>();
List<E> list = new LinkedList<>();	//ArrayList와 마찬가지로 E 타입 파라미터를 생략하면 왼쪽의 파라미터를 따라간다.

LinkedList 생성은 ArrayList와 같은 방식으로 선언하면 된다.
LinkedList가 처음 생성될 때에는 어떠한 링크도 만들어지지 않기 때문에 내부는 비어있다고 보면 된다.

아래 예제를 통해 ArrayList와 LinkedList의 성능을 비교해보도록 하자.
각각 10,000개의 객체를 삽입하는데 걸린 시간을 측정한 것이다.

package sec01.exam03;

import java.util.*;

public class LinkedListEx {

	public static void main(String[] args) {
		List<String> list1 = new ArrayList<String>();
		List<String> list2 = new LinkedList<String>();
		
		long startTime;
		long endTime;
		
		startTime = System.nanoTime();
		for(int i=0; i<10000; i++) {
			list1.add(0, String.valueOf(i));
		}
		endTime = System.nanoTime();
		System.out.println("ArrayList의 걸린 시간 : " + (endTime - startTime) + "ns");
		
		startTime = System.nanoTime();
		for(int i=0; i<10000; i++) {
			list2.add(0, String.valueOf(i));
		}
		endTime = System.nanoTime();
		System.out.println("LinkedList의 걸린 시간 : " + (endTime - startTime) + "ns");
	}

}

실행 결과

0번 인덱스에 String 객체를 10,000번 추가하기 위해 List 인터페이스의 add(int index, E elemet) 메소드를 이용했다.
실행 결과를 보면 LinkedList가 약 5배 가량 빠른 성능을 발휘하는 것을 볼 수 있다.

끝에서부터 추가/삭제하는 경우는 ArrayList가 빠르지만, 중간에 추가/삭제하는 경우에는 앞 뒤 링크 정보만 변경하면 되는 LinkedList가 더 빠르다.
ArrayList는 뒤쪽 인덱스들을 모두 1씩 증가/감소 시키는 시간이 필요하므로 처리 속도가 느리다.

각 성능면을 비교하면 아래 표와 같다.

구분	순차적으로 추가/삭제	중간에 추가/삭제	검색
ArrayList	빠르다	느리다	빠르다
LinkedList	느리다	빠르다	느리다