[Java/Collection] ArrayList 와 LinkedList

최지수·2022년 4월 28일
0

Java

목록 보기
20/27
post-thumbnail

Collection Framework
데이터 군을 저장하는 클래스들을 표준화한 설계를 의미해요. 다수의 데이터 그룹들을 관리하는 표준화된 프로그래밍 방식을 말해요.

자바에선 다수의 데이터를 다루는데 필요한 다양하고 풍부한 클래스들을 제공하며, 인터페이스와 다형성을 이용한 객체지향적 설계를 통해 표준화되어 있기 때문에 재사용성이 높은 코드를 제공해요.

들어가기 전에 앞서, List 인터페이스부터 알아봐요

List 인터페이스는 중복을 허용하면서 저장순서가 유지되는 collection 을 구현하는데 사용되요. 이번에 다룰 ArrayListLinkedList는 해당 인터페이스를 상속 받아 저장 순서가 유지되는 데이터 그룹을 생성해요. 참고로 이러한 데이터 그룹 관련 클래스는 Collection 인터페이스를 상속해요.

ArrayList

가장 많이 사용되는 collection framework이에요. List 인터페이스를 상속하기 때문에 데이터의 저장순서가 유지되고 중복을 허용해요.

ArrayList는 Object 배열을 이용해서 데이터를 순차적으로 저장해요. 첫 번째 저장 객체는 배열의 0번째 인덱스에 저장되고, 그 다음은 1번째에 저장하는 방식이에요. 만약 배열에 더이상 저장할 공간이 없으면 보다 큰 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장되요. 그래서 가급적이면 사용될 수 있는 최대 크기를 예측해서 미리 크기를 지정하고 사용하는게 성능적인 면에서 좋아요.

// 미리 capacity(크기)를 2로 지정해줘요.
ArrayList list = new ArrayList(2);
list.add(1);
list.add(1);	// 중복 허용
list.add(2);	// capacity가 2라서 내부적으로 배열을 새로 만들어요.

자바에선 Vector라는 ArrayList와 동일한 기능과 구현원리를 가진 클래스가 존재해요. 하지만, ArrayList가 개선된 클래스이고 Vector의 경우 기존에 작성된 소스를 유지하는 차원에서 남겨둔 것이라 ArrayList를 사용하는 것을 권장해요.

제공되는 인터페이스를 모두 알기 위해선 자바 레퍼런스를 참고하는게 좋을 거에요. 여기는 유용하다고 생각하는 부분만 작성할게요 ㅎㅎ.

add/remove

데이터를 추가하거나 삭제해요. remove의 경우 매개변수가 삭제 대상 객체일 수도 있고 배열 인덱스가 될 수 있어요. remove할 때 주의할 점은 for 문으로 순회하면서 특정 조건에서 remove를 수행하게 되면 인덱스가 실시간으로 변경되어 적절한 예외 처리가 없으면 의도하지 않은 결과가 발생할 수 있어요. 그러니 사용 시 주의해야해요.

List<Integer> list1 = new ArrayList<Integer>();
for(int i = 0 ; i < 10; ++i){
    list1.add(i);
}
for(int i = 0; i < list1.size(); ++i){
	// 0을 포함한 2의 배수만 삭제
    if(i % 2 == 0)
        list1.remove(i);
}
System.out.print(list1);	// [1,2,4,5,7,8] 의도치 않은 결과...!

// 따라서, 아래와 같이 remove가 일어난 시점엔 인덱스를 유지시켜요.
// remove가 됨에 따라 다음 인덱스가 -1이 발생했기 때문이에요.
for(int i = 0; i < list1.size();){
	Integer value = list1.get(i);	// get을 통해 해당 인덱스 데이터를 가져와요
	if(value % 2 == 0)
		list1.remove(i);
	else
		++i;
}
System.out.print(list1);	// [1,3,5,7,9]

get/set

get은 해당 인덱스의 데이터를 가져와요. C++에선 []operator를 통해 가져올 수 있었는데, 자바는 메서드화 시켜서 가져오네요 ㅎㅎ. 그러다보니 get는 데이터를 가져올 뿐이지, 변경시킬 수 없어요. 변경을 하기 위해선 set 메서드를 사용해야 해요.

