5. 연결 리스트 -c. 이중 원형 연결 리스트

이중 원형 연결 리스트

  # 이중 원형 연결 리스트는 마지막 노드가 첫번째 노드를 가리키고, 첫번째 노드도 마지막 노드를 가리키게 함으로 원형 구조를 이루게 한 이중 연결 리스트다.

  # 그러므로 순회시 따로 끝을 지정하지 않는한 무한 루프를 돌게 된다. 

  # 앞에 두개는 처음이나 끝에 도달했는데도 계속 prev나 next를 호출하면 각각 첫 노드나 끝 노드를 계속 반환하도록 했었다.

  # 앞에 두개에서는 Head포인터와 Tail포인터 두개를 사용했으나 Head포인터 하나로 두 위치를 모두 표시할 수 있다. (Head의 prev가 Tail임으로)

  # 연결 리스트의 특성상 특정 위치의 노드를 찾기 위해서는 각각의 노드를 거쳐가야 하므로 최악의 경우 size만큼의 노드를 확인해야한다.

  # 하지만 이중 원형 연결 리스트는 거쳐갈 노드의 수가 최악의 경우에도 size/2로 줄일 수 있다.

  # 원형 리스트는 STL에 포함되어 있지 않다.

이중 원형 연결 리스트의 ADT

  1. 원하는 위치에 노드를 추가할 수 있다.

  2. 원하는 위치의 노드를 삭제할 수 있다.  

  3. 원하는 위치의 노드의 값을 수정할 수 있다.

  4. 리스트 전체를 양방향으로 순회할 수 있다.

  5. 리스트의 전체 노드수를 확인할 수 있다.

  6. 리스트가 비어있는 경우는 사용자가 알아서 예외처리를 한다고 가정한다.

C++로 구현한 이중 원형 연결 리스트

 #pragma once

template <typename T>
class SircularLinkedList
{
	template <typename T>
	struct node {
		T data;
		node<T>* prev;
		node<T>* next;
	};

	node<T>* pHead;
	node<T>* pCursor;

	int iSize;

public:
	int getSize();

	int AddData(int index, T data);       //지정한 위치에 데이터 추가.
	T& CheckData(int index);              //지정한 위치에 있는 데이터를 확인.
	void ChangeData(int index, T data);   //지정한 위치에 있는 데이터를 수정.
	int DeleteData(int index);            //지정한 위치에 있는 데이터 삭제.
	int DeleteValue(T data);              //지정한 값을 가진 노드(들) 삭제.


	void SetCursor(int index);            //커서 포인터를 지정한 위치로 이동.
	//리스트 순회용
	T& Next();
	T& Prev();

public:
	SircularLinkedList();
	~SircularLinkedList();
};

template <typename T>
SircularLinkedList<T>::SircularLinkedList()
{
	pHead = nullptr;
	iSize = 0;
}

//getMethod
template <typename T>
int SircularLinkedList<T>::getSize()
{
	return iSize;
}

//원하는 위치에 데이터 추가 (맨 앞에 추가하고 싶다면 -1을, 맨 끝에 추가하고 싶다면 getSize()사용)
template <typename T>
int SircularLinkedList<T>::AddData(int index, T data)
{
	node<T>* newnode = new node<T>;
	newnode->data = data;

	if (pHead == nullptr) {
		newnode->prev = newnode;
		newnode->next = newnode;
		pCursor = pHead = newnode;
	}
	else {
		if (index <= 0 || index >= iSize - 1) {
			newnode->prev = pHead->prev;
			newnode->next = pHead;
			pHead->prev->next = newnode;
			pHead->prev = newnode;
			if (index <= 0) {
				pCursor = pHead = newnode;
			}
		}
		else {
			node<T>* pFind = pHead;
			if (index <= iSize / 2) {
				for (int i = 0; i < index - 1; i++) {
					pFind = pFind->next;
				}
			}
			else {
				for (int i = 0; i < iSize - index + 1; i++) {
					pFind = pFind->prev;
				}
			}
			newnode->prev = pFind;
			newnode->next = pFind->next;
			pFind->next->prev = newnode;
			pFind->next = newnode;
		}
	}

	return ++iSize;
}

