Linkedlist
자료구조중 하나로 값 또는 자료를 가지고 있는 데이터와 주소를 가지고 있어 이전 노드 또는 다음 노드와의 연결을 담당하는 포인터를 가진 노드들의 연결체
노드들을 추가하거나 삭제하여 노드들의 주소가 변경되어도 링크만 변화되어 Arraylist와는 다르게 데이터들의 추가나 삭제에는 유리, 탐색에는 순차탐색이 사용되기 때문에 불리
- 데이터의 잦은 변경(추가 및 삭제) : Linkedlist
- 저장된 데이터를 탐색하거나 정렬 : Arraylist
한 방향으로 연결된 구조Single LinkedList : 시작(가장 앞) 노드를 Header라고 함
양 방향으로 연결된 구조Double LinkedList : 시작(가장 앞) 노드를 Header이라 하고 끝(가장 뒤) 노드를 Tail이라고 함
관련 메서드
add(index, element) index에 element를 삽입
addFirst(element) 가장 앞 노드에 element를 삽입
addLast(element) 가장 끝 노드에 element를 삽입
clone() 복사본을 반환
contains(Object) Object가 존재하면 true(단, 없다면 false)
get(index) 해당 index 데이서 반환
indexOf(Object) Object가 처음 나타난 인덱스 반환(단, 없으면 -1)
clear() 모든 데이터 제거
remove() 첫 데이터를 제거
remove(index) 해당 index 데이터 제거
그 외 메서드 참고 : https://www.geeksforgeeks.org/linked-list-in-java/
시간복잡도
탐색 및 추가,제거 O(n)
모든 요소를 다 훑어야 탐색이 가능하며 또한 이러한 탐색 이후에 추가 및 제거가 가능함
