[Java] LinkedList

• 새로운 객체를 삽입하거나 삭제하기 간편
• 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리가 간편
• ArrayList는 중간 인덱스의 객체를 제어하면 뒤의 객체의 인덱스가 1씩 앞으로 당겨지기때문에 빈번한 객체 삭제와 삽입이 일어나는 곳에서는 ArrayList보다 링크만 변경하면되는 LinkedList가 좋은 성능을 발휘
• ArrayList는 내부 배열에 객체를 저장하여 인덱스로 관리하지만 LinkedList는 인접 참조를 링크하여 체인처럼 관리

수정 과정

• 탐색, 삽입, 삭제: O(n)
• 시작과 끝의 삽입, 삭제: O(1)

ArrayList vs LinkedList

구분	순차적으로 추가/삭제	중간에 추가/삭제	검색
ArrayList	빠름	느림	빠름
LinkedList	느림	빠름	느림

메소드 정리

값 추가

메소드	설명
boolean add(Object)	맨 뒤에 연결되며 값 추가
boolean offer(Object)	내부에서 add() 호출
void addLast(Object)	맨 뒤에 연결되며 값 추가
boolean offerLast(Object)	내부에서 addLast() 호출
void addFirst(Object)	맨 앞에 값 추가
void push(Obejct)	내부에서 addFirst() 호출
boolean offerFirst(Object)	내부에서 addFirst() 호출
void add(index, Object)	인덱스를 지정하여 값 추가
boolean addAll(Collection)	Collection 추가
boolean addAll(index, Collection)	인덱스를 지정하여 Collection 추가

값 반환

메소드	설명
Object getFirst()	맨 앞에 있는 값 반환 (없으면 예외 발생)
Object peek()	맨 앞에 있는 값 반환 (없으면 null 반환)
Object peekFirst()	peek()과 동일한 코드
Object element()	내부에서 getFirst() 호출
Object getLast()	맨 뒤에 있는 값 반환 (없으면 예외 발생)
Object peekLast()	맨 뒤에 있는 값 반환 (없으면 null 반환)
Object get(index)	인덱스에 위치한 값 반환

값 삭제

메소드	설명
Object poll()	맨 앞에 있는 값 삭제 후 반환 (없으면 null 반환)
Object pollFirst()	poll()과 동일한 코드
Object removeFirst()	맨 앞에 있는 값 삭제 후 반환
Object remove()	내부에서 removeFirst() 호출
Object pop()	내부에서 removeFirst() 호출
boolean removeFirstOccurrence(Object)	앞에서 뒤로 탐색하며 가장 먼저 찾은 객체를 삭제
Object pollLast()	맨 뒤에 있는 값 삭제 후 반환 (없으면 null 반환)
Object removeLast()	맨 뒤에 있는 값 삭제 후 반환
boolean removeLastOccurrence(Object)	뒤에서 앞으로 탐색하며 가장 먼저 찾은 객체를 삭제
boolean remove(Object)	값을 지정하여 삭제
Object remove(index)	인덱스 위치에 있는 값을 삭제 후 반환

기타 메소드

메소드	설명
boolean contains(Object)	값의 존재 여부 반환
int size()	길이 반환
Object set(index, Object)	인덱스에 위치한 값을 대체하고 이전 값을 반환
int indexOf(Object)	값의 첫 번째 인덱스 반환 (없으면 -1 반환)

항상 비어있지 않다면 예외를 발생하는 메소드(get, remove), 비어있을 가능성이 있고 예외 처리를 피하고자 하는 경우 null 값을 반환하는 메소드(peek, poll)를 상황에 따라 선택