//지정한 위치에 있는 데이터를 확인.
template <typename T>
T& SircularLinkedList<T>::CheckData(int index)
{
	int iIndex = index;
	if (index >= iSize) {
		iIndex = iSize - 1;
	}

	node<T>* pFind = pHead;
	if (iIndex <= iSize / 2) {
		for (int i = 0; i < iIndex; i++) {
			pFind = pFind->next;
		}
	}
	else {
		for (int i = 0; i < iSize - iIndex; i++) {
			pFind = pFind->prev;
		}
	}

	return pFind->data;
}

//지정한 위치에 있는 데이터를 수정.
template <typename T>
void SircularLinkedList<T>::ChangeData(int index, T data)
{
	int iIndex = index;
	if (index >= iSize) {
		iIndex = iSize - 1;
	}

	node<T>* pFind = pHead;
	if (iIndex <= iSize / 2) {
		for (int i = 0; i < iIndex; i++) {
			pFind = pFind->next;
		}
	}
	else {
		for (int i = 0; i < iSize - iIndex; i++) {
			pFind = pFind->prev;
		}
	}

	pFind->data = data;
}

//지정한 위치에 있는 데이터를 삭제
template <typename T>
int SircularLinkedList<T>::DeleteData(int index)
{
	if (pHead == nullptr) {
		return 0;
	}

	node<T>* pDel = nullptr;
	int iIndex = index;

	if (index <= 0) {
		pDel = pHead;
		pHead = pHead->next;
		pDel->prev->next = pHead;
		pHead->prev = pDel->prev;
		delete pDel;
		pCursor = pHead;
		return --iSize;
	}

	if (index >= iSize - 1) {
		pDel = pHead->prev;
		pDel->prev->next = pHead;
		pHead->prev = pDel->prev;
		delete pDel;
		return --iSize;
	}
	
	if (index > iSize - 1) {
		iIndex = iSize - 1;
	}

	node<T>* pFind = pHead;
	if (iIndex <= iSize / 2) {
		for (int i = 0; i < iIndex - 1; i++) {
			pFind = pFind->next;
		}
	}
	else {
		for (int i = 0; i < iSize - iIndex + 1; i++) {
			pFind = pFind->prev;
		}
	}

	pDel = pFind->next;
	pFind->next = pDel->next;
	pDel->next->prev = pFind;
	delete pDel;
	
	return --iSize;
}

//특정한 값을 가진 노드(들) 삭제
template <typename T>
int SircularLinkedList<T>::DeleteValue(T data)
{
	if (pHead == nullptr) {
		return 0;
	}

	node<T>* pDel = nullptr;
	while (pHead->data == data) {
		pDel = pHead;
		pHead = pHead->next;
		pDel->prev->next = pHead;
		pHead->prev = pDel->prev;
		delete pDel;
		pCursor = pHead;
		iSize--;
		if (iSize == 0) {
			pHead = nullptr;
			return 0;
		}
	} 


	node<T>* pFind = pHead;
	while (pFind->next != pHead) {
		if (pFind->next->data == data) {
			pDel = pFind->next;
			pFind->next = pDel->next;
			pDel->next->prev = pFind;
			delete pDel;
			iSize--;
		}
		else {
			pFind = pFind->next;
		}
	}
	return iSize;
}

//커서 포인터를 지정한 위치로 이동.
template <typename T>
void SircularLinkedList<T>::SetCursor(int index)
{
	pCursor = pHead;
	int iIndex = index;

	if (index > iSize - 1) {
		iIndex = iSize - 1;
	}

	if (iIndex <= iSize / 2) {
		for (int i = 0; i < iIndex; i++) {
			pCursor = pCursor->next;
		}
	}
	else {
		for (int i = 0; i < iSize - iIndex; i++) {
			pCursor = pCursor->prev;
		}
	}
}

//리스트 순회용
template <typename T>
T& SircularLinkedList<T>::Next()
{
	T& ret = pCursor->data;

	if (pCursor->next != nullptr) {
		pCursor = pCursor->next;
	}

	return ret;
}

template <typename T>
T& SircularLinkedList<T>::Prev()
{
	T& ret = pCursor->data;

	if (pCursor->prev != nullptr) {
		pCursor = pThis->prev;
	}

	return ret;
}


template <typename T>
SircularLinkedList<T>::~SircularLinkedList()
{
	node<T>* pDel = nullptr;
	node<T>* pFind = pHead;
	while (pFind != nullptr) {
		pDel = pFind;
		pFind = pFind->next;
		delete pDel;
	}

	pHead = nullptr;
	pCursor = nullptr;

	iSize = 0;
}