5. 연결 리스트 -a. 단일 연결 리스트

연결 리스트

  # 연결 리스트는 노드가 '데이터'부분과 다음 노드를 가리키는 '링크'부분으로 이루어진 리스트이다.

  # C/C++에서는 연결 리스트의 링크 부분을 포인터로 구현하며 그렇기에 선형 리스트와는 달리 연속된 메모리 공간을 필요로 하지 않는다는 장점이 있다.

  # 연결 리스트는 어떻게 연결하느냐에 따라서 '단일 연결 리스트', '이중 연결 리스트', '원형 연결 리스트'등으로 나뉜다. 

  # (Chunked List)라는 것도 있다는 것 같은데 잘 모르겠으므로 생략한다.

  # 단일 연결 리스트는 이전 노드가 다음 노드를 가리키는 포인터만 가지고 있는 구조이다.

단일 연결 리스트의 ADT

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

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

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

  4. 리스트 전체를 순회할 수 있다.

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

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

C++로 구현한 단일 연결 리스트

#pragma once

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

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

	int iSize;

public:
	int getSize();

	int AddData(T data);                  //리스트 끝에 데이터 추가
	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(); //리스트 순회용

public:
	SingleLinkedList();
	~SingleLinkedList();
};

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

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


//리스트 끝에 데이터 추가
template <typename T>
int SingleLinkedList<T>::AddData(T data)
{
	node<T>* newnode = new node<T>;
	newnode->data = data;
	newnode->next = nullptr;

	if (pHead == nullptr) {
		pHead = newnode;
		pCursor = pHead;
	}
	else {
		pTail->next = newnode;
	}
	pTail = newnode;
	
	return ++iSize;
}

//원하는 위치에 데이터 추가
template <typename T>
int SingleLinkedList<T>::AddData(int index, T data)
{
	node<T>* newnode = new node<T>;
	newnode->data = data;
	newnode->next = nullptr;

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

	return ++iSize;
}

//지정한 위치에 있는 데이터를 확인.
template <typename T>
T& SingleLinkedList<T>::CheckData(int index)
{
	int iIndex = index;
	if (index <= 0) {
		iIndex = 0;
	}
	node<T>* pFind = pHead;
	for (int i = 0; i < iIndex; i++) {
		pFind = pFind->next;
	}
	
	return pFind->data;
}

//지정한 위치에 있는 데이터를 수정.
template <typename T>
void SingleLinkedList<T>::ChangeData(int index, T data)
{

	int iIndex = index;
	if (index <= 0) {
		iIndex = 0;
	}
	node<T>* pFind = pHead;
	for (int i = 0; i < iIndex; i++) {
		pFind = pFind->next;
	}

	pFind->data = data;
}

//지정한 위치에 있는 데이터를 삭제
template <typename T>
int SingleLinkedList<T>::DeleteData(int index)
{
	node<T>* pDel = nullptr;
	int iIndex = index;

	if (index <= 0) {
		pDel = pHead;
		pHead = pHead->next;
		delete pDel;
		pCursor = pHead;
	}
	else if (index >= iSize - 1) {
		iIndex = iSize - 1;
	}

	node<T>* pFind = pHead;
	for (int i = 0; i < iIndex -1; i++) {
		pFind = pFind->next;
	}

	if (pFind->next == pTail) {
		pTail = pFind;
	}

	pDel = pFind->next;
	pFind->next = pDel->next;
	delete pDel;

	return --iSize;
}

//특정한 값을 가진 노드(들) 삭제
template <typename T>
int SingleLinkedList<T>::DeleteValue(T data)
{
	node<T>* pDel = nullptr;
	while (pHead != nullptr && pHead->data == data) {
		pDel = pHead;
		pHead = pHead->next;
		delete pDel;
		pCursor = pHead;
		iSize--;
	}

	if (pHead == nullptr) {
		return 0;
	}

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

	return iSize;
}

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

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

	for (int i = 0; i < iIndex; i++) {
		pCursor = pCursor->next;
	}
}

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

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

	return ret;
}


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

	iSize = 0;
}