F014 - List (ArrayList, LinkedList, Vector, Stack)

✍️ 지금까지 개발을 하면서 다양한 자료구조를 사용했지만, 어떻게 작동하는지 모른 채 사용했었다.
그래서 여러 상황들 속에서 자료구조를 적절히 사용하는 것이 아니라 남들이 쓰니까 따라 쓰고, 내가 익숙하니까 그냥 쓰는 것이 버릇이 됐다.

이번 시간을 통해 가장 자주 사용하는 List 인터페이스에 대해 공부하고 이를 구현한 ArrayList와 LinkedList의 차이를 확인해보자.

---

List

List(이하 리스트)는 데이터를 중복하여 담을 수 있고, 객체에 데이터가 담기는 순서대로 메모리에 할당된다는 특징을 가지고 있다.
이러한 특징 덕분에 데이터를 순서대로 조회할 때 주로 사용된다. 이를 확장한 클래스로는 Vector, ArrayList, LinkedList가 존재한다.

Method

메소드	설명
add(E a)	매개 변수로 전달 받은 데이터를 객체에 담는다.
add(Collection<?> c)	Collection 클래스를 상속 받는 자식 클래스에 한해서 매개 변수로 허용하고, 이를 현재 리스트에 순서대로 담는다.
set(int index, E element)	매개 변수로 전달 받은 인덱스에 전달 받은 객체로 교체한다.
remove(int index)	해당 인덱스에 담긴 데이터를 리스트 객체 내에서 삭제한다.
remove(Object o)	같은 객체를 찾아 리스트에서 삭제한다.
clear()	리스트 객체 내에 존재하는 모든 데이터를 지운다.
size()	리스트 객체에 담긴 데이터의 개수를 int 타입으로 반환한다. 일반적인 배열의 length는 메모리에 할당된 배열의 길이를 반환하기 때문에 length와 size()는 다른 의미를 가진다.
isEmpty()	리스트 객체 내에 데이터의 존재여부를 확인하고 boolean 타입을 반환한다. 하나의 데이터라도 존재하면 true, 존재하지 않으면 false를 반환한다.
indexOf(Object o)	매개 변수로 전달된 객체가 리스트에 몇 번째에 담겨 있는지 확인하고, 존재한다면 해당 인덱스 번호를 존재하지 않는다면 -1을 반환한다.
lastIndexOf(Object o)	리스트에서 매개 변수로 전달된 객체와 동일한 객체들 중 마지막 인덱스 번호를 반환하며 존재하지 않는다면 -1을 반환한다.
contains(Object o)	매개 변수로 Object 를 받으며, 해당 매개 변수가 리스트 객체 내에 존재하는지 확인한다.
toArray()	리스트 객체에 담긴 데이터를 Object 배열로 반환한다. 해당 배열 객체는 참조되지 않는 객체로 내부에 담긴 데이터에 안전하게 접근 가능하다. 하지만 Object[] 로 반환하기 때문에 별도의 캐스팅을 직접 해줘야 한다.
toArray(T[] a)	리스트 객체에 담긴 데이터를 매개 변수로 전달 받은 객체 타입의 배열로 반환하며, 만약 매개 변수 객체의 길이가 리스트보다 길다면 매개 변수 객체만큼의 배열을 만들고 리스트의 데이터를 새로 만든 배열에 순서대로 담는다. 나머지 공간은 아무 것도 채워지지 않고 빈 공간으로 할당된다.
itertator()	List 인터페이스는 Collection 클래스를 상속 받고, Collection 클래스는 Iterable 클래스를 상속 받는다. Itertable 클래스는 내부적으로 Iterator 인터페이스를 구현하고 있기 때문에 이를 통해 Itertator 객체로 캐스팅하여 객체 내부에 담긴 데이터를 순회 할 수 있다.

 

배열과 리스트 자료구조의 특징

Array : 배열

📍 정해진 길이를 가지고 있다.

📍 정적으로 메모리에 할당한다.

📍 배열의 길이를 동적으로 변경 할 수 없다.

📍 배열에 담긴 데이터는 메모리에 연속적으로 담기기 때문에 메모리 관리가 용이하다.

