728x90

List 개념 이해하기

 

 자료구조 중 하나인 List는 배열의 한계를 극복할 수 있는 강력한 자료구조 중 하나이며 데이터를 단순하지만 효율적으로 다룰 수 있는 자료구조이다.

 List는 Array처럼 어떠한 데이터들을 묶기 위한 개념이다. Array와 대표적으로 다른 특징들은 아래와 같다.

  • 데이터를 담을 공간의 추가가 가능하다. (Array는 초기 공간을 지정하기 때문에 한정적)
  • 데이터를 담을 공간의 삭제가 가능하다. (Array는 데이터가 담기는 공간의 값을 변경할 수 있지만 그 공간을 삭제할 수 는 없다.)
  • 즉, 크기가 가변적이다.

 List 인터페이스의 구현체에는 Stack, Vector, ArrayList, LinkedList가 있다. 이 중에서도 대표적인 클래스인 ArrayList와 LinkedList의 차이에 대해 정리해봤다.

http://changpd.blogspot.com/2014/08/arraylist-linkedlist-java.html

위 사진을 보면 알 수 있듯

ArrayList는 index가 있고,

LinkedList는 각 원소마다 앞, 뒤 원소의 위치값을 가지고 있다.

 

이러한 각각의 특징은 조회, 삽입, 삭제시에 성능의 차이를 발생시킨다.

ArrayList

  • index를 가지고 있고 무작위 접근이 가능하기 때문에, 해당 index의 데이터를 한 번에 가져올 수 있어 데이터에 빠르게 접근할 수 있다.
  • 자료들을 순차적인 메모리 공간 안에 연속하여 저장되는 자료구조
  • 배열과 비슷하나 빈자리 공간이 없이 순서대로 저장되는 특징
  • 논리적 순서와 물리적 순서가 동일
  • 탐색에서는 효율적이나 추가, 삭제에서는 상대적으로 효율이 떨어진다.
    (추가시 배열이 동적으로 늘어나는 것이 아니라 용량이 꽉 찾을 경우 더 큰 용량의 배열을 만들어 옮기는 작업을 하기 때문)

 

좀 더 자세히 알아보면,

ArrayList는 물리적 논리적 순서가 동일하다. 그래서 탐색은 효율적이나 추가, 삭제는 효율이 떨어진다.

https://blog-of-gon.tistory.com/159

그림처럼 메모리 공간 안에 순서대로 이름이 저장된다. 물리적, 논리적 순서가 동일하다.

따라서 탐색 또한 순서대로 이루어진다.

데이터를 추가하고 삭제할 때에 마지막 부분의 데이터를 추가하고 삭제한다면 문제가 없을 것이다. 

하지만 중간 데이터를 삭제한다면?

 

https://blog-of-gon.tistory.com/159

 데이터를 중간에서 삭제하거나 추가한다면 위와 같은 연산이 필요하다. 중간에 데이터를 추가, 삭제는 가능하지만 데이터를 추가하는 위치의 뒤의 자료들을 다시 한번 더 밀어주거나 당겨주는 연산을 해야 한다.

 

내부 코드를 보면서 더 자세히 이해해보자.

 

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    transient Object[] elementData; // non-private to simplify nested class access

    private int size;

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    public ArrayList(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }
}

 

내부 코드에는 위와 같이 3개의 생성자가 존재한다.

  • 매개변수를 받지 않는 생성자
  • 초기 용량을 매개변수로 받는 생성자
  • Collection 타입을 매개변수로 받는 생성자

여기서 첫 번째, 두 번째 생성자에 대해서 알아보자.

 

List<Integer> list = new ArrayList<>();

 

 보통 ArrayList의 객체를 만들 때 위와 같이 만든다. 위와 같이 만들면 아래와 같은 매개변수가 존재하지 않는 생성자가 만들어진다.

 

private static final int DEFAULT_CAPACITY = 10;

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

 

 위의 생성자를 이용해서 ArrayList를 만들게 되면 DEFAULT_CAPACITY = 10으로 정의되어 있다. 한마디로 배열의 크기가 10으로 지정된 것과 같다고 생각하면 된다.

 

그렇다면 용량 10보다 더 많은 원소를 넣는다면 어떻게 될까?

 

 위에서 배열과 ArrayList의 차이는 동적으로 요소를 추가, 삭제할 수 있고 용량이 초과하면 더 큰 용량의 배열에다 옮기는 과정이 일어난다고 했다.

 

