[Java] - List / ArrayList / LinkedList

List 인터페이스

• 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현
  

---

ArrayList

• List 인터페이스 구현 클래스
  • 저장순서 유지, 중복 허용
• 컬렉션 프레임워크에서 가장 많이 사용되는 컬렉션 클래스
• 일반 배열과 인덱스로 객체를 관리한다는 점이 비슷
  • 배열은 생성할 때 크기가 고정
  • ArrayList는 저장 용량(capacity)을 초과한 객체들이 들어오면 자동으로 저장 용량이 늘어남
• 기존의 Vector를 개선한 것으로 Vector와 구현원리와 기능적인 측면에서 동일
  • Vector보다는 ArrayList를 사용할 것(Vector는 호환성을 위해 남겨둠)

간단하게 ArrayList 사용법을 알아보자.

List<String> list = new ArrayList<>();
list.add("hello");
list.add("cat");
list.add("hi");
list.add("dog");
list.add("good");
list.add("friends");

System.out.println(list.size());   //  6
System.out.println(list.get(3));   //  dog
list.remove(3);
list.remove("cat");
System.out.println(list);   //  [hello, hi, good, friends]

ArrayList를 생성하고 런타임 시 객체들을 추가하는 것이 일반적이지만, 고정된 객체들로 구성된 List를 생성할 때도 있다.
이럴 때는 Arrays.asList(T... a) 메소드를 사용하면 된다.

List<String> companies = Arrays.asList("google", "apple", "samsung");
System.out.println(companies);  //  [google, apple, samsung]

List<Integer> numbers = Arrays.asList(1, 10, 100);
System.out.println(numbers);  //  [1, 10, 100]

---

LinkedList

배열은 구조가 간단하고 사용하기 쉽고, 데이터 조회 시간이 가장 빠르다는 장점을 갖고 있지만
아래와 같은 단점이 존재한다.

1. 크기를 변경할 수 없다.
2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.

배열의 단점을 보완하기 위해서 링크드 리스트(LinkedList) 라는 자료구조가 생겼다.

배열은 모든 데이터가 연속적으로 존재하지만 링크드 리스트는
불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어있다.

출처 : https://www.faceprep.in/data-structures/linked-list-vs-array/

링크드 리스트의 각 요소(node) 들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어있다.

class Node {
    Node    next;   //  다음 요소의 주소 저장
    Object  obj;    //  데이터 저장
}

링크드 리스트에서의 데이터 추가, 삭제는 간단하다.

추가

A -> B -> D

• B 와 D 노드사이에 'C' 노드를 추가

1. C 노드 생성
2. B의 다음 노드 참조를 D -> C로 변경
3. C의 다음 노드 참조를 D로 적용
   

A -> B -> C -> D

삭제

A -> B -> C

• 'B' 노드 삭제

1. A의 다음 노드 참조를 B -> C로 변경

A -> C

중간에 데이터 추가/삭제의 경우 링크드 리스트가 배열보다 훨씬 나은 성능을 보여준다.

더블 링크드 리스트

링크드 리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만, 이전요소에 대한 접근은 어렵다.
이 점을 보완한 것이 더블 링크드 리스트(이중 연결리스트, doubly linked list) 이다.

출처 : https://medium.com/journey-of-one-thousand-apps/data-structures-in-the-real-world-508f5968545a

단순히 링크드 리스트에 이전 요소에 대한 참조변수를 하나 더 추가한 것이다.

class Node {
    Node    next;       //  다음 요소의 주소 저장
    Node    previous;   //  이전 요소의 주소 저장
    Object  obj;        //  데이터 저장
}

더블 링크드 리스트는 링크드 리스트보다 각 요소에 대한 접근, 이동이 쉽기 때문에 더 많이 사용된다.

더블 링크드 리스트의 접근성을 향상시킨 것이
'더블 써큘러 링크드 리스트(이중 원형 연결리스트, doubly circular linked list)' 인데
더블 링크드 리스트의 첫 번째 노드와 마지막 노드를 연결시킨 형태이다.
-> TV의 마지막 채널에서 채널을 증가하면 첫 번째 채널로 이동하는 것과 같다.

실제로 자바의 LinkedList 클래스는 이름과 달리 '링크드 리스트'가 아닌 '더블 링크드 리스트로' 로 구현되어있다.