// list1.get(i) = 5;                // 이렇게 변경할 수 없어요.
System.out.print(list1.get(i) + ", ");
list1.set(i, list1.get(i) + 1);     // 이렇게 해줘야 해요.

containsAll

매개변수로 받는 Collection 변수와 비교해서 해당 매개변수 내 데이터가 모두 포함하고 있는지를 확인해요.

List list1 = ArrayList(); 	// 1, 2, 3, 4, 5
List list2 = ArrayList(); 	// 1, 2, 3
List list3 = ArrayList(); 	// 1, 2, 3, 6

list1.containsAll(list2); 	// true
list1.containsAll(list3); 	// false

retainAll

매개변수로 받는 Collection 변수와 비교해서 해당 매개변수 내 데이터와 겹치는 부분만 남기고 나머질 삭제해요. 삭제된 부분이 존재했다면 true를 반환하고, 그렇지 않으면 false를 반환해요.

List는 중복이 허용되는데 삭제가 되는 기준이 아직 이해가 되진 않네요 ㅎㅎ... 데이터 순서가 동일하면 true를 반환하지만, 순서가 다를 경우 false를 반환하게 되요. 이 부분은 좀 더 알아보고 나서 다시 정리할게요.


List<Integer> list1 = new ArrayList<Integer>();
list1.add(1);
list1.add(1);
list1.add(2);
list1.add(3);
List<Integer> list2 = new ArrayList<Integer>();
list2.add(1);
list2.add(1);
list2.add(2);
System.out.println(list1.retainAll(list2) + " " + list1); 	// true, list1 = [1,1,2]
list1 = new ArrayList<Integer>();
list1.add(1);
list1.add(1);
list1.add(2); 
list2 = new ArrayList<Integer>();
list2.add(1);
list2.add(2);	// 순서를 바꿨어요
list2.add(1);
System.out.println(list1.retainAll(list2) + " " + list1); 	// false, list1 = [1,1,2]

LinkedList

대표적인 자료구조인 링크드 리스트 collection 클래스에요. 링크드 리스트에 대한 개념은 여기를 보시면 될 것 같아요.

실제로 LinkedList는 해당 글에서 정리된 단방향 링크드 리스트가 아닌 더블 써큘러 링크드 리스트Double Circular Linked List 자료구조를 활용해요. 정방향 뿐만 아니라 역방향 접근도 용이하게 하기 위한 개선된 자료구조에요. 이 내용은 추후에 다루도록 할게요ㅎㅎ.

각설하고, ArrayList나 배열Array는 데이터를 읽는 시간이 인덱스를 찾아 접근하기 때문에 가장 빠르지만 한계가 존재해요.

ArrayList의 한계점
1. 크기를 변경할 수 없어요
변경할 수 없기 때문에 공간이 필요하면 새로운 배열을 생성해서 데이터를 복사하는 과정을 거쳐요. 그렇다고 실행 속도를 개선한다고 배열을 크게 늘려버리면 불필요한 메모리가 낭비되요

2. 비순차적인 데이터 추가 또는 삭제가 시간이 걸려요
차례대로 데이터를 추가하거나, 마지막에서부터 삭제하는 건 빨라요. 하지만 중간에 데이터를 삽입해야 하는 경우엔 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야 해요

링크드 리스트의 경우, 배열이 아닌 데이터와 근접 노드에 대한 정보를 담은 비연속성 자료구조이기 때문에, 삽입하거나 삭제할 땐 데이터를 담은 노드를 생성하고 근접 노드에 대한 정보를 적절히 갱신하면 되기 때문에 빨라요. 대신, 접근을 하기 위해선 첫 번째 노드부터 순차적으로 접근해야하기 때문에 ArrayList보다 느려요.

ArrayList vs. LinkedList

이론적으로 설명드렸으니, 실제로 돌려보면서 비교해봐요.

추가, 삽입, 삭제

