주요 특징
배열의 단점( ArrayList )을 극복하고 다양한 상황에서 유연한 자료 구조로 활용된다.
Node(노드) 개념의 도입 노드는 현 데이터 내부에 다음 데이터의 참조값을 포함해서 가지고 있다. → 마치 데이터가 연결돼 있는 듯한 효과
링크드 리스트에 A → B → C 순서로 저장한 경우의 개념도
LinkedList의 장단점
장점
- 동적 메모리 할당 : 필요할 때마다 노드를 추가하기 때문에 메모리 효율 증가
- 첫 번째 인덱스의 추가/삭제 시 O(1) 의 성능
단점
- 순차 검색 성능 O(n) : 링크를 타고 순차적으로 접근해서 검색하는 방식이리 때문
- 메모리 사용량 증가 : 각 노드가 다음 노드를 가리키는 참조를 추가적으로 저장하기 때문
LinkedList의 시간 복잡도
- 추가, 삭제
- 마지막 위치 : O(n)
- 처음 위치 : O(1)
- 특정 인덱스 조회 : O(n)
- 검색 : O(n)