[DataStructure] Linked List (Java)

Linked List

참고링크

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable

설명

LinkedList는 데이터 필드를 보유하는 노드와 다른 노드에 대한 참조로 구성된 선형 데이터 구조입니다.
synchronized가 되어있지 않아서 외부에서 동시성 처리를 해줘야합니다.
(동시성 처리를 위해 아래와 같이 사용하는게 최선의 방법입니다.)

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

사용법

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
List list = Collections.synchronizedList(new LinkedList());
list.add("test1");
list.add("test2");
list.add("test3");
list.remove(0);

LinkedList linkedList = new LinkedList();
linkedList.push("hello");
linkedList.pop();
linkedList.addFirst("hi1");
linkedList.addFirst("hi2");
linkedList.addFirst("hi3");
linkedList.remove();

System.out.println(list.get(0));
//결과 test2
System.out.println(linkedList.get(0));
//결과 hi2

시간복잡도

add() – list 끝 노드에 데이터를 추가하는거여서 tail에 넣어주면 됌 그래서 O(1)
add(index, element) – 평균적으로 O(n)
get() – 해당 노드를 순차적으로 찾아가야해서 O(n)
remove(element) – 맨 위에 노드를 제거하는거라서, 최상위 노드만 수정해주면 되기 때문에 O(1).
remove(index) – 해당 노드를 순차적으로 찾아가기 때문에 O(n)
contains() – 해당 노드를 순차적으로 찾아야해서 O(n)
참고링크

공간복잡도

대부분의 Collection들은 O(n)
참고링크
참고링크