LinkedList
LinkedList 컬렉션 클래스는 데이터를 효율적으로 추가, 삭제, 변경 등의 동작을 하기 위해 사용한다.
LinkedList는 ArrayList와는 다르게 불연속적으로 존재하며, 데이터들은 서로 연결되어 있다.
하나의 데이터와 다음 데이터의 주소를 담고있는 노드(Node)로 구성된다.
-
데이터가 연속된 위치에 저장되지 않고 모든 데이터가 데이터 부분과 주소 부분을 별도로 가지고 있다.
-
각 데이터는 노드라 불리며 배열에서 자주 삽입,삭제가 이루어지는 경우 용이하다.
-
ArrayList보다 검색에 있어서 느리다.
-
LinkedList list = new LinkedList();으로 선언 후 사용한다.
LinkedList 기본함수
-
add
list.add("Hello")로 값 추가
list.add(1, "World")로 특정 인덱스 값 변경 => Index를 알아야 변경 가능 -
size
list.size()로 저장된 객체 수 얻기 -
get
list.get(0)으로 0번 인덱스의 객체 출력 -
remove
list.remove(0)로 0번 인덱스에 저장된 객체 삭제
list.removeFirst(), list.removeLast()로 첫번째와 마지막 데이터 삭제
-
contains(Object)
list.contains("Hello")로 값이 있는지 확인 후 true나 false 출력
-
indexOf(Object)
list.indexOf("Hello")로 값의 Index를 찾아줌 값이 없으면 -1 리턴
LinkedList 시간복잡도
탐색 : O(n)
삽입 : O(n), O(1)
삭제 : O(n), O(1)
삽입과 삭제는 맨앞, 맨뒤일 경우 O(1), 탐색을 통해 중간에 삽입,삭제할 경우 O(n)
