LinkedList

자바 컬렉션 프레임워크에서 제공하는 양방향 연결 리스트 구현체이다.

내부적으로는 각 노드가 앞 뒤 노드를 가리키는 prev/next 링크를 가지고 있다.

삽입/삭제를 어느 리스트의 위치에서나 O(1) 에 처리할 수 있다.

→ 즉, 중간 인덱스에 삽입 삭제가 빈번하게 일어나는 상황에서 사용하면 좋다.

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    ...
}

LinkedList 는, List 인터페이스 , Deque 인터페이스 , Queue 인터페이스를 모두 구현하고 있다.

(보이지는 않지만, Deque 인터페이스가 Queue 인터페이스를 확장하고 있다.)

메소드

List 인터페이스 메소드

• get(i) : O(N) 의 성능을 가진다. i 번째 인덱스에 대한 원소를 가져온다.
• add(E) : 맨 뒤에 원소를 하나 추가한다.
• add(i, E): O(N) + O(1) 의 성능을 가진다. i 번째 인덱스에 원소를 삽입한다.
• remove(i) : O(N) + O(1) 의 성능을 가진다. i 번재 인덱스의 원소를 삭제한다.
• removeFirst() / Last() : O(1) , 맨 처음 및 마지막 원소를 삭제한다.
• set(i, e) : i 번째 인덱스의 원소를 e로 바꾼다.
• boolean(e) : e와 처음으로 일치하는 원소를 삭제한다.

Deque 인터페이스 메소드

Deque (덱) 자료형은 앞 뒤에서 모두 데이터 삽입/삭제가 가능한 자료형이다.

• 앞
  • void addFirst(E e)
  • boolean offerFirst(E e)
  • E removeFirst(), E pollFirst()
• 뒤
  • void addLast(E e)
  • boolean offerLast(E e)
  • E getLast()
  • E peekLast()
  • E removeLast()
  • E pollLast()

Queue 인터페이스 메소드

• boolean offer(E e) = offerLast(e)
• E poll() = pollFirst()
• E peek() = peekFirst()