학습 일자 : 2023.04.19
데이터를 포함하는 노드들을 연결식으로 만든 자료구조
노드는 데이터와 이전/다음 노드 객체를 참조하고 있음
노드가 메모리에 연속적으로 배치되지 않고, 이전/다음노드의 위치를 확인
→ 노드의 개수보다 노드의 위치가 더 중요함
[연결리스트 노드]
접근 : O(n)
→ 배열은 연속적인 데이터를 가지고 있어, 원하는 곳을 계산해서 한번에 갈 수 있지만, 연결리스트는 주소로 이어져 있는 구조이기 때문에 특정 노드에 가기 위해서는 시작시점부터 노드를 따라가 봐야 알 수 있음 → 최소 1회의 순회가 필요함.
탐색 : O(n) → 노드를 순회하며 조건에 맞는 데이터를 찾아야 함.
삽입 : O(1)
삭제 : O(1)
→ 삽입과 삭제는 앞뒤의 주소 연결만 바꿔주면 되기 때문에 한번에 해결이 가능함. (삽입과 삭제에 매우 유용한 구조임)