📍 배열의 논리적인 순서(Index)와 메모리에 할당된 물리적인 순서(메모리 주소)가 동일하다.

📍 배열의 길이가 정해져 있기 때문에 배열의 중간에 위치한 인덱스의 데이터를 삭제한다고 가정한다면, 해당 인덱스는 비워지게 된다.

List : 리스트

📍 인덱스가 존재하지 않는다.

📍 데이터의 순서가 존재하는 집합이다.

📍 메모리에 비연속적으로 데이터가 할당된다.

📍 포인터를 이용해서 데이터에 접근한다.

📍 빈 공간이 존재하지 않는 것을 원칙으로 리스트 중간의 데이터가 삭제된다면 빈 공간을 완전히 정리하므로써 리스트의 사이즈는 삭제된 데이터만큼 줄어든다.

Array.length / List.size()

🔎 Array.length
 : 메모리에 할당된 배열의 길이를 의미한다.

🔎 List.size()
 : 리스트에 담겨져 있는 데이터의 개수를 의미한다.

위에서 잠깐 살펴본 Array와 List의 특징을 보면 length와 size()가 왜 다른 의미인지 파악 할 수 있다.

먼저 배열은 객체를 선언 할 때 메모리에 할당 될 길이를 정해줘야 하며, 데이터들이 연속적으로 메모리에 할당된다.
이러한 특징 때문에 배열에 담긴 데이터가 삭제되더라도 메모리에 할당된 배열의 길이는 변하지 않아, 데이터의 개수가 아닌 메모리에 할당된 배열의 길이를 반환한다.

하지만 size() 메소드는 근본적으로 리스트의 길이가 아니라 리스트 객체 내에 존재하는 요소에 초점이 맞춰져 있다.
이는 리스트 자료구조의 특징인 데이터가 메모리에 연속적으로 할당되지 않는다. 또한, 리스트 내 데이터가 삭제된다면 빈 공간을 허용하지 않는 특징에 따라 리스트의 크기도 가변적이기 때문에 길이의 의미가 아닌 요소 개수의 의미로 바라봐야 한다.

---

ArrayList

ArrayList는 List 인터페이스를 구현한 클래스 중 하나로, 내부적으로 배열을 만들어 인덱스와 메모리 연속성의 특징을 가지는 클래스이다.

ArrayList 클래스의 내부를 잘 살펴보면 AbstractList 클래스를 확장하고, List 인터페이스 뿐만 아니라 Serializable, Cloneable, RandomAccess 등의 인터페이스도 구현한 것을 확인 할 수 있다.

클래스 / 인터페이스	태그	설명
AbstractList<E>	extends	이름 그대로 List 인터페이스의 추상화 클래스로 메모리에 랜덤으로 엑세스되는 자료구조를 최소한으로 구현 할 수 있도록 도와준다. 즉, 리스트 인터페이스를 구현한 클래스들의 공통적인 메소드를 미리 구현해놓은 클래스라는 의미이다.
List<E>	implements	리스트 인터페이스 내에서 명세 해놓은 메소드를 구현하고, 사용 할 수 있도록 한다.
RandomAccess	implements	리스트 객체에 담긴 데이터에 빠르게 접근하기 위해서 지정한다.
Cloneable	implements	복제가 가능한 객체임을 명시한다.
Serializable	implements	파일을 저장하거나 외부로 객체의 데이터를 전송하기 위한 용도로 직렬화를 수행한다.

ArrayList 클래스는 이름에서 알 수 있듯 객체를 만들 때 배열을 만드는데, 이 때 별도의 capacity 값을 지정하지 않는다면 길이가 10인 배열을 생성한다.

// 기본 배열 길이
private static final int DEFAULT_CAPACITY = 10;
// 생성되는 Object[]
transient Object[] elementData;

// 기본 생성자
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

// 매개 변수로 capacity를 전해 받을 때
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);
        }
    }

해당 배열은 Object[]로 생성되며, 배열은 기본적으로 한번 길이가 정해지면 늘리거나 줄일 수 없기 때문에 해당 배열이 다 차면, 현재 배열의 길이 2배인 새로운 배열을 만들고 기존의 배열에 담긴 데이터를 새로운 배열에 담아 반환한다.

