Linked List 구현 시, dummy 노드의 용도

자료구조 책에는 항상 리스트가 나오고, 서적마다 리스트를 구현하는 방법이 조금씩 다르다. 

여기서 다르다는 표현은 dummy 노드를 쓰느냐 마느냐 이다.
어떤 서적은 dummy 노드를 쓰지만, 어떤 서적은 안쓰기도 하며, 또 어떤 서적은 둘 다를 다루기도 한다.

그럼 이 차이가 무엇인지 알아보자. 그림 수준에서 설명하면 아래와 같다.
위의 그림은 dummy 노드를 사용하지 않았으며 head가 바로 첫 번쨰 노드 A를 가리키고 있다.

아래의 그림은 dummy 노드를 사용한 경우로, head는 dummy 노드를 가리키고 있다.

핵심은 head가 가리키는 첫 번째 노드가 dummy 노드인지 아닌지이다.
이에 따른 리스트 추가 하는 코드의 차이를 비교해보자. (이해를 쉽게 하기 위해 tail 코드는 제외한다.)

우선 dummy 노드를 사용하지 않는 경우의 코드를 보자.
새로운 노드를 추가 할 때, 첫 번째 노드인지 판단이 필요하다.

Node * head;
Node * tail;

Node * newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;

if(head == NULL) // 첫 번째 노드를 삽입 할 때의 처리가 필요하다.
 head = newNode;
else 
 tail->next = newNode;

tail = newNode;

두 번째로 dummy 노드를 사용하는 경우의 코드를 보자.
첫 번째 노드인 dummy가 추가되므로, 추가적인 판단 없이 노드를 추가한다.

Node * head;
Node * tail;

head = (Node*)malloc(sizeof(Node));
tail = head;

Node * newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;

tail->next = newNode; // 첫 번째 노드인지 판단할 필요 없이 바로 추가.
tail = newNode;

둘 중 어떤 방법이 더 좋을까? 라는 질문의 답은 낼 수 없지만,
데이터 추가 작업이 많은 링크드 리스트라면 dummy 노드를 사용하는게 좀 더 효율이 좋아보인다.