열혈 자료구조 - 4-2. 단순 연결 리스트의 ADT와 구현(2)

연결 리스트 구현

- 구조체 선언

typedef struct _linkedList
{
	Node * head;					// 더미노드를 가르킴
	Node * cur;					// 현재 노드(참조 및 삭제를 도움)
	Node * before;					// 삭제를 돕는 멤버
	int numOfData;					// 데이터 수
	int (*comp)(LData d1, LData d2);		// 정렬에 사용될 함수
} LinkedList;

- 초기화 : 더미 노드를 Head로 지정

void ListInit(List * plist)
{
	plist->head = (Node*)malloc(sizeof(Node));		// 더미노드
	plist->head->next = NULL;
	plist->comp = NULL;
	plist->numOfData = 0;
}

- 삽입 : 정렬 기준(정렬에 사용되는 함수)를 설정하지 않았을 경우는 FInsert, 설정했다면 SInsert를 실행

void LInsert(List * plist, LData data)
{
	if(plist->comp == NULL)
		FInsert(plist, data);
	else
		SInsert(plist, data);
}

    -> FInsert

void FInsert(List * plist, LData data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->next = plist->head->next;
	plist->head->next = newNode;			// Head에 추가

	(plist->numOfData)++;
}

NewNode 생성

추가

    -> SInsert

void SInsert(List * plist, LData data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	Node * pred = plist->head;
	newNode->data = data;

	while(pred->next != NULL && plist->comp(data, pred->next->data) != 0)
	{
		pred = pred->next;
	}

	newNode->next = pred->next;
	pred->next = newNode;

	(plist->numOfData)++;
}

- 검색

    -> LFirst : before을 head(더미노드)로 cur을 head 다음의 노드를 가르키게 하여 cur의 실제 데이터를 넘겨줌

int LFirst(List * plist, LData * pdata)
{
	if(plist->head->next == NULL)
		return FALSE;

	plist->before = plist->head;		// 더미노드
	plist->cur = plist->head->next;		// 더미노드 다음 노드

	*pdata = plist->cur->data;
	return TRUE;
}

    -> LNext : 이전의 cur를 before로 그 다음 노드를 cur로 가르켜 cur의 데이터를 넘겨줌

int LNext(List * plist, LData * pdata)
{
	if(plist->cur->next == NULL)
		return FALSE;

	plist->before = plist->cur;
	plist->cur = plist->cur->next;

	*pdata = plist->cur->data;
	return TRUE;
}

- 삭제

    -> rpos는 cur을 옮긴 후 해당 노드를 삭제하기 위해 cur의 주소를 담는 포인터 변수

    -> cur을 before 쪽으로 옮기는 이유는 6이 있는 노드는 순차적으로 참조,삭제 되는 과정에서 아직 참조가 되지 않았기 때문

    -> before은 이전으로 옮기려면 추가의 포인터 변수가 필요하고 LRemove는 조회(LFirst나 LNext)를 실행 후에 실행이 되기 때문에 조회 시 어처피 before와 cur가 조정되어 굳이 옮길 필요가 없음

LData LRemove(List * plist)
{
	Node * rpos = plist->cur;
	LData rdata = rpos->data;

	plist->before->next = plist->cur->next;
	plist->cur = plist->before;

	free(rpos);
	(plist->numOfData)--;
	return rdata;
}