[열혈자료구조] 5강. 연결 리스트(Linked List) 3 - (1)

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다.

 

리스트 그림그리기 힘들군요

 

앞서 4강에서 구현한 단순 연결 리스트를 변형하여 원형 연결 리스트를 제작하자.

원형 연결 리스트는 단순 연결 리스트에서 머리에서 가장 먼 노드가 NULL을 가리키는 것이 아니라, 머리에서 가장 가까운 노드를 가리키도록 하여 원형 구조를 이루는 것을 말한다. 새로운 노드 1을 머리에 추가한다고 한다면 아래와 같이 변한다.

 

새로운 노드 1을 꼬리에 추가한다고 하면 아래와 같이 변한다. 이때, 마지막 노드를 가리키는 포인터 변수는 tail이고, 첫 노드를 가리키는 포인터 변수는 tail->next가 된다.

이렇게 원형으로 연결 리스트를 구현하는 것의 특징은, LNext 함수의 무한 호출이 가능하여, 마지막 노드에서 호출했을 때 다시 첫 노드로 돌아온다는 것이다. 또한, 정렬 기능은 구현하기 불편해지므로 제외한다. 그리고 머리와 꼬리에 모두 노드를 추가할 수 있다. 

 

헤더 파일

 

LInsert와 LInsertFront 함수를 제외하고는 단순 연결리스트의 헤더와 동일하다. LInsert는 꼬리에, LInsertFront는 머리에 노드를 추가하는 함수이다.

#ifndef __C_LINKED_LIST_H__
#define __C_LINKED_LIST_H__

#define TRUE	1
#define FALSE	0

typedef int Data;

typedef struct _node
{
	Data data;
	struct _node * next;
} Node;

typedef struct _CLL
{
	Node * tail;
	Node * cur;
	Node * before;
	int numOfData;
} CList;


typedef CList List;

void ListInit(List * plist);
void LInsert(List * plist, Data data);
void LInsertFront(List * plist, Data data);

int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);
Data LRemove(List * plist);
int LCount(List * plist);

#endif

 

초기화, 노드의 삽입

 

초기화는 아래와 같이 tail, cur, before를 NULL로 설정한다.

void ListInit(List * plist)
{
	plist->tail = NULL;
	plist->cur = NULL;
	plist->before = NULL;
	plist->numOfData = 0;
}

첫 번째 노드가 추가되면, tail이 그 노드를 가리키게 되고, 추가된 노드는 자기 자신을 가리킨다. 첫 번째 노드를 추가하는 과정은 아래와 같이 코드로 작성할 수 있다.

void LInsert(List * plist, Data data){  //LInsertFront도 첫 노드 삽입 방법은 같다
    Node * newNode = (Node *) malloc(sizeof(Node));

    newNode->data = data;

    if(plist->tail->next == NULL){
        plist->tail = newNode;
        newNode->next = newNode;
    }
    else{
        
    }
    plist->numOfData++;
    
}

두 번째 이후의 노드부터는 LInsert와 LInsertFront가 달라진다. LInsert는 2 노드"를" 가리키는 자리에 새로운 노드를 넣고, LInsertFirst는 2 노드 "가" 가리키는 자리에 새로운 노드를 넣는다. else 부분이 다르므로, 이 부분만 코드를 첨부하겠다.

//LInsertFront
else
{
     newNode->next = plist->tail->next;
     plist->tail->next = newNode;
}

//LInsert
else
{
     newNode->next = plist->tail->next;
     plist->tail->next = newNode;
     plist->tail = newNode;
}

 

LInsertFront는 머리 부부네, LInsert는 꼬리 부분에 새 노드를 추가하는 것이다. 하지만, 이들은 최종 결과를 비교해 봤을 때 tail이 가리키고 있는 곳의 위치만 다를 뿐, 나머지 노드의 배열은 같다.따라서, LInsert의 코드를 보아도, LInsert와 동일하며 마지막에 plist->tail의 위치를 옮겨주는 부분만 다르다.

데이터 조회

 

데이터 조회를 위해 LFirst, LNext 함수를 구현할 것이며, 이를 위해 아래와 같은 Circular LinkedList(CList) 구조체를 정의하였다.

typedef struct _CLL
{
	Node * tail;
	Node * cur;
	Node * before;
	int numOfData;
} CList;

 

여기서 cur와 before의 역할은 단순 연결 리스트와 동일하고, LFirst에서 before는 tail로, cur는 tail->next로 초기화된다.

int LFirst(List * plist, Data * pdata)
{
	if(plist->tail == NULL) 
		return FALSE;

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

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

 

또한 LNext는 tail이 NULL을 가리킨다면 FALSE를 반환하고, 데이터가 존재하는 경우 before를 cur이 있는 곳으로 옮기고 cur이 다음 노드를 가리키게 한 후 cur이 가리키는 노드의 데이터를 반환한다.

int LNext(List * plist, Data * pdata)
{
	if(plist->tail == NULL)
		return FALSE;

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

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

 

노드의 삭제

 

단순 연결 리스트에서는 아래와 같이 before와 cur을 이용한 두 가지 과정을 거쳐 노드를 삭제하였다.

1. 삭제할 노드 앞의 노드와 삭제할 노드 뒤의 노드 연결
2. cur을 한칸 뒤로 이동

이는 원형 연결 리스트에서도 동일하여 적용된다. 대신, 두 가지 예외가 발생한다.

1. 삭제할 노드를 tail이 가리키고 있는 경우: tail도 한칸 앞으로 옮겨야 한다.
2. 리스트에 노드가 하나만 남아 있을 경우: 초기화 상태의 원형 리스트로 만들어야 한다.

이 두 가지 상황을 반영하여 아래와 같이 코드를 작성하자.

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

	if(rpos == plist->tail)
	{
		if(plist->tail == plist->tail->next)
			plist->tail = NULL;
		else
			plist->tail = plist->before;
	}

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

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

 

---

이러한 원형 연결 리스트는 순환되는 구조의 데이터(직원의 당직 순서 등)을 저장하기에 유리한 자료구조이다. 다음 포스팅에서는 연결 리스트의 마지막 자료구조인 양방향 연결 리스트(doubly linked list)에 대해 다룰 예정이다.