때문에 리스트에 담길 데이터의 개수를 알고 있다면 ArrayList 객체를 생성할 때 해당 개수만큼의 배열을 메모리에 할당하여 메모리 낭비를 줄일 수 있다.

하지만 담길 데이터의 개수를 알지 못하고, 대량의 데이터를 추가적으로 반복해서 ArrayList 객체에 담는다면 기존의 배열이 다 차고 새로운 배열을 만들어 기존 배열의 데이터를 새로운 배열에 담는 과정을 반복하는 만큼 수행하기 때문에 불필요한 메모리 낭비가 발생한다.

또한, ArrayList 클래스는 연속적인 메모리 공간과 인덱스를 사용하며 O(1)의 시간 복잡도로 데이터에 접근 할 수 있다는 배열의 특징을 가지고 있는데, 조회를 주 목적으로 사용한다면 효율적으로 메모리를 관리 할 수 있다.

하지만 데이터 추가나 삭제, 수정하는 행위가 지속적으로 수행되는 경우, 앞서 설명한 내용을 바탕으로 데이터 낭비가 발생할 수 있으며, 처음부터 변화가 발생하는 데이터의 위치까지 접근해야 하기 때문에 추가, 삭제, 수정의 행위는 O(n)의 시간 복잡도로 인해 효율성이 떨어진다.

그러한 이유로 ArrayList에 담길 데이터의 개수를 알거나 주 목적이 조회 용도라면 해당 클래스를 사용하는 것이 효율적일 수 있으나, 대량의 데이터를 추가, 삭제, 수정을 수행하는 로직이라면 ArrayList를 사용하는 것은 좋은 방법이 아니라고 생각한다.

---

LinkedList

LinkedList 클래스는 ArrayList 클래스와 달리 AbstractList 추상 클래스를 직접적으로 상속 받는 것이 아니라 AbstractSequesntialList 추상 클래스를 상속 받아 확장한다.
또한, RandomAccess 인터페이스를 구현하지 않는 것을 확인 할 수 있다.

이는 LinkedList의 구조와 밀접한 관계를 가지는데, LinkedList는 ArrayList 처럼 배열의 구조를 이용하는 것이 아니라 Node라는 객체의 연결을 통해 리스트를 구현한다.
(Node 객체는 LinkedList의 내부 클래스로 명시되어 사용된다.)

때문에 LinkedList는 Sequential Access(순차 접근)을 통해 데이터에 접근하기에 RandomAccess 인터페이스를 구현 할 필요가 없으며, 이로 인해 AbstractList 추상 클래스를 확장한 AbstractSequentialList 추상 클래스를 상속 받아 순차 접근에 필요한 공통적인 메소드를 제공 받는다.

public E get(int index) {
	// 인덱스가 List 범위를 벗어나는지 확인
	checkElementIndex(index);
	// node(index)를 통해 데이터 조회
	return node(index).item;
}

Node<E> node(int index) {
	// assert isElementIndex(index);

	if (index < (size >> 1)) {
		Node<E> x = first;
		for (int i = 0; i < index; i++)
			x = x.next;
		return x;
	} else {
		Node<E> x = last;
		for (int i = size - 1; i > index; i--)
			x = x.prev;
		return x;
	}
}

Node 객체는 item, next, prev를 멤버 필드로 가진다.

위의 코드의 node() 메소드를 확인하면 매개 변수로 받는 index의 값을 기준으로 첫 번째 노드와 마지막 노드 중 가장 가까운 방향에서 하나씩 다음 혹은 이전 노드를 방문해서 조회하고자 하는 노드에 도착했을 때 해당 노드를 반환하는 것을 알 수 있다.

이러한 구조를 가지는 LinkedList는 비연속적으로 메모리를 할당하며, 인덱스를 사용하지 않으므로 특정 데이터가 담긴 노드에 접근하기 위해서는 제일 처음에 위치한 노드부터 순차적으로 접근해 O(n)의 시간 복잡도를 가지는 특징을 가진다.

