STL (Standard Template Library)이라는 것을 알고나서부터는 연결 리스트를 따로 구현해서 쓰는 일은 거의 없어졌다.
하지만 대학에서 처음 포인터를 접하고(실제로는 중학교 때 처음 접했던 것 같다.) 자료구조를 구현할 때를 생각하면 아직도 머리가 지끈지끈 해 오는 것 같다.
예전 기억을 떠올리며 아주 간단히 단방향 연결 리스트를 구현하는 방법을 소개하고자 한다.
고수들은 이 글을 추억의 한 페이지로 여기고 잠시 사색에 잠기는 것도 즐거운 시간일 것이다.

참고로 총 3개의 파일로 나눠서 구현한다.
CY_List.cpp : 리스트를 구현한 파일
CY_List.h : 리스트 구현에 필요한 함수 및 구조체 선언 => 본 글에서는 생략한다.(cpp파일만 봐도 알겠죠?)
test.cpp : 구현한 리스트를 이용해서 만든 예제 프로그램

▶Node 초기화◀

우선 본 글은 리스트를 구현하는 것에 초점이 맞춰져 있기 때문에 node의 구조는 단순히 정수형 데이터와 다음 node를 가르키는 포인터로만 구현하였다.
(template을 이용하면 저장되는 data 형식을 동적으로 지정할 수 있지만 template에 관하여는 다음 기회에...)
위에서 구현한 내용은 리스트를 초기화 하는 함수(CY_InitList())와 node에 메모리를 할당하는 함수(CY_AllocNode())이다.
CY_InitList 함수에서는 head와 tail이 dummy node를 가르키게한다.(그림 참조)
일반적으로 head와 tail이 dummy 노드없이 NULL을 가르키게 하는 것만으로 구현할 수 있지만 그럴 경우 추가, 삭제를 위한 동작에서 포인터가 NULL을 가르키는지에 대해 매번 비교해야 하기 때문에 번거러워진다.
이런 일을 줄이기 위해 dummy node를 추가했다. 앞으로 구현해 가면서 살펴보도록 하겠다.

▶Node 추가◀

위의 그림은 리스트의 끝에 노드를 삽입하는 예이다.
리스트를 구현할 때 제일 중요한 것은 각 포인터를 어떤 순서대로 움직일 것인가(대입할 것인가)를 결정하는 것이다.
즉, 그림에서 표현한 것처럼 원하는 동작을 종이에 그려보고 포인터를 이동하는 순서를 기록해 보면 효과적일 것이다.

♨ 쉬어가기 과제. CY_AddToTail(100)을 실행했을 때의 그림을 그려보시오. (위의 그림에서 확장할 것!!)


CY_AddToHead() 함수는 리스트의 첫 머리에 Node를 삽입하는 함수이다.
여기부터는 dummy 때문에 오히려 헷갈리는 부분도 있을 것이다. 조금 더 쉽게 작성하기 위해서 dummy를 사용했는데 그렇지도 않은 것 같다.
dummy가 없는 경우는 CY_AddToHead()가 어떻게 구현되는지 한번 보자.

dummy를 사용하지 않으면 위의 코드처럼 head나 tail이 NULL인지를 체크하는 부분들이 꼭 필요하게 된다.
구현하는 사람의 필요에 따라 자신의 취향대로 구현하면 좋을 것 같다.

♨ 쉬어가기 과제. dummy 노드가 없는 경우의 구현 상황을 그림으로 표현하시오.

리스트의 모든 구현을 본 글에서 다룰려고 했는데 내용이 너무 길어지는 것 같아 이번 글에서는 리스트의 초기화와 삽입에 대해서만 서술하였다.
다음 글에서는 임의의 위치에 노드를 추가하는 부분과 임의의 노드를 삭제하는 방법에 대해 기록하려고 한다.

덧. 이미지 작성에 사용한 도구는 OpenOffice Draw 2.2와 IrfanView 3.99를 이용하였음.