5. 원형 연결 리스트 3 (원형 + 양방향)

2019. 6. 6. 18:05

1. 원형 연결리스트

▣ 원형 연결 리스트의 이해

단순 연결 리스트의 마지막 노드는 NULL을 가리킨다

원형 연결 리스트의 마지막 노드는 첫 번째 노드를 가리킨다

∙ 원형 연결리스트는 모든 노드가 원의 형태를 이루면서 연결되어 있기 때문에 원형 연결 리스트 에서는 사실상 머리와 꼬리의 구분이 없다

∙ 두 경우의 노드 연결 순서가 같으니, 원형 연결리스트는 head가 가리키는 노드가 다르다.

▣ 원형 연결 리스트의 장점

“단순 연결 리스트처럼 머리와 꼬리를 가리키는 포인터 변수를 각각 두지 않아도, (2개)
하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다.” (1개) 만으로도 가능

앞서 소개한 모델을 기반으로는 위의 장 점을 살리기 어렵다.
그래서 우리는 변형 된, 그러나 보다 일반적이라고 인식이 되고 있는 변경된 원형 연결 리스트를 구현한다.

▣ 변형된 연결 리스트

∙ 꼬리를 가리키는 포인터 변수는? tail

∙ 머리를 가리키는 포인터 변수는? tail->next

이렇듯 리스트의 꼬리와 머리의 주소 값을 쉽게 확인할 수 있기 때문에,
연결 리스트를 가리키는 포인터 변수는 하나만 있으면 된다.

▣ 변형된 연결 리스트변형된 원형 연결 리스트의 구현 범위

※ 원형 연결 리스트는 그 구조상 끝이 존재하지 않는다.
따라서 LNext 함수는 계속해서 호출이 가능하고, 이로 인해서 리스트를 순환하면서 저장된 값을 반환하도록 구현한다.

▶ 구조체 정의

typedef struct _linkedList
{
	Node* tail;
	Node* cur;
	Node* before;

	int numOfData;

}LinkedList;

typedef LinkedList List;

▶ 초기화 함수

//초기화
void ListInit(List* pList)
{
	pList->tail;
	pList->cur = NULL;
	pList->before = NULL;
	pList->numOfData = 0;
}

모든 멤버를 NULL과 0으로 초기화한다.

▶ 노드 삽입

void LInsertFront(List* pList, LData data)
{
	Node* newNode = new Node();
	newNode->data = data;

	if (pList->tail == NULL)
	{
		pList->tail = newNode;
		newNode->next = newNode;
	}
	else
	{

	}
	(pList->numOfData)++;
}

첫 번째 노드는 그 자체로 머리이자 꼬리이기 때문에 노드를 뒤에 추가하건 앞에 추가하건 그
결과가 동일하다

▶ 두번쨰 이후 노드 삽입

void LInsertFront(List* pList, LData data)
{
	Node* newNode = new Node();
	newNode->data = data;

	if (pList->tail == NULL)
	{
		pList->tail = newNode;
		newNode->next = newNode;
	}
	else
	{
		newNode->next = pList->tail->next;  //1
		pList->tail->next = newNode;        //2
	}
	(pList->numOfData)++;
}

▶ 원형 연결 리스트 구현: 앞과 뒤의 삽입 과정 비교

void LInsertTail(List* pList, LData data)
{
	Node* newNode = new Node();
	newNode->data = data;

	if (pList->tail == NULL)
	{
		//pList->tail = newNode;
		//newNode->next = newNode;

		pList->tail = newNode;
		newNode->next = newNode;

	}
	else
	{
		newNode->next = pList->tail->next;
		pList->tail->next = newNode;
		pList->tail = newNode;       //꼬리가 newNode 위치로 이동한다 (위 함수와 꼬리 위치가 차이점)
	}
	(pList->numOfData)++;
}

▶ 원형 연결 리스트 구현: 조회

int LFirst(List* pList, LData* pdata)
{
	if (pList->tail == NULL)   
		return false;

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

	*pdata = pList->cur->data;

	return true;
}

cur가 머리를 가리키게 한다

int LNext(List* pList, LData* pdata)
{
	if (pList->tail == NULL)   
		return false;

	pList->before = pList->cur;    
	pList->cur = pList->cur->next; 

	*pdata = pList->cur->data;
	return true;
}

※ 원형 연결 리스트이므로 리스트의 끝을 검사하는 코드가 없다

▶ 원형 연결 리스트 구현: 노드의 삭제

∙ 핵심연산 1. 삭제할 노드의 이전 노드가, 삭제할 노드의 다음 노드를 가리키게 한다.

∙ 핵심연산 2. 포인터 변수 cur을 한 칸 뒤로 이동시킨다.

//더미 연결리스트 삭제 코드
LData LRemove(List* pList)
{
	Node* rpos = pList->cur;
	LData rdata = rpos->data;


	pList->before->next = pList->cur->next;  //1
	pList->cur = pList->before;              //2


	delete rpos;
	(pList->numOfData)--;

	return rdata;
}

