[알고리즘] LinkedList

특징: 시작 노드만 알면 연결된 모든 노드를 알 수 있다.

Doubly-linked list

 

size(): O(1)

isEmpty(): O(1)

get(): O(n)

getFirst(): O(1)

getLast(): O(1)

set(): O(n)

iterator(): O(1)

listIterator(): O(1)

add(E e): O(1) (amortized time)

add(int index, E e): O( index 오른쪽 배열 크기) (amortized time)

remove(): O(n)

removeFirst(): O(1)

removeLast(): O(1)

peek(): O(1)

element(): O(1)

peekFirst(): O(1)
peekLast(): O(1)

pollFirst(): O(1)

pollLast(): O(1)

pop(): O(1)
push(): O(1)

indexOf(): O(n)

contains(): O(n)

addAll(E e): O(m) (넣는 배열 크기)

addAll(int index, E e): O(n + m)

sort(): O(nlogn)

clear(): O(n)

 

ArrayList와 비교했을때

장점

- 앞에서의 add, remove가 빠르다.

- remove가 빠르다.(중간 지점으로 가는건 ArrayList와 똑같지만 빼는 건 O(1) ArrayList는 O(m) 밀어주어야하기 때문에)

단점

- get, set이 느리다.

- 전반적으로 ArrayList보다 느리다.