[Java] Collection - List

List는 Collection 인터페이스를 확장하였다. 따라서, 몇몇 추가된 메소드를 제외하고는 Collection에 선언된 메소드와 큰 차이는 없다. Collection을 확장한 인터페이스와 다른 인터페이스와 List 인터페이스의 가장 큰 차이점은 배열처럼 '순서' 가 있다는 것이다.

 

List 인터페이스를 구현한 클래스들중에서 java.util 패키지에서는 ArrayList, Vector, Stack, LinkedList를 많이 사용한다.

 

ArrayList와 Vector 클래스의 사용법은 거의 동일하고 기능도 거의 비슷하다. 이 두 클래스는 "확장 가능한 배열" 이라고 생각하면 된다. 차이점은 Vector은 Thread safe하고, ArrayList는 Thread safe하지 않다.

 

/*

Vector : ArrayList와 비슷하지만 동기화가 되어있고 크기를 100% 증가시키는 차이가 있는 동적 배열

 

ArrayList를 Thread safe하게 만드는 법 ) 

List list = Collections.synchronizedList(new ArrayList(...));

*/

 

Stack라는 클래스는 LIFO(Last In First Out)를 지원한다. 가장 마지막에 추가한 값을 가장 처음에 빼 내는 것이다.

 

LinkedList라는 클래스는 "List"에도 속하지만, "Queue"에도 속한다. 

 

아래는 중요한 것에 관해서만 정리를 해보았다.

ArrayList란?

가변 크기의 배열을 구현한 콜렉션 클래스이다.

java.lang.object - java.util.AbstractCollection<E> - java.util.AbstractList<E> - java.util.ArrayList<E>  
// ArrayList 클래스의 상속관계

이 클래스들은 보시다시피 abstract 클래스이다.

AbstractCollection은 Collection 인터페이스 중 일부 공통적인 메소드를 구현해 놓은 것이며, AbstatList는 List 인터페이스 중 공통적인 메소드를 구현해 놓은 것이다.

 

jdk 11

인타페이스	용도
Serializable	원격으로 객체를 전송하거나, 파일에 저장할 수 있음을 지정
Cloneable	Object 클래스의 clone() 메소드가 제대로 수행될 수 있음을 지정. 즉, 복제가 가능한 객체임을 의미한다.
iterable<E>	객체가 "foreach" 객체가 "foreach"문장을 사용할 수 있음을 지정
collection<E>	여러 개의 객체를 하나의 객체에 담아 처리할 때의 메소드 지정
List<E>	목록형 데이터를 처리하는 것과 관련된 데이터 지정
RandomAcess	목록형 데이터에 보다 빠르게 접근할 수 있도록 임의로 접근하는 알고리즘이 적용된다는 것을 지정

 

ArrayList의 생성자는 3개다.

