2.2.4 연결 리스트

연결 리스트(linked list)는 요소가 메모리 안에서 연속적이지 않고 각 요소가 다음 항목의 주소를 가리키는 리스트를 말한다. 삽입이나 삭제 작업에 O(1) 복잡도를 가지므로 유용하다. 개별 항목은 메모리 내 어디에나 저장되기 때문에 인덱스별로 액세스할 수 없으며, 계산할 수도 없다. 하지만 리스트의 처음이나 끝에 주로 액세스하거나 항목을 열거하기 위한 목적이라면 그만큼 빠르게 액세스할 수도 있다. 그렇지 않으면 연결 리스트에 항목을 확인하는 작업은 배열이나 리스트와 같이 O(N) 복잡도를 갖는다. 그림 2-5는 연결 리스트의 레이아웃 예이다.

▲ 그림 2-5 연결 리스트의 레이아웃

그렇다고 해서 연결 리스트가 항상 일반 리스트보다 빠르다는 뜻은 아니다. 전체 메모리 블록을 한 번에 할당하고 추가적인 참조 검색을 수행하는 대신 각 요소를 위해 개별적으로 메모리를 할당한다면 성능이 저하될 수 있다.

큐나 스택 구조가 필요할 때마다 연결 리스트가 필요할 수 있다. 하지만 .NET은 이를 모두 지원한다. 따라서 시스템 프로그래밍에 관심이 없는 한, 면접 이외의 일상 업무에서는 연결 리스트를 사용할 필요가 없다. 이상적으로는 그렇겠지만, 불행하게도 면접관들은 연결 리스트를 이용한 골치 아픈 질문을 좋아하기 때문에 여전히 이에 익숙해지는 것이 중요하다.