몽땅뚝딱 개발자

연결 리스트(linked list) 1.1. 연결 리스트가 유용한 순간 연결 리스트는 배열과 상당히 유사하지만 자료 구조의 성능에 큰 차이가 있다. 가령 세 번째 node에 있는 값을 읽거나 검색하기 위해서는 첫 번째부터 접근하여 순차적으로 진행해야 하므로 O(N)이다. 따라서 읽기와 검색에서는 유의미한 차이가 없지만 연결 리스트는 삽입에서 빛을 발휘한다. 배열에서 최악의 시나리오는 인덱스 0에 데이터를 삽입하거나 삭제할 때이다. 나머지 데이터를 한 셀씩 오른쪽으로 옮겨야 하기 때문에 효율성은 O(N)이 된다. 반면 연결 리스트는 딱 한 단계인 O(1)만 걸린다. 삽입하는 경우 배열처럼 한 셀씩 옮기는 것이 아니라 기존 리스트 앞에 새 노드를 생성하고 노드가 이전의 첫 번째 노드를 가리키도록 만들면 된다..