용량이 초과했을 때는 내부 코드에서 어떻게 실행이 될까?

 

public class ArrayList<E> {
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
}

 

  ArrayList 안에는 배열에 값을 추가할 수 있는 add()메소드가 존재한다. 여기에 보면 ensureCapacityInternal()이 보이는데  여기서 배열 용량을 늘리는 작업이 일어날 것 같다.

 

public class ArrayList<E> {
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

 

 ArrayList 내부의 메소드인데 코드는 위와 같이 되어 있다. 복잡해 보이지만 중요한 부분은 grow() 메소드 내부에서 Arrays.copyOf(elementData, newCapacity);를 통해서 더 큰 배열에다 기존 배열의 원소들을 복사한다는 것이다.

 Arrays.copyOf()의 내부 코드를 보면 알 수 있지만 실제 A 배열을 B 배열로 옮기는 과정은 원소의 수가 얼마 안되면 괜찮겠지만 많다면 상당히 많은 시간이 소요되고 효율적이지 못하다.

 

ArrayList 객체를 만들 때 초기 용량을 설정하는 것이 좋다

 위와 같이 초기 용량을 설정하지 않으면 DEFAULT_CAPACITY = 10 이다. 많은 원소가 추가, 삭제가 되는 상황이라면 빈번하게 배열의 복사가 일어날 것이다. (위에서 보았듯이 10만개의 배열을 다른 배열로 복사한다고 생각하면 비효율적일 것 같다. 더 많은 개수라면 더욱이)

 

 물론 초기 용량을 미리 예상하기는 쉽지가 않지만 대략적으로 초기 용량을 생각하고, 그 예상하는 것보다 살짝 더 여유있는 값으로 초기 용량을 설정해주는 것이 좋다고 생각한다.

 

add()를 통해서 ArrayList 용량이 꽉찬다면?

ArrayList의 용량이 꽉찬다면 그 다음엔 얼마나 용량을 늘려줄까요?

int newCapacity = oldCapacity + (oldCapacity >> 1);

 용량을 늘리는 코드의 위와 같은 코드가 있다. 해석해보면 oldCapacity + oldCapacity / 2로 늘리고 있다. oldCapacity가 8이라면 8 + 4 = 12로 늘어나는 것이다.

 

LinkedList

  • 자료를 저장하기 위해 자료부분과 위치를 알려주는 노드부분으로 구성한 자료의 묶음
  • 노드 부분을 통해 논리적인 순서로 메모리상에 저장 (논리적 연결이 있을 뿐 메모리 상에서는 자료들이 연속하여 저장되지 않을 수 있음)
  • 추가, 삭제에서 효율적이나 상대적으로 탐색 능력이 떨어진다.
    (데이터를 추가, 삭제시 가리키고 있는 주소값만 변경해주면 되기 때문에)

 

https://blog-of-gon.tistory.com/159

 

특정 위치에서 삭제 또는 삽입의 경우

https://blog-of-gon.tistory.com/159

그림처럼 전체 부분의 수정이 아닌 노드 안에 담긴 위치정보의 변경으로서 자유롭게 연결이 가능하다. 

 

마지막 노드의 특징을 알아보면,

마지막 노드의 경우 다음 노드가 존재하지 않는다. 이 때문에 기준 노드처럼 마지막 노드에 대한 정보 또한 저장하고 관리를 해야만 효율적이다.

 

https://blog-of-gon.tistory.com/159

 

 이런 식으로 LinkedList를 사용하면 특정 부분에 데이터를 삭제 삽입하는 과정에서의 연산은 ArrayList보다 훨씬 효율적인 구조로 이루어진다.

 다만 탐색의 경우에는 계속해서 위치정보 읽고 찾아가며 이동해야 되기 때문에 메모리에서 순서대로 읽는 것과는 차이가 분명하다. 

 

ArrayList와 LinkedList 성능 차이

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ArrayListLinkedListTest {
    public static void main(String[] args) {
        ArrayList al = new ArrayList(2000000);
        LinkedList ll = new LinkedList();

        System.out.println("= 순차적으로 추가하기 =");
        System.out.println("ArrayList : " + addl(al));
        System.out.println("LinkedList : " + addl(ll));
        System.out.println();
        System.out.println("= 중간에 추가하기 =");
        System.out.println("ArrayList : " + add2(al));
        System.out.println("LinkedList : " + add2(ll));
        System.out.println();
        System.out.println("= 중간에서 삭제하기 =");
        System.out.println("ArrayList : " + remove2(al));
        System.out.println("LinkedList : " + remove2(ll));
        System.out.println();
        System.out.println("= 순차적으로 삭제하기 =");
        System.out.println("ArrayList : " + remove1(al));
        System.out.println("LinkedList : " + remove1(ll));
    }

    public static long addl(List list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list.add(i+"");
        }

        long end = System.currentTimeMillis();
        return end - start;
    }

