[JAVA] LinkedList

#JAVA #컬렉션 #List

[!NOTE] 주요 특징
배열의 단점( [[ArrayList]] )을 극복하고 다양한 상황에서 유연한 자료 구조로 활용된다.

Node(노드) 개념의 도입
노드는 현 데이터 내부에 다음 데이터의 참조값을 포함해서 가지고 있다.
-> 마치 데이터가 연결돼 있는 듯한 효과

링크드 리스트에 A -> B -> C 순서로 저장한 경우의 개념도

LinkedList의 장단점

장점

• 동적 메모리 할당 : 필요할 때마다 노드를 추가하기 때문에 메모리 효율 증가
• 첫 번째 인덱스의 추가/삭제 시 O(1) 의 성능

단점

• 순차 검색 성능 O(n) : 링크를 타고 순차적으로 접근해서 검색하는 방식이리 때문
• 메모리 사용량 증가 : 각 노드가 다음 노드를 가리키는 참조를 추가적으로 저장하기 때문

LinkedList의 시간 복잡도

• 추가, 삭제
  • 마지막 위치 : O(n)
  • 처음 위치 : O(1)
• 특정 인덱스 조회 : O(n)
• 검색 : O(n)

---

출처 : 인프런 '김영한의 실전 자바 - 중급 2편'