연결리스트 Reverse

연결리스트의 역순 연산 코드는 다음과 같다.

Node *reverse(List *head)
{
  Node *p, *q, *r;
  p = head; // p는 역순으로 만들 리스트
  q = NULL; // q는 역순으로 만들 노드
  while (p != NULL)
  {
    r = q;
    q = p;
    p = p->link;
    q->link = r;
  }
  return q; //5번이 끝난 후
}

4까지 data가 있는 노드를 reverse해보자.

연결리스트에서 = 연산자는 대입하는 게 아니라, 가리킨다고 생각했다.

1번째 실행

처음에 r = q 이므로,
(1) q가 가리키는 걸 r이 가리키고
(2) p가 가리키는 걸 q가 가리키고
(3) p->link가 가리키는 것을 p가 가리키고
(4) r이 가리키는 것을 q->link가 가리킨다.
결과는 아래와 같다.

---

2번째 실행

처음에 r = q 이므로,
(1) q가 가리키는 걸 r이 가리키고
(2) p가 가리키는 걸 q가 가리키고
(3) p->link가 가리키는 것을 p가 가리키고
(4) r이 가리키는 것을 q->link가 가리킨다.
결과는 아래와 같다.

---

3번째 실행

처음에 r = q 이므로,
(1) q가 가리키는 걸 r이 가리키고
(2) p가 가리키는 걸 q가 가리키고
(3) p->link가 가리키는 것을 p가 가리키고
(4) r이 가리키는 것을 q->link가 가리킨다.
결과는 아래와 같다.

---

4번째 실행

처음에 r = q 이므로,
(1) q가 가리키는 걸 r이 가리키고
(2) p가 가리키는 걸 q가 가리키고
(3) p->link가 가리키는 것을 p가 가리키고
(4) r이 가리키는 것을 q->link가 가리킨다.
결과는 아래와 같다.

p = NULL 이 되므로 whlie이 종료되고
q가 헤더인 연결리스트가 만들어진다

---

LinkedList Reverse가 이해가 되지 않아서 정리해봤다.