[JAVA] JAVA List

이번엔 JAVA 의 List 에 대해서 알아보도록 하겠습니다.
제가 알기론 List 는 배열의 단점을 보완하기 위해 나온 데이터 구조로 알고 있습니다. 배열은 사용함에 있어 불편한 점이 있는데 그것은 사용하기 전 배열의 크기를 지정을 해주어야 한다는 것입니다.
하지만 프로그래밍을 해보면 아시겠지만 배열을 쓸 때 배열에 들어갈 데이터가 얼마나 들어올지 가늠 하기 힘든 경우가 많습니다. 그래서 배열의 크기를 너무 적게 설정하면 ArrayIndexOutOfBoudns 에러가 발생한 것이고, 그렇다고 무작정 배열의 크기를 크게 하자니 그 만큼 메모리 낭비가 심한 코드가 되버리게 되버리죠. C 에서는 이런 문제를 해결하기 위해서 동적 할당을 사용했습니다만 C 의 동적 할당도 써보시면 아시겠지만 여러 제약 조건과 또 메모리를 직접 건드는 작업이다 보니 메모리 해제 등을 제대로 해주지 않으면 엄청 많은 오류를 만나게 됩니다. 하지만 JAVA 에서는 이런 배열의 문제를 해결한 List 라는 데이터 구조를 제공해 주고 있어 List 를 알아놓으면 JAVA 코딩 할 때 굉장히 유용할 것입니다.

List 란?

JAVA 에서의 List 는 컬렉션 프레임워크(Collection Framework)의 일부로, 동적 크기 배열을 구현하는 인터페이스입니다. 배열처럼 구성 요소를 일렬로 세운 구조를 가지고 있으며, 구성 요소를 인덱스(index)로 관리하기 때문에 구성 요소를 저장하면 자동으로 인덱스가 부여되고, 인덱스로 객체를 검색, 추가, 삭제할 수 있는 등의 기능을 제공합니다.

List 인터페이스를 구현한 클래스로는 ArrayList, Vector, LinkedList, Stack 등이 있습니다. Vector 는 JDK 1.0 에서 등장한 자료 구조고 지금까지도 사용되긴 하지만 JDK 1.2 이후에 ArrayList 가 추가된 후에는 ArrayList 가 성능 측면에서 더 효율적이기 때문에 일반적으로 ArrayList 가 더 많이 사용됩니다. Vector 를 사용하는 경우에는 호환성을 위해 기존 코드에서 ArrayList 로 수정하지 않고 사용되는 경우가 많다고 합니다.

그리고 구성 요소의 추가, 삭제, 삽입 등의 작업이 많이 일어나는 경우에는 LinkedList 를 사용하는 것이 더 효율적입니다. ArrayList 는 배열을 사용하여 데이터를 저장해서 데이터의 추가나 삭제가 발생할 때, 해당 위치에서 데이터를 삽입하거나 삭제한 뒤에 다른 요소들을 한 칸씩 이동시키기 때문에 구성 요소가 많을 경우 많은 연산이 발생합니다. 하지만 LinkedList 는 각 요소들을 노드(Node)로 구성한 연결 리스트를 사용해 데이터를 저장하기 때문에 데이터의 추가나 삭제가 발생할 때, 해당 위치에서 노드를 추가하거나 삭제하면 되어 단순히 이전 노드와 다음 노드의 포인터의 변경으로 이루어지기 때문에 ArrayList 대비 연산이 극도로 적기 때문입니다.

List 의 특징

• 순서가 있고 중복을 허용한다.
• 인덱스로 관리하기 때문에 인덱스로 접근이 가능하다.
• 크기가 가변적이다.

List 는 컬렉션 프레임워크(Collection Framework)의 일부로, 동적 크기 배열을 구현하는 인터페이스입니다. List<> 를 사용하면 데이터를 순서대로 저장하고 관리할 수 있습니다. 이를 통해 배열과 비슷한 동작을 하지만 크기를 자동으로 저장할 수 있는 장점을 갖습니다.

public interface List<E> extends Collection<E> {
  // List 인터페이스 메소드들이 여기에 선언됨
}

List 의 인터페이스

List 에서 자주 사용되는 인터페이스는 다음과 같습니다.

