[DataStructure] Java에서 Linked List는 Queue와 List를 모두 사용할 수 있다. + (Iterable, Collection, List, Queue ... 요약)

코딩 테스트 문제를 풀면서 문득 'LinkedList는 List로도 사용할 수 있고, Deque로도 사용할 수 있는 것 같네' 란 생각이 들었는데요, List와 Deque를 모두 구현하고 있었군요.

위 이미지는 LinkedList가 상속하고 구현하고 있는 클래스, 인터페이스 들을 다이어그램으로 표시한 그림인데요, 

이 글에서는 이 LinkedList와 관련된 각 클래스, 인터페이스를 살펴보고자 합니다.

Iterable

Iterable 인터페이스는 Java에서 컬렉션을 순회하는 표준 방법을 제공한다. 이 인터페이스는 컬렉션의 요소들을 순회할 수 있도록 해준다. 

Iterator<T> iterator()

Iterable 인터페이스는 Java에서 컬렉션을 순회하는 표준 방법을 제공한다.

주요 메서드는 다음과 같다.

1. Iterator<T> iterator(): 컬렉션의 요소를 순회할 수 있는 Iterator<T>를 반환한다. Iterator는 hasNext(), next(), remove() 메서드를 제공한다.
2. default void forEach(Consumer<? super T> action): 각 요소에 대해 주어진 action 을 수행한다. for-each 문과 유사하게 동작하며, 요소를 순회하면서 Consumer를 통해 동작을 수행한다.
3. default Spliterator<T> spliterator(): Spliterator<T>를 생성하여 반환한다. Spliterator는 컬렉션의 요소를 분할하고 병렬 처리를 지원한다. 기본 구현은 Spliterators.spliteratorUnknownSize(iterator(), 0)를 사용하지만, 성능 향상을 위해 재정의하는 것이 좋다.

Collection

Collection 인터페이스는 Java의 다양한 Collection을 관리하기 위한 기본적인 동작을 정의한다.

여기서 Collection이란 여러 개의 객체를 하나의 단위로 묶어서 관리하기 위한 인터페이스이다.

 

주요 기능은 다음과 같다.

쿼리(조회) 연산

• size(): 컬렉션의 요소 개수를 반환
• isEmpty(): 컬렉션이 비어 있는지 여부를 반환
• contains(Object o): 특정 요소가 컬렉션에 포함되어 있는지 여부를 반환
• iterator():컬렉션의 요소를 순회할 수 있는 `Iterator`를 반환
• toArray(), toArray(T[] a): 컬렉션의 모든 요소를 배열로 반환

수정 연산

• add(E e)는 컬렉션에 요소를 추가하고, 성공 시 true를 반환
• remove(Object o)는 컬렉션에서 특정 요소를 제거하고, 성공 시 true를 반환

벌크 연산

• containsAll(Collection<?> c): 지정된 컬렉션의 모든 요소가 이 컬렉션에 포함되어 있는지 확인
• addAll(Collection<? extends E> c): 지정된 컬렉션의 모든 요소를 이 컬렉션에 추가
• removeAll(Collection<?> c): 이 컬렉션에서 지정된 컬렉션에 포함된 모든 요소를 제거
• removeIf(Predicate<? super E> filter): 지정된 조건에 맞는 모든 요소를 제거
• retainAll(Collection<?> c): 지정된 컬렉션에 포함된 요소만 남기고 나머지를 제거
• clear(): 컬렉션의 모든 요소를 제거

비교와 해싱

• equals(Object o): 이 컬렉션과 지정된 객체가 동일한지 확인
• hashCode(): 이 컬렉션의 해시 코드를 반환

스트림 연산

• spliterator(): 컬렉션의 요소를 분할할 수 있는 `Spliterator`를 반환
• stream(): 이 컬렉션을 소스로 하는 순차 스트림을 반환
• parallelStream(): 이 컬렉션을 소스로 하는 병렬 스트림을 반환

List

List 인터페이스는 Collection 인터페이스의 하위 인터페이스로, 요소들의 순서를 유지하는 컬렉션을 정의한다.

이 인터페이스를 구현하는 클래스들은 요소를 특정 위치에 삽입하거나 제거할 수 있다.

또한, 요소의 인덱스를 기반으로 접근할 수 있는 메서드들을 제공한다. 그리고 중복을 허용한다,

순서가 있기 때문에, void sort(Comparator c)로 지정된 Comparator를 사용하여 정렬이 가능하다.

위치 기반 접근 연산