public static void execute() {
    ArrayList a1 = new ArrayList<>(20_000_000);
    LinkedList l1 = new LinkedList<>();

    System.out.print("순차적 추가");
    System.out.println("ArrayList : " + add1(a1));
    System.out.println("LinkedList : " + add1(l1));

    System.out.print("중간에 삽입");
    System.out.println("ArrayList : " + add2(a1));
    System.out.println("LinkedList : " + add2(l1));

    System.out.print("중간에 삭제");
    System.out.println("ArrayList : " + remove2(a1));
    System.out.println("LinkedList : " + remove2(l1));

    System.out.print("순차적 삭제");
    System.out.println("ArrayList : " + remove1(a1));
    System.out.println("LinkedList : " + remove1(l1));
}

private static long add1(List list) {
    long start = System.currentTimeMillis();
    for(int i = 0 ; i < 1_000_000; ++i) list.add(i + "");
    long end = System.currentTimeMillis();
    return end - start;
}
   
private static long add2(List list) {
    long start = System.currentTimeMillis();
    for(int i = 0 ; i < 10_000; ++i) list.add(500, "X");
    long end = System.currentTimeMillis();
    return end - start;
}

private static long remove1(List list) {
    long start = System.currentTimeMillis();
    for(int i = list.size() - 1; i >= 0 ; --i) list.remove(i);
    long end = System.currentTimeMillis();
    return end - start;
}

private static long remove2(List list) {
    long start = System.currentTimeMillis();
    for(int i = 0 ; i < 10_000; ++i) list.remove(0);
    long end = System.currentTimeMillis();
    return end - start;
}

여기서 알 수 있는 사실은,

1. 순차적 추가/삭제는 ArrayList가 더 빨라요
물론 위 예제는 추가하는 과정에서 배열을 확장하는 처리를 배제하기 위해 일부러 크기를 크게 잡아놨어요. 만약 따로 크기를 지정해주지 않는다면 배열을 생성해서 복사하는 작업이 있으므로 LinkedList가 더 빠를 수도 있어요.

순차적 삭제는 마지막 데이터부터 역순으로 진행하는 의미로, 각 요소들의 재배치가 필요하지 않아서 ArrayList도 마찬가지로 빨라요.

2. 중간에 데이터 추가(삽입)/삭제는 LinkedList가 더 빨라요
이 경우 LinkedList는 각 요소간의 연결만 변경만 해주면 되서 처리 속도가 빨라요. ArrayList의 경우 각 요소들을 재배치해서 추가할 공간을 확보하거나 빈 공간을 채워야하기 때문에 느려요

접근(Access)

public static void execute() {

    ArrayList a1 = new ArrayList<>(20_000_000);
    LinkedList l1 = new LinkedList<>();

    add(a1);
    add(l1);

    System.out.print("접근시간 테스트");
    System.out.println("ArrayList : " + access(a1));
    System.out.println("LinkedList : " + access(l1));
}

private static long add(List list) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < 1_000_000; ++i)
        list.add(i + "");
    long end = System.currentTimeMillis();
    return end - start;
}

private static long access(List list) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < 10_000; ++i)
        list.get(i);
    long end = System.currentTimeMillis();
    return end - start;
}

접근은 ArrayList가 압도적으로 빨라요. 단순히 배열의 주소 + n * 데이터 타입의 크기로 접근하면 되기 때문이에요. LinkedList는 아까 언급했듯이, 초기 노드부터 순차적으로 접근하기 때문에 느릴 수 밖에 없어요.

그래서 중복 데이터를 허용하는 collection 클래스를 사용할 때 아래와 같은 조건을 고려해서 사용하시면 최적화를 기대할 수 있어요.

Collection접근추가 및 삭제비고
ArrayList빠름느림순차적인 추가/삭제는 더 빠르나 비효율적인 메모리 공간 차지
LinkedList느림빠름데이터가 많을 수록 접근성 떨어짐

물론 Collection에 속한 대부분의 클래스들은 서로 변환이 가능한 생성자를 제공하니까, 상황에 따라 적절히 대처가 가능하니 참고하세요~

참고

넥스트리소프트 - 링크드리스트

profile
#행복 #도전 #지속성

0개의 댓글