구조를 그릴 줄 아는지보다, 탐색·삽입·삭제 각각이 어떤 단계로 일어나는지 머릿속에 그리고 상황에 맞춰 비용을 가를 수 있는지를 본다.
연결 리스트는 각 노드가 데이터와 다음 노드 포인터를 들고 줄지어 있는 선형 구조다. 중간에 노드를 끼우거나 빼는 일은 앞뒤 포인터만 바꾸면 되므로 "노드 위치를 이미 알고 있다"는 전제에선 O(1)에 가깝지만, 인덱스로 N번째를 찾으려면 머리부터 한 칸씩 따라가야 해서 O(n)이다. 배열과 달리 메모리를 연속으로 잡지 않아 캐시 라인 안에 다음 노드가 거의 들어오지 않고, 그래서 순회 성능은 배열보다 눈에 띄게 떨어진다. "삽입/삭제 비용"이 진짜 병목이고 포인터 조작이 핵심일 때만 배열보다 유리하다.
LinkedList로 짠 컬렉션을 ArrayList로 바꿔 성능이 개선됐던 경험이 있다면 캐시 지역성 이야기로 풀 수 있다
LRU 캐시나 큐를 직접 구현해 본 적이 있다면 노드 포인터 조작이 왜 필요했는지 자연스럽게 이어 갈 수 있다
포인터/참조 실수로 사이클이나 메모리 누수를 겪은 경험이 있다면 자료구조 선택의 위험 비용으로 묶을 수 있다
아직 공개된 답변이 없어요. 첫 공개 답변을 남겨보세요.