    public static long add2(List list) {
        long start = System.currentTimeMillis();

        for (int i = 0; i < 10000; i++) {
            list.add(500, "X");
        }

        long end = System.currentTimeMillis();
        return end - start;
    }

    public 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;
    }

    public static long remove2(List list) {
        long start = System.currentTimeMillis();

        for (int i = 0; i < 10000; i++) {
            list.remove(i);
        }

        long end = System.currentTimeMillis();
        return end - start;
    }
}

 

= 순차적으로 추가하기 =
ArrayList : 126
LinkedList : 171

= 중간에 추가하기 =
ArrayList : 1695
LinkedList : 10

= 중간에서 삭제하기 =
ArrayList : 1303
LinkedList : 122

= 순차적으로 삭제하기 =
ArrayList : 8
LinkedList : 23

 

순차적으로 추가하기

  • ArrayList : 순차적으로 추가하면 배열 원소들의 이동이 없이 추가만 하면 되기 때문에 쉽게 할 수 있다.
  • LinkedList : LinkedList는 순차적으로 추가하면 그 추가하고자 하는 곳으로 계속 탐색해서 가야 한다. 하지만 내부적으로 양방향으로 되어 있기 때문에 ArrayList와 큰 차이가 나지는 않는다.

중간에 추가하기

  • ArrayList: 중간에 추가하게 되면 빈 공간을 만들어야 하기 때문에 원소들의 이동이 필요하기 때문에 상당히 비효율적이다.
  • LinkedList: 중간에 추가할 때는 추가하고자 하는 원소 앞 or 노드로 가서 가리키고 있는 주소만 추가해주면 되기 때문에 금방 할 수 있다.

중간에 삭제하기

  • ArrayList: 중간에서 삭제하는 것도 마찬가지로 중간에 빈 공간이 생기기 때문에 채우기 위해서 원소들의 이동이 일어나므로 시간이 오래 걸린다.
  • LinkedList: 중간에 추가할 때는 추가하고자 하는 원소 앞 or 노드로 가서 가리키고 있는 주소만 추가해주면 되기 때문에 금방 할 수 있다.

순차적으로 삭제하기

  • ArrayList: 순차적으로 마지막 원소를 삭제할 때는 원소들의 이동이 필요 없기 때문에 시간이 오래 걸리지 않는다.
  • LinkedList: LinkedList는 내부적으로 양방향 연결리스트로 되어 있기 때문에 ArrayList와 큰 차이가 없는 것을 볼 수 있다.

성능 차이의 결론

순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다.

  • 단순히 저장하는 시간만을 비교할수록 하기 위해서 ArrayList에서 배열 재배치가 일어나는 상황은 제외하였다. 그렇다면 순차적으로 삭제한다는 것은 마지막 데이터부터 삭제할 경우 각 요소들의 재배치가 필요하지 않기 때문에 상당히 빠르다.

중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.

  • 중간 요소를 추가 또는 삭제하는 경우, LinkedList는 각 요소간의 연결만 변경해주면 되기 때문에 처리속도가 상당히 빠르다. 반면에 ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야하기 때문에 처리속도가 느리다.

 

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

 

ArrayList vs LinkedList 시간복잡도

https://devlog-wjdrbs96.tistory.com/64
http://changpd.blogspot.com/2014/08/arraylist-linkedlist-java.html

 

Reference

 

 

저작자표시

'Algorithm & Data Structure > study' 카테고리의 다른 글

[Data Structure / Java] ✒️ Stack, Queue  (0) 2022.08.15
[Data Structure / Java] ✒️ Map  (2) 2022.08.12
[Data Structure / Java] ✒️ 시간 복잡도  (0) 2022.08.04
[Data Structure / Java] ✒️ Call By Value / Call By Reference  (1) 2022.08.04
[Data Structure / Java] ✒️ 컴퓨터가 데이터를 다루는 방법  (0) 2022.08.03

티스토리툴바