8장. 연결 리스트

연결리스트는 데이터 요소의 선형 집합으로, 데이터의 순서가 메모리에 물리적인 순서대로 저장되지는 않는다. 동적으로 새로운 노드를 삽입하거나 삭제하기 간편하며, 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리도 쉽다.

• 연결리스트는 배열과는 달리 특정 인덱스에 접근할 때 전체를 읽어야 하므로 상수시간으로 접근 불가하다.
• 탐색 = O(n)

• 반면, 시작 또는 끝 지점에 아이템을 추가하거나 삭제, 추출하는 작업은 상수시간에 가능하다.
• 끝 지점에 삽입, 삭제, 추출 = O(1)

문제 리스트