1. 소개
LinkedList 는 List 및 Deque 인터페이스의 이중 연결 List 구현입니다. 모든 선택적 List 작업을 구현하고 모든 요소( null 포함 )를 허용합니다.
2. 특징
아래에서 LinkedList 의 가장 중요한 속성을 찾을 수 있습니다 .
- List을 인덱싱하는 작업은 시작 또는 끝 중 지정된 인덱스에 가까운 쪽부터 List을 순회합니다.
- 동기화 되지 않음
- 그것의 Iterator 및 ListIterator 반복자는 fail-fast 입니다(즉, 반복자가 생성된 후 List이 수정되면 ConcurrentModificationException 이 발생함)
- 모든 요소는 다음 및 이전 항목에 대한 참조를 유지하는 노드입니다.
- 삽입 순서를 유지합니다.
LinkedList 가 동기화되지는 않았지만 다음과 같이 Collections.synchronizedList 메서드 를 호출하여 동기화된 버전을 검색할 수 있습니다 .
List list = Collections.synchronizedList(new LinkedList(...));3. ArrayList 와의 비교
둘 다 List 인터페이스를 구현하지만 의미론이 다르므로 사용할 것을 결정하는 데 확실히 영향을 미칩니다.
3.1. 구조
ArrayList 는 Array 가 지원 하는 인덱스 기반 데이터 구조 입니다. O(1)과 동일한 성능으로 해당 요소에 대한 임의 액세스를 제공합니다.
반면에 LinkedList 는 데이터를 요소 List으로 저장하고 모든 요소는 이전 요소와 다음 요소에 연결됩니다. 이 경우 항목 검색 작업의 실행 시간은 O(n)입니다.
3.2. 운영
항목의 삽입, 추가 및 제거 작업은 요소가 컬렉션 내의 랜덤의 위치에 추가될 때 배열 크기를 조정하거나 인덱스를 업데이트할 필요가 없기 때문에 LinkedList 에서 더 빠릅니다. 주변 요소의 참조만 변경됩니다.
3.3. 메모리 사용량
LinkedList 는 LinkedList 의 모든 노드가 이전 요소와 다음 요소에 대한 두 개의 참조를 저장하는 반면 ArrayList 는 데이터와 인덱스만 보유 하기 때문에 ArrayList 보다 더 많은 메모리 를 사용합니다.
4. 사용법
다음은 LinkedList 를 사용하는 방법을 보여주는 몇 가지 코드 샘플입니다 .
4.1. 창조
LinkedList<Object> linkedList = new LinkedList<>();4.2. 요소 추가
LinkedList 는 표준 add() 및 addAll() 메서드 외에 각각 시작 또는 끝에 요소를 추가하는 addFirst() 및 addLast() 를 찾을 수 있는 List 및 Deque 인터페이스를 구현 합니다.
4.3. 요소 제거
요소 추가와 유사하게 이 List 구현은 removeFirst() 및 removeLast()를 제공합니다.
또한 부울(컬렉션에 지정된 요소가 포함된 경우 true)을 반환하는 편리한 메서드 removeFirstOccurence() 및 removeLastOccurence() 가 있습니다.
4.4. Queue 작업
Deque 인터페이스는 큐와 유사한 동작을 제공합니다(실제로 Deque 는 Queue 인터페이스를 확장함) .
linkedList.poll();
linkedList.pop();이러한 메서드는 첫 번째 요소를 검색하고 List에서 제거합니다.
poll() 과 pop() 의 차이점은 pop 은 빈 리스트에서 NoSuchElementException() 을 발생시키는 반면 poll 은 null을 반환 한다는 것입니다. pollFirst() 및 pollLast( ) API 도 사용할 수 있습니다.
예를 들어 푸시 API가 작동 하는 방식은 다음과 같습니다.
linkedList.push(Object o);요소를 컬렉션의 헤드로 삽입합니다.
LinkedList 에는 다른 많은 메서드가 있으며 대부분 이미 Lists 를 사용한 사용자에게 친숙할 것 입니다. Deque 에서 제공하는 다른 방법은 "표준" 방법에 대한 편리한 대안이 될 수 있습니다.
전체 문서는 여기 에서 찾을 수 있습니다 .
5. 결론
ArrayList 는 일반적으로 기본 List 구현입니다.
그러나 일정한 액세스 시간 및 효과적인 메모리 사용보다 지속적인 삽입/삭제 시간(예: 빈번한 삽입/삭제/업데이트)에 대한 기본 설정과 같이 LinkedList 를 사용하는 것이 더 적합한 특정 사용 사례 가 있습니다.
코드 샘플은 GitHub 에서 찾을 수 있습니다 .