LinkedList는 추가, 수정, 삭제에 ArrayList 보다 좋은 효율을 보여준데, ArrayList는 길이가 정해져 있어 데이터를 추가,수정, 삭제하는 행위를 수해할 때 새로운 배열을 생성하면서 메모리를 낭비하기 때문에 효율이 떨어진다.
하지만 LinkedList는 변경하고자 하는 데이터가 위치한 노드를 교체해주기만 하면 되기 때문에 추가적으로 전체 데이터를 복사하는 경우는 발생하지 않아 훨씬 효율적이다.

이런 이점이 있는 LinkedList이지만 해당 행위를 수행할 때 O(n)의 시간 복잡도를 가지는 경우가 발생하는데, 이는 첫 번째 혹은 마지막 노드를 제외한 중간 노드에 대한 해당 행위를 수행 할 때 발생한다.

그 이유는, 어쨌든 변경하고자 하는 데이터가 위치한 노드까지 도달해야 하기 때문이다.
다만 첫 번째와 마지막 노드는 처음과 끝에 위치한 노드이기 때문에 추가적으로 다른 노드를 찾지 않아도 되기 때문에 O(1)의 시간 복잡도를 가진다.

Vector

Vector 클래스는 ArrayList 클래스와 동일한 내부 구조를 가지고 있지만, 둘의 가장 큰 차이는 동기화의 여부이다.
ArrayList 클래스는 동기화를 지원하지 않지만 Vector 클래스는 동기화를 지원한다.

때문에 여러 개의 스레드가 동시에 Vector 객체에 접근 할 수 없으며, 이전 스레드에서 Vector 객체에 대한 작업 수행을 완료해야지 다른 스레드에서 Vector 객체에 접근 할 수 있다. 그래서 멀티 스레드 환경에서 안전하게 객체 내에 데이터를 변경 할 수 있다.

다만, 멀티 스레드를 지원하기 때문에 ArrayList 보다 성능이 떨어진다는 단점이 존재한다.

Stack

Stack 클래스는 LIFO(선입후출)의 구조를 가지는 자료구조이며, Vector 클래스를 상속 받아 확장한다. Vector 클래스를 그대로 확장하기 때문에 Vector 클래스의 문제점을 그대로 이어 받는다.

또한, 자료구조 상 Stack 클래스와 Vector클래스의 상속 관계는 옳지 않으나 아직까지 사용하는 유저가 존재해 별 다른 변경이나 사용을 금지하지 않고 있다.

Vector와 Stack은 왜 사용하지 않을까?

앞서 알아봤던 내용처럼 Vector 클래스는 동기화를 수행하는데, 내부에 구현된 대부분 메소드에 synchronized 제어자가 선언되어 있다.

이 때문에 Vector 객체에 한번만 Locking을 수행하면 되는 것을 해당 객체의 synchronized 가 선언된 메소드를 호출 할 때 마다 Locking이 수행되서 불필요한 오버헤드가 발생한다.

때문에 멀티 스레드 환경에서도 특정 조건이 아니라면 성능 저하를 일으키기 때문에 왠만하면 ArrayList를 사용하는 것이 좋으며, 멀티 스레드 환경에서 ArrayList를 사용하여 객체 동기화를 진행하고자 한다면, Collections.synchronizedList()를 생성자의 매개 변수로 전달하여 객체를 만들면 된다.

Stack 클래스 또한 Vector 클래스를 확장했기 때문에 위와 같은 문제점을 그대로 이어 받는다. 이를 대체하기 위해서 Deque 클래스를 사용하는 것이 좋다.

---

💭 이번 시간을 통해 대략적으로 알고 있었던 ArrayList, LinkedList 클래스에 대해서 알게 되었고, 추가적으로 Vector와 Stack이 왜 사용되지 않는지, List와 Array의 차이에 대해 공부 할 수 있게 되었다.

실무에서 해당 부분들을 충분히 고려해서 개발을 할 수 있도록 지속적으로 상기시켜야겠다!

---

참고 사이트

자바에서 Vector와 Stack 컬렉션이 쓰이지 않는 이유?

 

랜덤 액세스 메모리 - 위키백과, 우리 모두의 백과사전