생성자	설명
ArrayList()	객체를 저장할 공간이 10개인 ArrayList를 만든다.
ArrayList(Collection? extends E c>	매개 변수로 넘어온 컬렉션 객체가 저장되어 있는 ArrayList를 만든다.
ArrayList(int initialCapcity)	매개 변수로 넘어온 initialCapacity 개수만큼 저장 공간을 갖는 ArrayList를 만든다.

 

ArrayList에 최대로 담을 수 있는 크기

"MAX_ARRAY_SIZE = Integer.MAX.VALUE - 8;", 할당된 배열의 최대 크기이다. 요청된 배열의 크기가 가상머신(VM) 을 초과하면 OutOfMemory가 발생할 수 있다.

 

ArrayList의 오버헤드

ArrayList 객체를 선언할 때 매개변수를 넣지 않으면, 초기 크기는 10이다. 따라서 10개 이상의 데이터가 들어가면 크기를 늘리는 작업이 ArrayList 내부에서 자동으로 수행된다. 이러한 작업이 수행되면, 어플리케이션에 영향을 주게 된다. 어느 정도 예측 가능하다면 초기 크기를 지정할 것을 권장한다.

 

ArrayList에 데이터를 담는 메소드

리턴 타입	메소드 이름 및 매개변수	설명
boolean	add(E e)	매개 변수로 넘어온 데이터를 가장 끝에 담는다
void	add(int index, E e)	매개 변수로 넘어온 데이터를 지정된 index 의치에 담는다.
boolean	addAll(Collection<? extends E> c	매개 변수로 넘어온 콜렉션 데이터를가장 끝에 담는다.
boolean	addAll(int index, Collection(? extends E> c)	매개 변수로 넘어온 컬렉션 데이터를 index에 지정된 위치부터 담는다

 

ArrayList add() 동작방식

 

내용이 길어 따로 글 작성해두었습니다. 여기!

 

여기서 주의해야 할 점은,

데이터 담을 때, list2 = list 형식으로 담으면, list라는 객체가 생성되어 참조되고 있는 주소까지도 사용되어지기 때문에,

Collection 관련 객체를 복사할 일이 있을 때에는 이와 같이 생성자를 사용하거나, addAll() 메소드를 사용할 것을 권장한다.

 

ArrayList에 데이터를 꺼내는 메소드

리턴 타입	메소드 이름 및 매개변수	설명
int	size()	ArrayList 객체에 들어가 있는 데이터의 개수를 리턴한다.
E	get(int index)	매개 변수에 지정한 위치에 있는 데이터를 리턴한다.
int	indexOf(object o)	매개 변수로 넘어온 객체와 동일한 데이터의 위치를 리턴한다.
int	lastIndexOf(object o)	매개 변수로 넘어온 객체와 동일한 마지막 데어터의 위치를 리턴한다
object[]	toArray()	ArrayList 객체에 있는 값들을 Object[] 타입의 배열로 만든다
<T>	toArray(T[] a)	ArrayList 객체에 있는 값들을 배개 변수로 넘어온 T 타입의 배열로 만든다.

여기서 중요한 것은 매개 변수가 없는 toArray() 메소드는 Object 타입의 배열로만 리턴을 한다는 것이다. 그러므로, 제네릭을 사용하여 선언한 ArrayList 객체를 배열로 생성할 때에는 이 메소드를 사용하는 것은 좋지 않다. 두 번째에 있는 메소드를 사용하는것을 적극 추천한다.

 

toArray(T[] a)는 매개 변수로 넘긴 객체에 값을 담아준다. 하지만, ArrayList 객체의 데이터 크기가 매개 변수로 넘어간 배열 객체의 크기보다 클 경우에는 매개 변수로 배열의 모든 값이 null로 채워진다. 그러므로 크기가 0인 배열을 넘겨주는 것이 가장 좋다.

 

ArrayList에 있는 데이터를 삭제하는 메소드

리턴 타입	메소드 이름 및 매개 변수	설명
void	clear()	모든 데이터를 삭제한다.
E	remove(int index)	매개 변수에서 지정한 위치에 있는 데이터를 삭제하고, 삭제한 데이터를 리턴한다.
boolean	remove(Object o)	매개 변수에 넘어온 객체와 동일한 첫 번째 데이터를 삭제한다.
boolean	removeAll(Collection<?> c	매개 변수로 넘어온 컬렉션 객체에 있는 데이터와 동일한 모든 데이터를 삭제한다.

ArrayList에 데이터의 값을 변경하는 메소드

리턴 타입	메소드 이름 및 매개 변수	설명
E	set(int index, E element)	지정한 위치에 있는 데이터를 두 번째 매개 변수로 넘긴 값으로 변경했다. 그리고, 해당 위치에 있던 데이터를 리턴한다.

추가로 trimToSize() 메소드

리턴타입	메소드 이름 및 매개변수	설명
void	trimToSize()	용량을 크기에 맞게 줄인다. ( 빈 공간을 없앤다)

String 클래스의 trim() 메소드가 앞 뒤의 공백을 없애는 것 처럼, 이 메소드를 사용하면, 저장할 수 있는 공간은 만들어 두었지만, 데이터가 저장되어 있지 않을 때 해당 공간을 없애버린다. 보통 이 메소드를 사용할 일이 없지만, 만약 ArrayList의 객체를 원격으로 전송하거나, 파일로 저장하는 일이 있을 때 이 메소드를 한 번호출함으로써 데이터의 크기를 줄일 수 있다는 장점이 있다.

 

LinkenList란 뭘까?

LinkedList의 상속 관계

java.lang-Object - java.util.AbstractCollection<E> - java.util.AbstractList<E> - java.util.AbstractSequentialList<E>- java.util.LinkedList<E>

LinkedList가 구현한 인터페이스

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{

LinkedList 클래스는 List도 되고 Queue(FIFO)된다. 두 인터페이스의 기능을 모두 구현한 특이한 클래스라고 볼 수 있다. 게다가 Deque 인터페이스도 구현하므로, 맨 앞과 끝의 데이터를 쉽게 처리할 수 있다.

 

LinkedList의 생성자

LinkedList는 일반적인 배열 타입의 클래스와 다르게 생성자로 객체를 생성할 때 처음부터 크기를 지정하지 않는다. 왜냐하면, 각 데이터들이 앞 뒤로 연결되는 구조이기 때문에, 미리 공간을 만들어 놓을 필요가없는 것이다. 따라서 두 가지 생성자만 존재한다.

생성자	설명
LinkdList()	비어 있는 LinkedList 객체를 생성한다.
LinkedList(Collection<? extends E> c)	매개 변수로 받은 컬렉션 객체의 데이터를 LinkedList에 담는다.

LinkedList의 객체의 데이터를 담는 메소드

리턴 타입	메소드 이름 및 매개 변수	설명
void	addFirst(Object)	LinkedList 객체의 가장 앞에 데이터를 추가한다.
boolean	offerFirst(Object)
boid	push(object)
boolean	add(Object)	LinkedList 객체의 가장 뒤에 데이터를 추가한다.
void	addLast(Object)
boolean	offer(Object)
boolean	offerLast(Object)
void	add(int, Object)	LinkedList 객체의 특정 위치에 데이터를 추가한다.
Object	set(int, Object)	LinkedList 객체의 특정 위치에 있는 데이터를 수정한다. 그리고 기존에 있던 데이터를 리턴한다.
boolean	addAll(Collection)	매개 변수로 넘긴 컬렉션의 데이터를 추가한다.
boolean	addAll(int, Collection)	매개 변수로 넘긴 컬렉션의 데이터를 지정된 위치에 추가한다.

LinkedList가 여러 종류의 인터페이스를 구현했기 때문에 중복된 기능을 수행하는 메소드가 많다. 여러 메소드를 혼용하면 그 소스를 읽는 사람도 이해하기 힘들기 때문에 한 가지만 선정하여 사용하는 것을 권장하며, add가 붙은 메소드를 사용하는 것이 오해의 소지가 가장 적다.

 

LinkedList 클래스에서 특정 위치의 데이터를 꺼내는 메소드

리턴 타입	메소드 이름 및 매개 변수	설명
Object	getFirst()	LinkedList 객체의 맨 앞에 있는 데이터를 리턴한다.
Object	peekFirst()
Object	peek()
Object	element()
Object	getLast()	LinkedList 객체의 맨 뒤에 있는 데이터를 리턴한다.
Object	peekLast()
Object	get(int)	LinkedList 객체의 지정한 위치에 있는 데이터를 리턴한다.

맨 앞에 있는 데이터를 가져오는 메소드들은 모두 내부적으로 getFirst() 메소드를 호출하므로, 이 메소드를 사용하는 것을 권장한다.

 

데이터의 값으로 위치를 찾거나, 존재하는지를 확인하는 메소드

리턴 타입	메소드 이름 및 매개 변수	설명
boolean	contains(Object)	매개 변수로 넘긴 데이터가 있을 경우 true를 리턴한다.
int	indexOf(Object)	매개 변수로 넘긴 데이터의 위치를 앞에서부터 검색하여 리턴한다. 없을 경우 -1을 리턴한다.
int	lastIndexOf(Object)	매개 변수로 넘긴 데이터의 위치를 끝에서부터 검색하여 리턴한다. 없을 경우 -1을 리턴한다

삭제 관련 메소드

리턴 타입	메소드 이름 및 매개 변수	설명
Object	remove()	LinkedList 객체의 가장 앞에 있는 데이터를 삭제하고 리턴한다.
Object	removeFirst()
Object	poll()
Object	pollFirst()
Object	pop()
Object	pollLast()	LinkedList 객체의 가장 끝에 있는 데이터를 삭제하고 리턴한다
Object	removeLast()
Object	remove(int)	매개 변수에 지정된 위치에 있는 데이터를 삭제하고 리턴한다.
boolean	remove(Object)	매개 변수로 넘겨진 객체와 동일한 데이터 중 앞에서부터 가장 처음에 발견된 데이터를 삭제한다,
boolean	removeFirstOccurrence(Object)
boolean	remverLastOccurrence(Object)	매개 변수로 넘겨진 객체와 동일한 데이터 중 끝에서부터 가장 처음에 발견된 데이터를 삭제한다.

맨 앞에 있는 데이터를 삭제하는 많은 메소드들은 모두 removeFirst() 메소드를 내부적으로 호출한다. 반대로 맨 뒤에 있는 데이터를 삭제하는 메소드들은 모두 removeFirst() 메소드를 내부적으로 호출한다. 따라서, 혼동을 피하려면 remove가 붙은 메소드를 사용할 것을 권장한다.

 

LinkedList 객체를 하나씩 검색하기 위한 Iterator

리턴 타입	메소드 이름 및 매개 변수	설명
ListIterator	listIterator(int)	매개 변수에 지정된 위부터의 데이터를 검색하기 위한 ListIterator 객체를 리턴한다.
Iterator	descendingiterator()	LinkedList의 데이터를 끝에서부터 검색하기 위한 Iterator 객체를 리턴한다.

 

stack 클래스는 뭘까?

일반적으로 웹개발 할 때나 또는 LIFO기능을 위해서 이 클래스를 사용하는 것은 권장하지 않는다. 왜냐하면 ArrayDeque라는 클래스가 존재하기 때문이다. 하지만 ArrayDeue 클래스는 쓰레드에 안전하지 못하다. 약간 성능은 떨어지지만, 쓰레드에 안전한 LIFO 기능을 원한다면 이 Stack 클래스를 사용하면 된다.

ArrayDeque란?? java.util.ArrayDeque 클래스는 Queue 및 Deque의 구현 클래스로서 배열을 이용해 규와 데크를 구현 함.

java.lang.Object - java.util - AbstractCollection<E> - java.utilAbstractList<E> - java.util.Vector<E>-java.util.Stack<E>

 

부모 클래스가 Vector이기 때문에 Vector 클래스에서 제공하는 모든 메소드를 사용할 수 있다. 나머지는 위에 ArrayList와 동일하기 때문에 위를 참조하면 된다.

 

stack 클래스는 자바에서 상속을 잘못 받은 클래스다. 이 클래스가 JDL 1.0부터 존재했기 때문에 원래의 취지인 LIFO를 생각한다면 Vector에 속해서는 안 된다. 하지만, 자바의 하위 호환성을 위해서 이 상속관계를 유지하고 있다고 생각하면 된다. 

 

Stack 클래스의 생성자는 단 하나

생성자	설명
Stack()	아무 데이터도 없는 Stack 객체를 만든다.

 

Stack클래스의 메서드

리턴 타입	메소드 이름 및 매개변수	설명
boolean	empty()	객체가 비어있는지를 확인한다.
E	peek()	객체의 가장 위에 있는 데이터를 리턴한다
E	pop()	객체의 가장 위에 있는 데이터를 지우고, 리턴한다.
E	pusj(E item)	매개 변수로 넘어온 데이터를 가장 위에 저장한다.
int	search(Object o)	매개 변수로 넘어온 데이터의 위치를 리턴한다.

 

그럼 Array와 ArrayList 중 무엇을 사용하는 것이 더 좋을까?

배열이 성능상 메모리나 효율면에서 가장 좋다. 배열은 초기화시 메모리에 할당되어 속도가 빠르다. 또 다차원 배열이 가능하다. 하지만 사이즈가 고정되어 있고, 사이즈를 변경할 수 가 없다. 

 

그래서 담으려는 데이터의 크기가 얼마나 되는지 모르는 경우엔 어떻게 해야하나? 지금까지의 설명으로 유추해보면,

 

- int의 최대값에 해당하는 크기를 갖는 배열을 만든다. -> 메모리 낭비

- 배열의 크기가 부족하면, 필요한 개수만큼 더 큰 배열을 하나 더 만들어서 거기다가 복사한다. 

 

위 2가지의 방법은 메모리 낭비와 시간이 많이 발생한다. 그래서 이럴때 List를쓴다.

 

List는 추가시 메모리를 재할당하여 배열보다 속도가 느리지만 (배열을 사용할때 크기가 부족할 경우, 필요한 개수만큼 더 큰 배열을 만들때 얼마나 더 큰 배열을 만드냐의 따라 속도는 다르곘지만) , 

초기화시 사이즈가 고정되지 않기 때문에 유동적이며, 또 동적으로 값의 추가, 삭제 기능이 가능하다.

 

둘 중에 적절한 상황에 맞게 쓰는 것이 답인 것 같다.

 

ArrayList와 LinkedList의 차이

 

검색 = ArrayList가 빠르다.

 ArrayList는 인덱스 기반의 자료 구조이며 get(int index) 를 통해 O(1) 의 시간 복잡도를 가진다. 그에 비해 LinkedList는 검색 시 모든 요소를 탐색해야 하기 때문에 최악의 경우에는 O(N)의 시간 복잡도를 가진다.

 

중간데이터 추가 / 삭제 = LinkedList가 빠르다.

LinkedList에서의 데이터의 삽입, 삭제 시에는 ArrayList와 비교해 굉장히 빠른데, LinkedList는 이전 노드와 다음 노드를 참조하는 상태만 변경하면 되기 때문이다. 삽입, 삭제가 일어날 때 O(1)의 시작 복잡도를 가진다. 반면 ArrayList의 경우 삽입, 삭제 이후 다른 데이터를 복사해야 하기 때문에 최악의 경우 O(N) 의 성능을 내게 된다.

 

마지막에서부터 데이터를 삭제할 때 = ArrayList가 빠르다.

마지막에서부터 데이터를 삭제할 경우 각 데이터들의 재배치가 필요하지 않기 때문에 ArrayList가 더 빠르다.

 

결론

- 삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다.

- 데이터의 접근하는게 중요하다면 ArrayList를 사용하는 것이 좋다.

 

Collection의 Set. Queue 알아보기 , map 알아보기

참고 : 자바의 신 / 이상민