부산대학교자료구조
Scientific Inference Lab

Links Both Ways

Doubly Linked Lists

prev 참조와 센티널로 양방향 연결을 추적한다.

문제 1

prev 참조가 바꾸는 것

단일 연결리스트(SLList)와 이중 연결리스트(DLList)에 원소가 각각 n개 있다.

  1. SLList에서 마지막 노드를 삭제하는 비용과 그 원인을 적는다.
  2. DLList의 노드 하나가 저장하는 세 필드와 각각 가리키는 것을 적는다.
  3. 원소가 1,000개일 때 DLList가 SLList보다 더 저장하는 참조의 수를 적는다.
  4. SLList에서 현재 노드의 참조만으로 바로 앞 노드에 갈 수 없는 이유를 적는다.
해설 펼치기
  1. Θ(n)이다. 앞 노드를 찾으려 처음부터 따라가야 한다.
  2. u.data는 값, u.next는 뒤따르는 노드, u.prev는 앞서는 노드를 가리킨다.
  3. 노드마다 prev 참조 하나를 더 저장하므로 1,000개다.
  4. 현재 노드에는 앞 노드의 참조가 없어 바로 이동할 수 없다. head부터 다시 따라가면 찾을 수 있지만 Θ(n)이 든다.
문제 2

센티널로 닫힌 고리

  1. 빈 DLList에서 dummy.next, dummy.prev, n을 적는다.
  2. 빈 목록에 원소 a 하나를 넣은 뒤 dummy.next, dummy.prev, a.prev, a.next가 가리키는 노드를 적는다.
  3. a, b, c를 담은 목록에서 c.next와 a.prev가 가리키는 노드를 적는다.
  4. 센티널이 없을 때 따로 처리해야 했던 경우 세 가지와, 센티널이 있을 때 그 경우들이 어떻게 처리되는지 적는다.
해설 펼치기
  1. dummy.next와 dummy.prev는 모두 dummy 자신이고 n은 0이다.
  2. dummy.next와 dummy.prev는 a, a.prev와 a.next는 dummy다.
  3. 둘 다 dummy다. 센티널이 마지막 노드의 뒤이면서 첫 노드의 앞이라 고리가 닫힌다.
  4. 첫 노드 앞에 삽입(head 갱신), 마지막 노드 삭제(tail 갱신), 빈 목록에 삽입(둘 다 갱신)이다. 센티널이 있으면 모두 일반 삽입·삭제와 같은 규칙으로 처리한다.

오개념 점검: dummy는 값을 담는 원소가 아니므로 원소 수 n에 세지 않는다.

문제 3

가까운 끝에서 찾기

원소가 n = 10개인 DLList에서 get_node(i)는 i < n/2이면 dummy.next에서 next로 i걸음, 아니면 dummy에서 prev로 n − i걸음 이동한다.

  1. i = 3, 5, 7일 때 출발점, 이동 방향, 걸음 수를 적는다.
  2. n = 10에서 이동하는 걸음 수의 최댓값을 적는다.
  3. 같은 목록을 SLList로 저장했다면 i = 7에 가는 걸음 수를 적는다.
  4. i번째 노드를 찾는 비용을 식으로 적는다.
해설 펼치기
  1. i = 3: dummy.next에서 next로 3걸음. i = 5: 5 < 5가 거짓이라 dummy에서 prev로 10 − 5 = 5걸음. i = 7: dummy에서 prev로 10 − 7 = 3걸음.
  2. ⌊n/2⌋ = 5걸음이다.
  3. 앞에서만 갈 수 있어 7걸음이다.
  4. Θ(1 + min{i, n − i})다.
문제 4

참조 네 개의 순서

목록 a, b, c, d에서 노드 w = c 앞에 새 노드 u(값 x)를 넣는다.

  1. 네 줄을 올바른 순서로 적고, 각 줄이 끝난 뒤 바뀐 참조를 적는다.
  2. w.prev = u를 가장 먼저 실행하면 어떤 문제가 생기는지 적는다.
  3. 첫 자리(w = a)에 넣을 때와 빈 목록에 넣을 때 w.prev가 각각 무엇인지 적는다.
해설 펼치기
  1. u.prev = w.prev(u의 앞이 b), u.next = w(u의 뒤가 c), u.next.prev = u(c의 앞이 u), u.prev.next = u(b의 뒤가 u)다. 결과는 a, b, x, c, d다.
  2. w.prev를 먼저 u로 바꾸면 새 노드에서 기존 앞 노드 b를 바로 읽을 수 없다. head부터 다시 찾을 수는 있지만, 네 참조만 바꾸는 삽입 절차에서는 u 쪽 참조를 먼저 채워 b와 w를 보존해야 한다.
  3. 첫 자리에서는 dummy, 빈 목록에서는 w가 dummy이고 w.prev도 dummy 자신이다. 센티널 덕분에 같은 네 줄로 처리한다.
문제 5

삭제와 비용

목록 a, b, c, d, e(n = 5)가 있다. 1과 2는 각각 이 목록에서 따로 시작한다.

  1. remove_node(w)로 w = d를 삭제할 때 바뀌는 참조 두 개와 반환값, 삭제 뒤 n을 적는다.
  2. 마지막 원소 e를 삭제할 때 따로 처리할 경우가 없는 이유를 적는다. 원소 하나만 남은 목록에서 그 원소도 지운 뒤 dummy.next와 dummy.prev가 각각 어디를 가리키는지 적는다.
  3. 원소가 8개일 때 인덱스 2의 노드를 인덱스로 찾아 삭제하는 비용과, 그 노드의 참조를 이미 가진 경우의 비용을 비교한다.
  4. DLList에서 비용이 큰 부분이 어디인지 한 문장으로 적는다.
해설 펼치기
  1. c.next = e, e.prev = c로 바뀌고 d를 반환하며 n은 4다.
  2. e의 next가 dummy라 w.next.prev = w.prev가 dummy.prev = d로 그대로 동작한다. 원소 하나만 남았을 때 그 원소를 지우면 dummy.next와 dummy.prev가 모두 다시 dummy 자신을 가리킨다.
  3. 인덱스로 찾으면 min{2, 6} = 2걸음을 걸은 뒤 참조 두 개를 바꾸므로 Θ(1 + min{i, n − i})이고, 참조를 이미 가지면 Θ(1)이다.
  4. 노드를 찾는 순회가 비용을 정하고, 찾은 뒤의 삽입·삭제는 Θ(1)이다.