LinkedList

이 글은 Baeldung 사이트 'A Guide to the Java LinkedList'를 해석, 정리한 글입니다.

 

LinkedList

LinkedList

LinkedList는 Java Collections Framework 중에 하나이다.

List와 Deque Interface를 상속받아 구현된 Class이다.

LinkedList 특징

• Indexing을 할 때 시작이나 끝 중 가까운 곳에서 실행
• 비동기(not synchronized)
• Iterator, ListIterator 모두 fail-fast
• 모든 Element가 이전, 다음 Element를 참조
• 삽입된 순서를 유지

LinkedList가 Collections.synchronizedList Method를 사용하면 synchronized 하게 할 수 있다.

List list = Collections.synchronizedList(new LinkedList(...));

LinkedList vs ArrayList

구조

ArrayList는 Array 구조 기반이라 Random Access로 검색(O(1))

LinkedList는 모든 Element가 이전, 다음 Element로 연결되어 있어 Sequential Access로 검색(O(n))

동작

삽입, 제거할 때 ArrayList보다 LinkedList가 빠르다

LinkedList는 Array 크기를 조정하거나 Index를 변경할 필요 없이 주변 Element 참조만 변경하면 된다.

Memory

ArrayList보다 LinkedList가 Memory를 많이 차지한다.

LinkedList는 모든 Element가 주변 Element 참조값을 저장한다.

ArrayList는 오직 data, index만 저장한다.

	ArrayList	LinkedList
Indexing	O(1)	O(n)
맨 처음 Element 추가/삭제	O(n)	O(1)
맨 마지막 Element 추가/삭제	O(1)	O(n) - last Element is unknown O(1) - last Element is known
맨 중간 Element 추가/삭제	O(n)	search time + O(1)

LinkedList Element 추가, 제거

LinkedList는 List와 Deque를 구현한 Class이다.

추가할 때는 add, addAll, addFirst, addList Method를 사용할 수 있다.

제거할 때는 removeFirst, removeLast, removeFirstOccurence, removeLastOccurence Method를 사용할 수 있다.

LinkedList<Integer> list = new LinkedList<Integer>();
list.addFirst(1); // 가장 앞에 데이터 추가
list.addLast(2); // 가장 뒤에 데이터 추가
list.add(3); // 데이터 추가
list.add(1, 10); // index 1에 데이터 10 추가

list.removeFirst(1); // 가장 앞 데이터 제거
list.removeLast(); // 가장 뒤 데이터 제거
list.removeFirstOccurence(2); // 해당 데이터 첫번째에 있어 제거하면 true, 없으면 false 리턴
list.removeLastOccurence(3); // 해당 데이터 마지막에 있어 제거하면 true, 없으면 false 리턴
list.remove(); // 0번째 데이터 제거
list.remove(1); // index 1에 있는 데이터 제거
list.clear(); // 모든 데이터 제거

Queue 동작

LinkedList는 Deque를 구현한 Class이기 때문에 Queue의 Method를 사용할 수 있다.

linkedList.poll();
linkedList.pop();
linkedList.push(Object o);

[참고사이트]

자료구조: Linked List 대 ArrayList