LinkedList

https://www.baeldung.com/java-linkedlist

 

1. 소개

LinkedList는 list와 Deque인터페이스의 이중 연결 리스트 구현체로 모든 선택적 리스트 연산을 구현하고 모든 요소(null 포함)을 허용한다.

 

2. 특징

• list를 인덱싱하는 작업은 지정된 인덱스에 더 가까운 첫번째 혹은 마지막부터 목록을 탐색한다.
• 동기화 되지 않는다.
• Iterator과 ListIterator은 fail-fast 이다.
  • iterator가 생성된 후 List가 수정되면 ConcurrentModificationException이 반환된다.
• 모든 요소는 이전, 이후 요소에 대한 참조를 가지고 있으며 Node라 한다.
• 삽입 순서를 유지한다.

LinkedList는 비동기이며 동기로 사용하고 싶으면 Colldections.syncronizedList를 사용해야 한다.

 

3. ArrayList와 비교하기

둘다 List 인터페이스를 구현하지만 다른 문법을 가지고 있다.

 

3.1 구조

ArrayList는 Array를 기반으로하는 인덱스 기반의 데이터 구조. 임의의 요소 엑세스시 O(1)와 동일한 성능을 제공

LinkedList는 각 요소를 list로 저장하며 각 노드는 이전, 이후 요소와 연결되어 있다. 검색 작업 실행시간은 O(n)이다.

 

3.2 연산자

삽입, 수정, 삭제시 LinkedList가 빠르다. 

Collection에서 임의의(arbitary) 위치에 요소가 추가되었을 때 배열의 크기를 조정하거나 인덱스를 변경할 필요가 없고 주변 요소의 참조값만 변경하면 된다.

 

3.3 메모리 사용량

LinkedList에 있는 모든 노드가 이전, 이후 2개의 참조를 가지고 있기 때문에 LinkedList가 ArrayList보다 더 많은 메모리를 사용한다. ArrayList는 오직 데이터와 인덱스 값만을 가지고 있다.

 

4. 사용법

 

4.1. 생성

LinedList<Object> linkedlist = new LinkedList<>();

 

4.2. 추가

LinkedList는 List와 Deque 인터페이스의 구현채로 add(), addAll() 메서드를 사용한다.

addFirst()와 addLast()는 처음이나 끝에 요소를 추가할 수 있다.

 

4.3 삭제

추가와 비슷하게 removeFirst()나 removeLast()를 상속받는다.

또한 removeFirstOccurence(), removeLastOccurence()를 사용해 collection이 특정 요소를 포함하면 true를 반환하는 메서드를 사용 boolean값을 반환할 수 있다.

 

4.4 Queue 연산자

Deque 인터페이스는 queue 같은 동작을 제공한다.

linkedList.poll();
linkedList.pop();

해당 메서드들은 list에서 첫번째 요소를 검색(retrieve)하고 삭제한다.

poll()과 pop()의 차이는 pop은 empty list라면 NosuchElementException()을 반환하지만 poll은 null을 반환한다.

pollFirst()와 pollLast()도 가능하다.

linkedList.push(Object o);

push API는 collection의 head에 요소를 삽입한다.