1. java.util.LinkedList 개괄
- 원형 이중 연결 리스트의 형태로 구현
- 한 노드가 다른 노드를 연결/분리하는 방식으로 동작
- 기본적으로는 비동기화된 리스트이기 때문에, 동기화가 필요한 경우
Collections.synchronizedList(new LinkedList(…))와 같이 wrapping하여 사용
연관된 인터페이스/클래스
상위 인터페이스(Java 17 기준)
java.util.Queue
- 큐의 핵심 기능을 다루는 메서드 시그니처가 정의된 인터페이스
java.util.Deque
- 덱의 핵심 기능을 담당하는 메서드의 시그니처가 정의된 인터페이스
상위 클래스
java.util.AbstractSequentialList
- 순차 접근을 통해서만 데이터에 접근할 수 있는 선형 자료구조(연결리스트, 큐, 덱 등)의 기본 골격을 제공하기 위한 추상 클래스
- 메서드 오버라이딩을 통해
java.util.AbstractList의 임의 접근 방식을 순차 접근 방식으로 재정의
ps) 따로 다루지 않은 인터페이스나 클래스는 여기를 참조
2. java.util.LinkedList의 메서드
cf1) 데이터 삽입, 삭제, 접근 기능을 중심으로 정리
cf2) List 인터페이스와 Collection 인터페이스에 이미 정의된 부수적인 메서드는 제외
(두 인터페이스에 정의된 주요 메서드는 여기에서 확인 가능)
cf3) Queue 인터페이스에 정의된 메서드와 Deque 인터페이스의 일부 메서드는 큐/덱 관련 내용에서 별도로 정리함
LinkedList의 데이터 노드 구현
Node 클래스
java.util.LinkedList의 내부 클래스java.util.LinkedList클래스의 데이터 노드 클래스는 이전 노드와 다음 노드를 가리키는 참조변수를 모두 멤버변수로 사용
:java.util.LinkedList는 이중 연결 리스트
LinkedList의 주요 필드
int size: LinkedList의 크기, 즉 데이터 노드의 개수를 의미
Node<E> first: LinkedList의 머리 노드를 가리키는 변수
Node<E> last: LinkedList의 꼬리 노드를 가리키는 변수
cf) transient
: java 언어에서 사용되는 예약어의 일종으로, 이 예약어를 사용하여 선언된 변수/필드는 Java 객체를 바이트 코드로 변환하는 직렬화의 대상에서 제외됨
LinkedList의 생성자
LinkedList()
- 연결된 노드의 개수가 0개인 LinkedList 객체를 생성
LinkedList(Collection c)
- 주어진 컬렉션을 포함하는 LinkedList를 생성
데이터 노드 추가/삽입
데이터 노드 추가/삽입의 핵심 동작
- 새로운 데이터 노드(이하 노드)를 생성
- 지정한 위치의 이전 노드의 참조를 새로운 노드에 대한 참조로 변경
- 지정한 위치의 다음 노드를 새로운 노드가 참조하도록 변경
데이터 노드 추가/삽입의 핵심 동작 관련 메서드
private void linkFirst(Object e)
- 지정한 데이터를 가진 노드를 새로 생성한 후 LinkedList의 맨 앞에 연결
addFirst(E e)의 핵심 동작을 구현한 메서드
void linkLast(Object e)
- 지정한 데이터를 가진 노드를 새로 생성한 후 LinkedList의 맨 뒤에 연결
void add(Object o)와void addLast(Object o)의 핵심 동작을 수행하는 메서드
void linkBefore(Object e, Node<E> succ)
- 지정한 노드의 이전 노드로 주어진 데이터 노드를 연결
add(int index, Object element)의 핵심 동작을 구현
: LinkedList의 중간에 노드를 삽입할 때 사용
단일 데이터 노드 추가/삽입 메서드
java.util.List 인터페이스의 메서드 구현
void add(int index, Object element)
- LinkedList의 지정한 위치에 데이터 노드 element를 삽입
- LinkedList의 맨 앞 또는 맨 뒤부터 시작하여 순차적으로 접근하는 방식으로 지정된 위치에 접근
void add(Objet element)
- 지정된 객체를 LinkedList의 맨 끝에 추가
java.util.Deque 인터페이스의 메서드 구현
void addFirst(Object o)/void addLast(Object o)
- 지정한 데이터를 가진 노드를 LinkedList의 첫번째/마지막 노드로 저장
- LinkedList에 노드가 하나도 없을 경우
NoSuchElementException발생
boolean offerLast(Object o)/boolean offerLast(Object o)
- 지정한 데이터를 가진 노드를 LinkedList의 첫번째/마지막 노드로 저장
addFirst()와addLast()메서드를 이용하여 각각 구현
void push(Object o)
addFirst()와 동일한 기능을 수행- 덱의 기능을 기반으로 스택의 데이터 추가 기능을 구현
컬렉션 단위 데이터 노드 추가/삽입
boolean addAll(int index, Collection c)
- LinkedList의 지정된 위치에 주어진 컬렉션에 포함된 모든 요소를 삽입
boolean addAll(Collection)
- 주어진 컬렉션에 포함된 모든 요소를 LinkedList의 끝에 추가
boolean addAll(int index, Collection c)메서드에 의해 구현됨
데이터 노드 삭제
데이터 노드 삭제의 핵심 동작
- 삭제하려는 데이터 노드의 이전 노드가 삭제하려는 노드의 바로 다음 노드를 참조하도록 변경
데이터 노드 삭제의 핵심 동작 관련 메서드
private Object unlinkFirst(Node f)
- 첫번째 노드를 LinkedList에서 분리한 후 그 다음 노드로 머리 노드를 변경
removeFirst()의 핵심 동작을 구현한 메서드
private Object unlinkLast(Node l)
- 마지막 노드를 LinkedList에서 분리한 후 그 이전 노드로 꼬리 노드를 변경
removeLast()의 핵심 동작을 구현한 메서드
Object unlink(Node x)
- 지정한 노드를 연결리스트에서 삭제하기 위해 해당 노드의 앞뒤 노드 간 연결관계를 조정한 후, 삭제하려는 노드에 할당된 메모리를 해제
Object remove(int index)의 핵심 동작을 구현한 메서드
: 주로 연결 리스트 중간에 위치한 노드를 삭제할 때 사용되는 메서드
단일 데이터 노드 삭제 메서드
java.util.List 인터페이스의 메서드 구현
Object remove(int index)
- 지정한 위치에 저장된 노드를 연결리스트에서 삭제
java.util.AbstractSequentialList의 메서드를 오버라이딩하여 구현
: 순차 접근 방식으로만 지정된 노드에 접근 가능,node()메서드를 통해 순차 접근 수행
boolean remove(Object o)
- LinkedList에서 첫번째로 일치하는 객체를 찾아서 제거
- LinkedList의 첫번째 노드부터 순차적으로 탐색
removeFirstOccurence(Object o)메서드를remove(Object o)로 구현
java.util.Deque 인터페이스의 메서드 구현
Object removeFirst()/Object removeLast()
- LinkedList의 첫번째/마지막 노드를 연결리스트에서 삭제
- LinkedList에 노드가 하나도 없을 경우
NoSuchElementException발생
Object pollFirst()/Object pollLast()
- LinkedList의 첫번째/마지막 노드를 연결리스트에서 삭제
- LinkedList에 노드가 하나도 없을 경우 null을 반환
boolean removeFirstOccurence(Object o)
- LinkedList에서 첫번째로 일치하는 객체를 찾아서 제거
- LinkedList의 첫번째 노드부터 순차적으로 탐색
remove(Object o)를 바탕으로 구현
boolean removeLastOccurence(Object o)
- LinkedList에서 마지막으로 일치하는 객체를 찾아서 제거
- LinkedList의 마지막 노드부터 역순으로 탐색
Object pop()
removeFirst()와 동일한 기능을 수행- 덱의 기능을 기반으로 스택의 데이터 삭제 기능을 구현
컬렉션 단위의 데이터 노드 삭제
boolean removeAll(Collection c)/boolean retainAll(Collection c)
java.util.LinkedList에서 직접 오버라이딩하여 구현하는 대신java.util.AbstractCollection에 이미 구현된 메서드를 그대로 사용
: Iterator 객체를 사용하여 LinkedList의 각 노드에 접근
데이터 노드 접근
데이터 노드 접근 보조용 메서드
Node<E> node(int index)
- 첫번째/마지막 노드 중 한 곳을 탐색의 시작점으로 설정한 다음 지정한 노드까지 순차 접근을 수행
- 리스트 내 노드의 위치를 나타내기 위해 편의상 인덱스를 사용할 뿐, 임의 접근은 불가능
java.util.List 인터페이스 메서드 구현
Object get(int index)
- LinkedList에서 지정된 위치의 노드에 저장된 객체를 반환
java.util.Deque 인터페이스 메서드 구현
Object getFirst()/Object getLast()
- LinkedList의 첫번째/마지막 노드에 저장된 객체를 반환
- LinkedList에 노드가 하나도 없을 경우
NoSuchElementException발생
Object peekFirst()/Object peekLast()
- LinkedList의 첫번째/마지막 노드에 저장된 객체를 반환
- LinkedList에 노드가 하나도 없을 경우 null을 반환
Reference
- 자바의 정석 3판 (남궁성 지음)
- Java 공식 문서 - LinkedList