LinkedList 내부 코드를 살펴보면 다음과 같이 이전과 다음 요소 모두 참조가능한 형태이다.

// LinkedList.java
public class LinkedList<E>
  ...
  private static class Node<E> {
      E item;
      Node<E> next;
      Node<E> prev;

      Node(Node<E> prev, E element, Node<E> next) {
          this.item = element;
          this.next = next;
          this.prev = prev;
      }
  }
  ...
}

이유는 위에서 설명했듯이 링크드 리스트의 단점인 낮은 접근성을 높이기 위한 것이다.

---

ArrayList vs LinkedList

예제코드를 통해서 ArrayList와 LinkedList의 차이에 대해 살펴보자.

추가/삭제

실행

public static void main(String[] args) {
    List<String> al = new ArrayList<>(2000000);
    List<String> ll = new LinkedList<>();

    System.out.println("=====순차적 추가=====");
    System.out.println("ArrayList : " + add1(al));
    System.out.println("LinkedList : " + add1(ll));
    System.out.println("=====중간 추가=====");
    System.out.println("ArrayList : " + add2(al));
    System.out.println("LinkedList : " + add2(ll));
    System.out.println("=====중간 삭제=====");
    System.out.println("ArrayList : " + remove2(al));
    System.out.println("LinkedList : " + remove2(ll));
    System.out.println("=====순차적 삭제=====");
    System.out.println("ArrayList : " + remove1(al));
    System.out.println("LinkedList : " + remove1(ll));
}

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

private static long add2(List<String> list) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        list.add(5000,i + "");
    }
    long end = System.currentTimeMillis();
    return end - start;
}

private static long remove1(List<String> 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<String> list) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        list.remove(i);
    }
    long end = System.currentTimeMillis();
    return end - start;
}

결과

=====순차적 추가=====
ArrayList : 99
LinkedList : 233
=====중간 추가=====
ArrayList : 2233
LinkedList : 106
=====중간 삭제=====
ArrayList : 1403
LinkedList : 219
=====순차적 삭제=====
ArrayList : 8
LinkedList : 25

순차적 추가/삭제 -> ArrayList가 빠르다

• 테스트 시 ArrayList의 경우 충분한 초기용량을 확보하여 저장공간이 부족하여 새로운 ArrayList를 생성하는 상황 방지
• 순차적 삭제는 마지막 데이터부터 역순으로 삭제
  • ArrayList는 마지막 데이터부터 삭제할 경우 요소 재배치가 필요없어서 상당히 빠름.

중간 추가/삭제 -> LinkedList가 빠르다

• LinkedList의 경우 각 요소의 연결만 변경해주면 되므로 처리속도가 빠르다.

접근(조회)

다음은 접근시간에 대한 테스트를 실행해보자.

실행

public static void main(String[] args) {
    List<String> al = new ArrayList<>(1000000);
    List<String> ll = new LinkedList<>();
    
    add(al);
    add(ll);

    System.out.println("=====접근시간 테스트=====");
    System.out.println("ArrayList :" + access(al));
    System.out.println("LinkedList :" + access(ll));

}

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

private static void add(List<String> list) {
    for (int i = 0; i < 100000; i++) {
        list.add(i+"");
    }
}

결과

=====접근시간 테스트=====
ArrayList :1
LinkedList :133

요소 접근시간 -> ArrayList가 빠르다

배열의 경우 아래의 수식으로 간단하게 찾는 요소의 주소를 얻을 수 있다.

인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

• 배열 -> 각 요소들이 연속적으로 메모리상에 존재
  • 위의 식으로 간단하고 빠르게 데이터를 읽음
• 링크드리스트 -> 불연속적으로 위치한 각 요소들이 연결
  • 처음부터 n번째 데이터까지 차례대로 읽어야함
  • 데이터의 개수가 많아질수록 데이터를 읽는 접근시간(access time)이 길어진다.

정리

컬렉션	읽기(접근시간)	추가/삭제	비고
ArrayList	빠름	느림	순차적인 추가/삭제는 더 빠름. 비효율적인 메모리 사용
LinkedList	느림	빠름	데이터가 많을수록 접근성 떨어짐

---

References

• 남궁성, 『자바의 정석』, 도우출판(2016)
• https://www.geeksforgeeks.org/vector-vs-arraylist-java/
• https://stackoverflow.com/questions/1386275/why-is-java-vector-and-stack-class-considered-obsolete-or-deprecated