※ 더미 노드와 삭제하는 방법은 동일하다

※ 그림상으로는 두 연결 리스트의 삭제 과정이 비슷해 보이나,
원형 연결 리스트에 는 더미 노드가 없기 때문에 삭제의 과정이 상황에 따라서 달라진다.

▶ 원형 연결 리스트 노드 삭제 구현

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

	//삭제할 노드를 tail이 가리킨다면
	if (rpos == pList->tail)
	{
		//그리고 마지막 노드라면
		if (pList->tail == pList->tail->next) //2
		{
			pList->tail == NULL;
		}
		else
		{
			pList->tail = pList->before;	   //1
		}
	}

	//단순 연결리스트와 동일한 코드
	pList->before->next = pList->cur->next;
	pList->cur = pList->before;

	delete rpos;
	(pList->numOfData)--;
	return rdata;
}

2. 양방향 연결리스트

typedef struct _node
{
	int data;  //현재 데이터
	struct _node * next;   //다음 노드를 가르킬 포인터  
	struct _node * precv;  //이전 노드를 가르킬 포인터  

} Node;

양방향 연결 리스트를 위한 노드 구조체 변경

▶ 양방향으로 노드를 연결하는 이유

※ 단순 연결 리스트와 같이 before를 유지할 필요가 없다!

※ 오른쪽 노드로의 이동이 용이하다! 양방향으로 이동이 가능하다!

※ 위의 코드에서 보이듯이 양방향으로 연결한다 하여 더 복잡한 것은 아니다! 그렇게 느낀다면 선입견이다.

▶ 구현할 양방향 연결 리스트 모델

LRemove 함수를 ADT에서 제외시킨다.
대신에 왼쪽 노드의 데이터를 참조하는 LPrevious 함수를 ADT에 추가시킨다.
새 노드는 머리에 추가한다.

▶ 연결 리스트의 구현: 리스트의 초기화

typedef struct _dblinkedList
{
	Node* head;
	Node* cur;
	int numOfData;

}_dblinkedList;

typedef _dblinkedList List;

ListInit 함수의 정의에 참조해야 하는 구조체의 정의

//초기화
void ListInit(List* pList)
{
	pList->head = NULL;
	pList->numOfData = 0;
}

멤버 cur은 조회의 과정에서 초기화 되는 멤버이니 head와 numOfData만 초기화 하면 된다

▶ 연결 리스트의 구현: 노드 삽입

더미 노드를 기반으로 하지 않기 때문에 노드의 삽입 방법은 두 가지로 구분이 된다

▶ 연결 리스트의 구현: 첫번쨰 노드 삽입

void LInsert(List* pList, LData data)
{
	Node* newNode = new Node();
	newNode->data = data;

	newNode->next = pList->head;
	newNode->precv = NULL;
	pList->head = newNode;
	
	(pList->numOfData)++;
}

▶ 연결 리스트의 구현: 두 번째 이후 노드의 삽입

void LInsert(List* pList, LData data)
{
	Node* newNode = new Node();
	newNode->data = data;

	newNode->next = pList->head;

	if (pList->head != NULL) 
	{   //(1/2)
		pList->head->precv = newNode;
	}

	//헤드 이동(2/2)
	newNode->precv = NULL;
	pList->head = newNode;
	
	(pList->numOfData)++;
}

첫 번째 노드의 추가 과정에 덧붙여서, if문이 포함하는 문장이 두 번째 이후의 노드 추가 과정에서는 요구가 된다.

이미 들어있을 경우에는 헤드 이전에 추가를 하고, newNode의 이전을 NULL로 한뒤 헤드를 newNOde로 이동한다

▶ 연결 리스트의 구현: 데이터 조회

int LFirst(List* pList, LData* pdata)
{
	if (pList->head == NULL)   
		return false;

	pList->cur = pList->head;  //처음

	*pdata = pList->cur->data;
	return true;
}

int LNext(List* pList, LData* pdata)
{
	if (pList->head == NULL)
		return false;

	pList->cur = pList->cur->next; //다음거

	*pdata = pList->cur->data;
	return true;
}

int LPreviout(List* pList, LData* pdata)
{
	if (pList->head == NULL)
		return false;

	pList->cur = pList->cur->precv;  //전에거

	*pdata = pList->cur->data;
	return true;
}

※ LFirst 함수와 LNext 함수는 사실상 단방향 연결 리스 트의 경우와 차이가 없다.
LPrevious 함수는 LNext 함수와 이동 방향에서만 차이가 난다

저작자표시

'프로그래밍 > 자료구조' 카테고리의 다른 글

7. 큐 (Queue) (0)	2019.06.10
6. 스택(Stack) (0)	2019.06.07
4. 연결 리스트 2 (연결리스트 + 더미노드 + 정렬삽입) (0)	2019.06.05
3. 연결리스트 1 (ADT + 배열기반 연결리스트) (0)	2019.06.05
2. 재귀(Recursion) (0)	2019.06.04

딩굴딩굴고양이