초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
배열은 값이 이어진 주소에 붙어 있어야 해서, 맨 앞에 끼워 넣으면 값을 모두 밀어야 했습니다. 값을 밀지 않고 끼워 넣을 수 있는 자료구조는 없을까요?
배열이 값을 미는 까닭은 순서를 주소로 정하기 때문입니다. 인덱스 3의 값은 반드시 시작 주소 + 3에 있어야 하니, 앞에 하나 끼우면 뒤의 값이 모두 자리를 옮깁니다.
순서를 주소 대신 값 옆에 적어 두면 어떨까요? 값마다 다음 값의 주소를 적어 두면, 쪽지마다 다음 쪽지 위치가 적힌 보물찾기처럼 값이 메모리 아무 데나 흩어져 있어도 순서대로 따라갈 수 있습니다. 끼워 넣을 때도 값은 그대로 두고 적어 둔 주소만 고치면 됩니다.
값 하나와 다음 값의 주소를 한 묶음으로 노드(node)라 합니다. 이 주소처럼 다른 데이터가 있는 주소를 담은 값을 포인터(pointer)라 하고, 노드를 포인터로 줄줄이 이은 것을 연결 리스트(linked list)라 합니다. 첫 노드의 주소는 따로 기억해 두고, 마지막 노드의 포인터에는 끝이라는 표시를 둡니다.
처음 노드의 주소는 14번입니다.
위 숫자는 주소입니다. 노드마다 이웃한 두 칸에 값과 포인터(→ 다음 노드의 주소)가 있습니다.
새 노드는 빈 주소 아무 데나 만들면 됩니다. 앞 노드의 포인터가 새 노드를, 새
노드의 포인터가 원래 뒤 노드를 가리키게 고치면 끝입니다. 다른 노드는 옮기지 않고
포인터 두 개만 바꿉니다. 맨 앞에 넣을 때는 새 노드가 첫 노드가 됩니다. C로 써
봅시다. struct로 값과 포인터를 한 노드로 묶고, malloc으로 빈 주소에 새
노드를 만듭니다.
출력 없음대신 노드의 주소를 계산으로 알 수 없으니, 인덱스 3의 값을 보려면 처음 노드부터 포인터를 세 번 따라가야 합니다.
읽기(위치 4), 넣기(위치 0), 넣기(맨 끝 다음)를 차례로 실행해 봅시다.
연결 리스트도 넣을 자리의 앞 노드까지 찾아가는 데에는 시간이 걸립니다.
파이썬의 collections.deque는 내부적으로 연결 리스트로 구현되어 있습니다(노드
하나에 값을 여러 개 담습니다). 배열 글과 같은 코드를 deque로 돌려
봅시다.
실행을 눌러 봅시다.
실행을 눌러 봅시다.
배열과 반대로 하나씩 다 읽기는 오래 걸리고, 맨 앞에 넣기는 금방 끝납니다.
d[i]를 읽을 때마다 노드를 따라가야 하기 때문입니다.
시간 복잡도로 쓰면 배열은 읽기가 O(1), 맨 앞에 넣기가
O(n)이고 연결 리스트는 그 반대입니다. 그래서 맨 앞에서 넣고 빼는 일이 잦으면
연결 리스트가, 아무 위치나 자주 읽으면 배열이 유리합니다. 배열은 값이 붙어 있어
공간적 지역성 덕도 봅니다.
노드 1000개짜리 연결 리스트가 있습니다. 노드마다 다음 노드의 주소만 적혀 있고, 첫 노드와 마지막 노드의 주소는 따로 기억해 둡니다. 그래서 맨 끝에 값을 하나 넣을 때는 포인터를 한 번도 따라가지 않습니다. 맨 끝 노드 하나를 빼고 기억해 둔 마지막 노드 주소도 고치려면, 포인터를 적어도 몇 번 따라가야 할까요? 첫 노드에서 한 번 따라가면 인덱스 1 노드에 닿습니다. 숫자로 답하세요.