[Java] 2. List

List?

List는 컬렉션 프레임워크에서 제공하는 컬렉션 클래스 중 하나이다.

 

컬레션 프레임워크의 핵심 인터페이스에는 대표적으로 List, Set, Map이 있는데

여기서 List는 순서가 있고 데이터의 중복을 허용하는 특징이 있다.

 

List 인터페이스의 구현 클래스에는 ArrayList, LinkedList, Stack, Vector 등이 있다.

 

ArrayList

• ArrayList는 컬렉션 프레임워크에서 가장 많이 사용되는 컬렉션 클래스이다.
• ArrayList는 기존의 Vector를 개선한 것으로 Vector와 구현원리과 기능적인 측면에서 동일하며 Vector는 기존에 작성된 소스와의 호환을 위해 남겨두고 있을 뿐이기 때문에 가능하면 ArrayList를 사용하는 것이 좋다.
• ArrayList를 생성할 때, 저장할 요소의 개수를 고려해서 실제 저장할 개수보다 약간 여유 있는 크기로 하는 것이 좋다. -> 크기를 늘리는 과정의 처리시간이 많이 소요되기 때문

 

LinkedList

• 배열의 단점을 보완하기 위해서 고안되었다. -> 배열의 단점: 크기를 변경할 수 없다, 데이터 추가 및 삭제에 시간이 많이 걸린다.
• LinkedList는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있다.
• LinkedList의 추가, 삭제는 요소의 참조만 변경하면 되기 때문에 처리속도가 매우 빠르다.
• LinkedList는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵다. 이 점을 보완한 것이 Doubly Linked List이다. 이를 더 보완하여 접근성을 향상시킨 것이 Doubly Circular Linked List이다.

 

element()와 peek()의 차이

element()와 peek() 모두 첫 번재 요소를 반환하는 함수이다. 이 두 함수 사이의 차이점이 무엇인지 살펴보자.

• element(): 요소가 존재하지 않을 경우 NoSuchElementException을 발생시킨다.
• peek(): 요소가 존재하지 않을 경우 null값을 반환한다.

이외에도 remove()와 poll(), add()와 offer()도 위와 같은 차이를 가지며 자세한 내용은 Oracle 문서에서 확인할 수 있다.

 

in Oracle docs

Queue, Deque 인터페이스를 구현하면서 추가된 getFirst(), peekFirst() 함수도 위와 같은 차이가 있다.
getFirst() -> NoSuchElementException, peekFirst() -> null 반환

 

ArrayList vs LinkedList

그럼 어느 상황에 어떤 컬렉션을 써야할지 살펴보자.

• 먼저 순차적으로 데이터를 추가/삭제하는 경우에는 ArrayList가 더 빠르다.
  • 하지만 ArrayList의 크기가 충분하지 않아서 새로운 크기의 ArrayList를 생성하고 복사하는 일이 발생하게 된다면 LinkedList가 더 빠를 수 있다.
  • ArrayList는 마지막 데이터부터 삭제할 경우 각 요소들의 재배치가 필요하지 않기 때문에 빠르다.
• 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 더 빠르다.
  • LinkedList는 각 요소간의 연결만 변경해주면 되기 때문에 처리속도가 상당히 빠르다.
• LinkedList는 데이터가 많을수록 접근시간이 길어진다.
  • 배열은 각 요소들이 연속적으로 메모리상에 존재하기 때문에 간단한 계산만으로 원하는 요소의 주소를 얻어서 저장된 데이터를 곧바로 읽어올 수 있다.
  • 하지만 LinkedList는 불연속적으로 위치한 각 요소들이 서로 연결된 것이기 때문에 처음부터 n번째 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있다.
• 데이터 개수의 변경이 잦다면 LinkedList를 사용하는 것이 더 나을 수 있다.

 

Stack & Queue

• 스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out)구조로 되어있다.
• 큐는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In Fisrt Out)구조로 되어있다.
• 순차적으로 데이터를 추가하고 삭제하는 스택에는 ArrayList와 같은 배열기반의 컬렉션 클래스가 적합하다.
• 큐는 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로, ArrayList보다 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 더 적합하다. -> ArrayList와 같은 배열기반의 컬렉션 클래스르 사용한다면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적이다.
• 자바에서는 스택을 Stack 클래스로 구현하여 제공하고 있지만 큐는 Queue 인터페이스로만 정의해 놓았을 뿐 별도의 클래스를 제공하고 있지 않다. 대신 Queue 인터페이스를 구현한 클래스들이 있어서 이 들 중의 하나를 선택해서 사용하면 된다.

 

Priority Queue

• Queue 인터페이스의 구현체 중 하나로, 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내게 된다는 특징이 있다. null은 저장할 수 없다.
• PriorityQueue는 저장공간으로 배열을 사용하며, 각 요소를 힙(heap)이라는 자료구조의 형태로 저장한다.

 

Deque

• Queue의 변형으로, 한 쪽 끝으로만 추가/삭제할 수 있는 Queue와 달리, Deque은 양쪽 끝에 추가/삭제가 가능하다. Deque의 조상은 Queue이며, 구현체로는 ArrayDeque과 LinkedList 등이 있다.