메소드	리턴 타입	설명
size()	int	리스트에 있는 요소 개수를 반환합니다.
add(E e)	boolean	리스트에 요소를 추가합니다.
remove(Object o)	boolean	주어진 객체가 리스트에 존재할 경우 해당 요소를 삭제
contains(Object o)	boolean	주어진 객체가 리스트에 있는지 확인합니다. 있을 경우 true, 없을 경우 false 를 반환합니다.
get(int index)	E	주어진 인덱스에 저장된 요소를 반환합니다. 만약 인덱스 값이 리스트이 사이즈보다 큰 값일 경우 에러가 발생합니다.
set(int index, E element)	E	주어진 인덱스에 위치한 요소를 새로운 요소로 대체.
isEmpty()	boolean	리스트가 비었는지 체크하는 메소드로 리스트에 요소가 없다면 true 를 요소가 있다면 false 를 반환합니다.
equals(Object o)	boolean	주어진 객체와 동일한지 비교하고, 동일하다면 true 를 그렇지 않다면 false 를 반환합니다.
indexOf(Object o)	int	주어진 객체가 있는 첫 번째 요소의 위치 값을 반환합니다 만약 요소가 존재하지 않을 경우 -1을 반환합니다.
clear()	void	리스트의 모든 요소들을 제거합니다.
addAll(Collection c)	boolean	주어진 Collection 객체의 구성 요소들 모두를 넣고자 하는 List 의 마지막 인덱스부터 차례로 넣어줍니다.
addAll(int index, Collection c)	boolean	주어진 Collection 객체의 구성 요소들 모두를 넣고자 하는 List 의 파라매터로 주어진 인덱스 부터 차례로 넣어줌 만약 List 의 크기가 주어진 인덱스 값 보다 적다면 에러 발생

List 의 장단점

<장점>

1. 데이터의 개수에 따라 해당 개수만큼 메모리를 동적 할당해주기 때문에 메모리 관리에 좋습니다.
   • 배열은 사용하기 위해서 배열의 크기를 미리 정의해두어야 하는데, 만약 생각한 것 보다 데이터의 양이 적다면 배열의 나머지 부분은 사용하지 않게 되므로 메모리 낭비를 유발, 이러한 배열들이 많아진다면 메모리 유수가 발생합니다.

2. 빈 공간을 허용하지 않기 때문에 데이터 관리가 편합니다.

3. 포인터로 각 데이터들이 연결되어 있기 때문에 해당 데이터에 연결된 주소만 바꿔주면 되므로 삽입 삭제에 용이 합니다 (LinkedList)

<단점>

1. 객체로 데이터를 다루기 때문에 적은 양의 데이터만 사용할 경우 배열에 비해 차지하는 메모리가 커집니다.
   • 그래서 데이터의 양이 적을 때는 리스트 보다는 배열을 사용하는 경우가 더 좋을 수도 있습니다.
2. 기본적으로 포인터 기반으로 구성되어 있고, 메모리에 순차적으로 할당하는 것이 아니기 때문에(물리적 주소가 순차적이지 않다) 색인(검색) 능력이 떨어집니다.

ArrayList

ArrayList 는 List 인터페이스를 구현한 클래스로 컬렉션 프레임워크에서 일반적으로 가장 많이 사용됩니다. 기능적으로는 Vector 와 동일하지만 Vecotr 를 개선한 것이므로 Vector 보다 많이 사용됩니다.
ArrayList 는 저장 공간에 데이터가 모두 찬 경우 새로운 ArrayList 를 만들고 새로 만든 것에 이전 ArrayList 의 모든 데이터를 복사하는 방식이기 때문에 이 때마다 지연이 발생합니다.
ArrayList 는 첫과 끝이 아닌 List 의 중간에 데이터를 삽입하거나 삭제를 할 때 요소들의 위치를 앞 뒤로 이동 시키기 때문에 중간에 있는 데이터의 삽입/삭제 동작은 느립니다. 따라서 ArrayList 는 최대한 데이터의 삽입/삭제는 연산은 마지막 요소에만 적용하도록 하는 것이 좋으며, 데이터를 저장하고 조회하는 경우에 사용하는 것이 좋습니다.

LinkedList

ArrayList 와 배열은 모든 데이터가 연속적으로 존재하지만, LinkedList 는 불연속적으로 존재하며, 데이터들은 모두 연결되어 있습니다. 따라서 LinkedList 컬렉션은 데이터를 효율적으로 변경(추가, 삭제) 할 때 사용하면 좋습니다.

ArrayList vs LinkedList

ArrayList 와 LinkedList 는 위에서 알아본 것과 같이 ArrayList 는 순차적 추가/삭제 시에, LinkedList 는 요소 중간 추가/삭제 시에 빠르다고 하였습니다. 그렇다면 실제로 그렇게 동작하는지 예제 코드를 이용해 테스트를 진행해 보도록 하겠습니다.

1. 추가/삭제

추가/삭제에 대한 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 의 경우 각 요소의 연결만 변경해주면 되므로 처리속도가 빠르다.

2. 조회

고성 요소 조회에 대해서 ArrayList 와 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 가 빠르다
• LinkedList 가 ArrayList 보다 느린 이유
  • 처음부터 n번째 데이터까지 차례대로 읽어야함
  • 데이터의 개수가 많아질수록 데이터를 읽는 접근시간(access time) 이 길어진다.

마치며

JAVA 의 List 에 대해 기초적인 것에 대해서 알아보았습니다. List 는 JAVA 의 컬렉션 프레임워크 중에서 가장 많이 쓰이는 컬렉션 프레임워크이기 때문에 필수로적으로 알아야합니다. 그래서 기초적인 것에 대해서 조금 더 상세히 다루었습니다.
이번에도 저의 포스트를 읽어주셔서 감사드리며, 잘못된 내용, 오타 궁금한 것이 있으시면 댓글로 말씀해 주시길 바랍니다.