• E get(int index) : 지정된 위치에 있는 요소를 반환
• E set(int index, E element): 지정된 위치의 요소를 주어진 요소로 대체하고, 이전 요소를 반환
• void add(int index, E element): 지정된 위치에 요소를 삽입
• E remove(int index): 지정된 위치의 요소를 제거하고, 제거된 요소를 반환
• int indexOf(Object o): 리스트에서 특정 요소의 첫 번째 발생 위치를 반환
• int lastIndexOf(Object o)`**: 리스트에서 특정 요소의 마지막 발생 위치를 반환

리스트 반복자

• ListIterator<E> listIterator(): 리스트의 요소를 순회할 수 있는 ListIterator를 반환
• ListIterator<E> listIterator(int index): 지정된 위치에서 시작하는 리스트의 요소를 순회할 수 있는 ListIterator를 반환

서브리스트 뷰

• List<E> subList(int fromIndex, int toIndex): 지정된 범위의 요소를 포함하는 서브리스트를 반환

Java 9 이후 추가된 정적 메서드

• List<E> of(E... elements): 주어진 요소들을 포함하는 불변 리스트를 반환
• List<E> copyOf(Collection<? extends E> coll): 주어진 컬렉션의 요소를 포함하는 불변 리스트를 반환

AbstractCollection, AbstractList, AbstractSequentialList

Java Collections Framework에는 추상 클래스들이 포함되어 있다. 이러한 추상 클래스들은 일반적으로 일부 기본 동작을 구현하여 구체적인 Collection 구현 클래스들이 상속받아 사용할 수 있도록 설계되었다. AbstractCollection, AbstractList, AbstractSequentialList는 이러한 추상 클래스들 중 일부이다. 각각의 클래스는 특정한 Collection 타입을 위한 공통된 동작을 제공한다.

AbstractCollection

AbstractCollection 클래스는 Collection 인터페이스를 구현하는 모든 클래스의 기본 구현을 제공한다. 이 클래스는 대부분의 Collection 메서드를 구현하지만, iterator()와 size() 메서드는 구현하지 않는다. 이 클래스는 Collection 인터페이스의 다른 메서드를 기반으로 기본 동작을 제공하기 위해 설계되었다.

AbstractList

AbstractList 클래스는 List 인터페이스를 구현하는 클래스들을 위한 기본 구현을 제공한다. 이 클래스는 AbstractCollection 클래스를 상속받으며, List 인터페이스의 구체적인 동작을 추가로 정의한다. 

AbstractList 클래스는 임의 접근(Random Access) 방식의 List 구현체를 위해 설계되었다. 이를 상속받는 클래스는 효율적인 인덱스 접근을 제공해야 한다. (e.g. ArrayList, Vector, ArrayDeque)

AbstractSequentialList

AbstractSequentialList 클래스는 List 인터페이스를 구현하는 클래스 중 연결 리스트(Linked List)와 같은 순차 접근(Sequential Access) 방식의 List를 위한 기본 구현을 제공한다. 이 클래스는 AbstractList 클래스를 상속받으며, `List` 인터페이스의 동작을 순차 접근 방식으로 구현한다.
AbstractSequentialList는 순차 접근이 효율적인 List 구현체를 위해 설계되었다. (e.g. LinkedList, Queue, Stack)

Queue

Queue 인터페이스는 Java Collections Framework의 일부분으로, 요소를 처리하기 전에 저장하는 데 사용되는 컬렉션을 정의한다. 이 인터페이스는 기본적인 Collection 작업 외에도 삽입, 추출 및 검사의 세 가지 주요 연산을 제공한다. 각 연산은 예외를 던지거나 특별한 값을 반환하는 두 가지 형태로 존재한다.

Queue 인터페이스에는 다음과 같은 주요 메서드들이 있다.

삽입 메서드

• boolean add(E e): 큐의 끝에 요소를 삽입하며, 큐의 용량 제한에 위배될 경우 예외를 던진다.
• boolean offer(E e): 큐의 끝에 요소를 삽입하며, 용량 제한에 도달하면 false를 반환한다.

제거 메서드

• E remove(): 큐의 앞에서 요소를 제거하고 반환하며, 큐가 비어 있으면 예외를 던진다.
• E poll(): 큐의 앞에서 요소를 제거하고 반환하며, 큐가 비어 있으면 null 을 반환한다.

검사 메서드

• E element(): 큐의 앞에 있는 요소를 반환하며, 큐가 비어 있으면 예외를 던진다.
• E peek(): 큐의 앞에 있는 요소를 반환하며, 큐가 비어 있으면 null을 반환한다.

Deque

Deque(Double Ended Queue)는 Queue를 확장하는 인터페이스로, 요소를 양쪽 끝에서 삽입하고 제거할 수 있는 기능을 추가로 제공한다. 즉 Deque는 FIFO와 LIFO(Last-In-First-Out) 모두 지원하는 자료구조이다. 

Deque는 addFirst(E e), addLast(E e), removeFirst(), removeLast(), getFirst(), getLast(), peekFirst(), peekLast() 등 양쪽 끝을 조작하는 추가 메서드를 제공한다.

Deque는 스택처럼 동작할 수 있도록 push(E e)와 pop() 메서드를 제공하며, 이 메서드들은 Deque를 Stack처럼 사용할 수 있게 한다.

Clonable과 Serializable

Java에서 Cloneable과 Serializable은 특별한 역할을 하는 Marker 인터페이스이다.

Cloneable

Cloneable 인터페이스는 객체의 얕은 복사를 허용하는 인터페이스이다. 객체가 Cloneable 인터페이스를 구현하면 Object\ 클래스의 clone() 메서드를 호출할 수 있다. 이 인터페이스를 구현하지 않으면 clone() 메서드를 호출할 때 CloneNotSupportedException이 발생한다.
얕은 복사(Shallow Copy)만 수행하므로, 객체 내의 참조형 필드들은 복사되지 않고 원본 객체와 같은 객체를 참조하게 된다.

Serializable

Serializable 인터페이스는 객체가 직렬화 가능함을 나타내는 인터페이스이다.

직렬화는 객체의 상태를 byte 스트림으로 변환하여 파일로 저장하거나 네트워크를 통해 전송할 수 있게 한다.

직렬화된 객체는 나중에 역직렬화를 통해 원래의 상태로 복원할 수 있다.
직렬화 과정에서 특정 필드를 제외하려면 transient 키워드를 수 있다.

LinkedList

LinkedList 클래스는 List와 Deque 인터페이스를 구현하는 이중 연결 리스트이다. 이 클래스는 모든 선택적 List 작업을 지원하며, null을 포함한 모든 요소를 허용한다.

주요 기능 및 특징

이중 연결 리스트 구조

• LinkedList는 이중 연결 리스트(doubly-linked list)로 구현된다. 각 노드는 이전 노드와 다음 노드를 참조한다. 이러한 구조를 통해 요소의 삽입과 삭제가 빠르게 이루어질 수 있다.
• 인덱스를 통한 접근 시, 인덱스에 따라 리스트의 시작 또는 끝에서부터 가장 가까운 쪽으로부터 탐색을 시작한다.

동기화되지 않음

• 기본적으로 LinkedList는 동기화되지 않는다. 여러 스레드가 동시에 리스트에 접근하고, 그 중 하나 이상의 스레드가 List를 구조적으로 수정하면, 외부에서 동기화를 해야 한다.
• 구조적 수정이란 요소를 추가하거나 삭제하는 모든 작업을 포함하며, 단순히 요소의 값을 설정하는 작업은 포함되지 않는다다
• 동기화는 List를 자연스럽게 캡슐화하는 객체를 사용하여 수행하거나, Collections.synchronizedList 메서드를 사용하여 리스트를 생성할 때 동기화된 List로 Wrapping 할 수 있다.

 반복자 (Iterator)

• LinkedList의 iterator 및 listIterator 메서드가 반환하는 반복자는 fail-fast 동작을 한다.
• 이는 Iterator가 생성된 이후에 리스트가 구조적으로 수정되면, 반복자는 ConcurrentModificationException을 발생시킨다. 따라서 Iterator 는 동기화되지 않은 동시 수정에 대해 실패하여, 비결정적이고 임의의 동작이 발생할 가능성을 줄인다.
• 그러나, 이 fail-fast 동작은 완전히 보장되지 않으며,  프로그램의 정확성을 위해 이 예외에 의존하는 것은 바람직하지 않고 주로 버그를 감지하기 위해 사용되어야 한다.

Java Collections Framework의 멤버

• LinkedList 클래스는 Java Collections Framework의 일부입니다. 이는 LinkedList가 Java의 표준 Collection API와 호환된다는 것을 의미한다.

그럼 ArrayList, Deque를 구분하지 않고, LinkedList만 사용한다면?

ArrayList vs LinkedList

시간 복잡도 비교

연산	LinkedList	ArrayList
접근 (Access)	O(n)	O(1)
검색 (Search)	O(n)	O(n)
삽입 (Insertion)	O(1) (특정 위치 접근 후)	O(n) (평균), O(1) (끝)
삭제 (Deletion)	O(1) (특정 위치 접근 후)	O(n) (평균)

메모리 효율성 비교

• LinkedList: 각 노드가 데이터 외에 두 개의 포인터(prev, next)를 저장해야 하므로 메모리 사용량이 많음.
• ArrayList: 연속된 메모리 블록에 데이터를 저장하므로 메모리 사용량이 적음. 배열 크기를 늘릴 때 잠시 더 많은 메모리를 사용하지만, 이는 드문 경우임.

ArrayDeque vs LinkedList

시간 복잡도 비교

연산	LinkedList	ArrayDeque
접근 (Access)	O(n)	O(1) (양쪽 끝)
검색 (Search)	O(n)	O(n)
삽입/삭제 (Insertion/Deletion)	O(1) (특정 위치 접근 후)	O(1) (양쪽 끝에서)

메모리 효율성 비교

• LinkedList: 각 노드가 데이터 외에 두 개의 포인터(prev, next)를 저장해야 하므로 메모리 사용량이 많음.
• ArrayDeque: 연속된 메모리 블록에 데이터를 저장하므로 메모리 사용량이 적음. 배열 크기를 늘릴 때 잠시 더 많은 메모리를 사용하지만, 이는 드문 경우임.

따라서 ArrayList, ArrayDeque에 비해 메모리 효율성이 떨어지고, LinkedList는 중간에 삽입/삭제가 빈번하게 이루어질 때 사용하는 것이 유리하다.

마치며

코딩테스트에서 그냥 모든 Deque, Stack, ArrayList 와 같은 자료구조를 LinkedList로 통일시키면 편하지 않을까? 라는 궁금증에 시작된 공부인데, 거의 핵심 자료구조들을 공부하게된 것 같다.