단순 연결 리스트의 ADT와 구현(4) 이어서

04-2. 윤성우의 열혈 자료구조 ④

#ifndef __D_LINKED_LIST_H__
#define __D_LINKED_LIST_H__

#define TRUE	1
#define FALSE	0

typedef int LData;
typedef struct _node // 노드 구조체
{
	LData data;
	struct _node * next;
} Node;

typedef struct _linkedList // 연결리스트 구조체
{
	Node * head;
	Node * cur;
	Node * before;
	int numOfData;
	int (*comp)(LData d1, LData d2);
} LinkedList;

**typedef LinkedList List**;

void ListInit(List * plist);
void LInsert(List * plist, LData data);

int LFirst(List * plist, LData * pdata);
int LNext(List * plist, LData * pdata);

LData LRemove(List * plist);
int LCount(List * plist);

void SetSortRule(List * plist, int (*comp)(LData d1, LData d2));

#endif

헤더파일을 보면 순차 리스트의 헤더파일과 매개변수(List)가 같음을 알 수 있다.

다만 List의 typedef는 다르다. 즉, 앞으로는 Typedef만 바꾸면 같은 ADT를 계속 활용할 수 있다는 의미임.

• 강의에서 짚고 넘어가지 않은 부분이 책에 적혀있어서 남긴다. 헤더에서 head와 cur, before등을 따로 지역변수나 전역변수 등으로 선언하지 않고, 하나의 구조체로 묶어준 것은… 프로세스가 여러개의 연결리스트를 요구할때, 그때마다 일일이 전역변수로 head…등을 선언해주는건 매우 불필요한 일이기 때문이다. 따라서 이들을 모두 연결리스트구조체로 묶어주고, 이후에 Init함수로 필요할때마다 초기화해서 사용할 수 있도록 한다.

이제 하나씩 구현해보자.

void ListInit(List * plist);

자만하지 말고 그림을 그리며 구현한다. 그리고 우리가 초기화하는건, 어떤 한 노드가 아니라 연결리스트 구조체 자체이다.

노드는 동적할당으로 알아서 초기화될것임.

void ListInit(List* plist)
{
	plist->head = (Node*)malloc(sizeof(Node));
	plist->head->next = plist->head;
	plist->cur = NULL;
	plist->before = NULL;
	plist->comp = NULL;
	plist->numOfData = 0;
}

초기화를 다음과 같이 설정했다.

그런데 강의에서는

이렇게 진행한다. 차이점은

1. cur, before의 초기화를 진행하지 않았다.
2. head→next를 NULL로 초기화했다.

1.은 왜인지 잘모르겠다… 초기화해줄때 같이 해주는게 낫지 않나? 아마 나중에 cur이나 before를 사용할때 초기화해서 사용할 목적인지도 모르겠다.

2.도 아마 NULL로 초기화하고, 나중에 다른 노드 연결해서 사용할때 시작을 head→next = head로 두려는 것 같다…