[Data Structure] Singly Linked List

연결 리스트(Linked List) - 포인터로 구현

• 데이터의 집합을 저장하기 위해 사용되는 데이터
• 연속되는 항목들이 포인터로 연결
• 동적으로 리스트의 크기가 커지거나 줄어들 수 있음
• 필요한 만큼 메모리를 사용하기 때문에 불필요한 메모리를 낭비하지 않음

연결 리스트를 배열로 구현 할 경우, 속도가 빠르지만, 일정한 메모리를 미리 확보해야 한다는 단점이 있다.
연결 리스트를 포인터를 이용하여 구현할 경우, 필요한 만큼 객체를 생성하기 때문에 낭비되는 부분이 없다. 하지만 포인터를 저장하는 공간이 필요하기 때문에 객체 1개당 필요한 메모리가 배열보다 커진다는 단점이 있다.

아래의 코드는 포인터를 이용한 단일 연결 리스트(Singly Linked List)를 구현했다.
우선, 연결 리스트를 관리하기 위한 구조체를 선언하였고, head node 와 tail node 를 추가하였다.
두 노드는 값을 가지지 않고, 단지 시작 노드와 끝 노드의 포인터 값을 가지고 있다.
그림으로 표현하면, 아래와 같은 구조다.

singly linked list 구조

head node 와 tail node 사이에 추가, 삭제, 변경 등이 이루어진다.
단일 연결 리스트를 class 화 하여 구현하였다.

단일 연결 리스트의 데이터 구조

• Node 구조체

// linked list node
struct Node 
{
	int iValue;
	Node* next;
};

• 연결 리스트 관리 구조체

// single linked list 관리 구조체			
// Head Node -> Node -> ..... -> Tail Node 의 구조
// Head, Tail node 에는 value 가 없다.
struct List
{
	Node*	pHead;
	Node*	pTail;
	int	iSize;
};

 

단일 연결 리스트 함수

• 단일 연결 리스트 생성

bool CSingleLinkedList::CreateList()
{
	bool bRet = false;
	m_pList = (List*)malloc(sizeof(List));
	if (NULL == m_pList)
		return false;

	// 관리 구조체의 head 노드 생성. 포인터 값만 있을 뿐, 데이터는 없음.
	m_pList->pHead = (Node*)malloc(sizeof(Node));
	if (NULL == m_pList->pHead)
		return false;

	// 관리 구조체의 tail 노드 생성. 포인터 값만 있을 뿐, 데이터는 없음.
	m_pList->pTail = (Node*)malloc(sizeof(Node));
	if (NULL == m_pList->pTail)
	{
		free(m_pList->pHead);
		return false;
	}

	// 초기에 head의 next는 tail을 가리킴. 생성된 node가 없기 때문.
	m_pList->pHead->next = m_pList->pTail;
	// tail의 next는 자기 자신을 가리킴.
	m_pList->pTail->next = m_pList->pTail;
	m_pList->iSize = 0;

	return bRet;
}

• 노드 삽입 (앞쪽)

// head 노드 다음에 node 추가.
bool CSingleLinkedList::AddNodeFirst(int iValue)
{
	if (NULL == m_pList)
		return false;

	bool bRet = true;

	Node* newNode = (Node*)malloc(sizeof(Node));
	if (NULL == newNode)
		return false;

	newNode->iValue = iValue;
	// 새롭게 추가되는 노드의 next는 기존에 head 노드의 next로 설정.
	newNode->next = m_pList->pHead->next;
	
	// head 노드의 next를 새롭게 추가되는 노드로 설정.
	m_pList->pHead->next = newNode;
	m_pList->iSize++;
	
	return bRet;
}

• 노드 삽입 (뒷쪽)

// tail 노드 앞에 node 추가.
bool CSingleLinkedList::AddNodeLast(int iValue)
{
	if (NULL == m_pList)
		return false;

	bool bRet = true;
	Node* pTmp;
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (NULL == newNode)
		return false;

	newNode->iValue = iValue;
	// 새롭게 추가되는 노드의 next는 tail 노드.
	newNode->next = m_pList->pTail;
	
	// pTemp 노드에 담기는 내용이 Head 노드임에 주의
	pTmp = m_pList->pHead;
	while (pTmp->next != m_pList->pTail)
	{
		pTmp = pTmp->next;
	}

	pTmp->next = newNode;

	m_pList->iSize++;
	bRet = true;

	return bRet;
}

• 노드 삭제

bool CSingleLinkedList::RemoveNode(int iValue)
{
	if (NULL == m_pList)
		return false;

	bool bRet = true;
	Node* pRemoveNode;
	Node* pPrevNode;

	pRemoveNode = SearchList(iValue);
	if (NULL == pRemoveNode)
		return false;
	
	pPrevNode = m_pList->pHead;

	while (pPrevNode->next != pRemoveNode)
	{
		pPrevNode = pPrevNode->next;
	}

	pPrevNode->next = pRemoveNode->next;
	free(pRemoveNode);
	m_pList->iSize--;
	
	return bRet;
}

• 노드 검색

Node* CSingleLinkedList::SearchList(int iValue)
{
	if (NULL == m_pList)
		return NULL;

	Node* pSearchNode;

	pSearchNode = m_pList->pHead->next;

	while (pSearchNode != m_pList->pTail)
	{
		if (iValue == pSearchNode->iValue)
			return pSearchNode;
		else
			pSearchNode = pSearchNode->next;
	}

	return NULL;
}

• 노드 정렬 (오름차순)

void CSingleLinkedList::SortList()
{
	if (NULL == m_pList)
		return;

	Node* pCurNode;
	Node* pNextNode;
	int iTemp = 0;

	pCurNode = m_pList->pHead->next;

	while (m_pList->pTail != pCurNode->next)
	{
		pNextNode = pCurNode->next;
		while (m_pList->pTail != pNextNode)
		{
			if (pCurNode > pNextNode)
			{
				iTemp = pNextNode->iValue;
				pNextNode->iValue = pCurNode->iValue;
				pCurNode->iValue = iTemp;
			}
			pNextNode = pNextNode->next;
		}
		pCurNode = pCurNode->next;
	}

	return;
}

• 단일 연결 리스트 노드 출력

void CSingleLinkedList::ShowList()
{
	if (NULL == m_pList)
		return;

	Node* pCurNode;

	pCurNode = m_pList->pHead->next;

	while (pCurNode != m_pList->pTail)
	{
		printf("data: %d\n", pCurNode->iValue);

		pCurNode = pCurNode->next;
	}

	return;
}

• 단일 연결 리스트 제거

bool CSingleLinkedList::DeestroyList()
{
	if (NULL == m_pList)
		return false;

	bool bRet = true;
	Node* pCurNode;
	Node* pNextNode;

	pCurNode = m_pList->pHead->next;
	while (m_pList->pTail != pCurNode)
	{
		pNextNode = pCurNode->next;
		free(pCurNode);
		pCurNode = pNextNode;
	}

	free(m_pList->pHead);
	free(m_pList->pTail);
	
	m_pList->pHead = m_pList->pTail = NULL;
	m_pList->iSize = 0;
	
	free(m_pList);
	m_pList = NULL;
	
	return bRet;
}

해당 단일 연결 리스트는 int 형의 자료에 대하여 동작한다.
사용성이 한정적이기 때문에 template 를 이용하여 다양한 자료형에 대하여 사용할 수 있도록 구현해봐야겠다.

 

template 를 이용하여 구현

#pragma once

#include <stdio.h>
#include <malloc.h>

template<typename T>
struct Node 
{
	T Value;
	Node<T> *next;
};

template<typename T>
struct List
{
	Node<T>	*pHead;
	Node<T>	*pTail;
	int		iSize;
};


template<typename T>
class CSinglyLinkedList
{
public:
	CSinglyLinkedList(): m_pList(NULL) {};
	~CSinglyLinkedList() {};

public:
	bool CreateList()
	{
		bool bRet = true;
		m_pList = (List<T>*)malloc(sizeof(List<T>));
		if (NULL == m_pList)
			return false;

		m_pList->pHead = (Node<T>*)malloc(sizeof(Node<T>));
		if (NULL == m_pList->pHead)
			return false;

		m_pList->pTail = (Node<T>*)malloc(sizeof(Node<T>));
		if (NULL == m_pList->pTail)
		{
			free(m_pList->pHead);
			return false;
		}

		m_pList->pHead->next = m_pList->pTail;
		m_pList->pTail->next = m_pList->pTail;
		m_pList->iSize = 0;

		return bRet;
	}

	bool AddNodeFirst(T Value)
	{
		if (NULL == m_pList)
			return false;

		bool bRet = true;

		Node<T> *newNode = (Node<T>*)malloc(sizeof(Node<T>));
		if (NULL == newNode)
			return false;

		newNode->Value = Value;
		newNode->next = m_pList->pHead->next;

		m_pList->pHead->next = newNode;
		m_pList->iSize++;

		return bRet;
	}

	bool AddNodeLast(T Value)
	{
		if (NULL == m_pList)
			return false;

		bool bRet = true;
		Node<T>* pTmp;
		Node<T>* newNode = (Node<T>*)malloc(sizeof(Node<T>));
		if (NULL == newNode)
			return false;

		newNode->Value = Value;
		newNode->next = m_pList->pTail;

		pTmp = m_pList->pHead;
		while (pTmp->next != m_pList->pTail)
		{
			pTmp = pTmp->next;
		}

		pTmp->next = newNode;

		m_pList->iSize++;

		return bRet;
	}

	Node<T>* SearchList(T Value)
	{
		if (NULL == m_pList)
			return NULL;

		Node<T>* pSearchNode;

		pSearchNode = m_pList->pHead->next;

		while (pSearchNode != m_pList->pTail)
		{
			if (Value == pSearchNode->iValue)
				return pSearchNode;
			else
				pSearchNode = pSearchNode->next;
		}

		return NULL;
	}

	bool RemoveNode(T Value)
	{
		if (NULL == m_pList)
			return false;

		bool bRet = false;
		Node<T>* pRemoveNode;
		Node<T>* pPrevNode;
		
		for (;;)
		{
			pRemoveNode = SearchList(Value);
			if (NULL == pRemoveNode)
			{
				bRet = false;
				break;
			}
			pPrevNode = m_pList->pHead;

			while (pPrevNode->next != pRemoveNode)
			{
				pPrevNode = pPrevNode->next;
			}

			pPrevNode->next = pRemoveNode->next;
			free(pRemoveNode);
			m_pList->iSize--;
			
			
			bRet = true;
			break;
		}
		
		return bRet;
	}

	bool DeestroyList()
	{
		if (NULL == m_pList)
			return false;

		bool bRet = true;
		Node<T>* pCurNode;
		Node<T>* pNextNode;

		pCurNode = m_pList->pHead->next;
		while (m_pList->pTail != pCurNode)
		{
			pNextNode = pCurNode->next;
			free(pCurNode);
			pCurNode = pNextNode;
		}

		free(m_pList->pHead);
		free(m_pList->pTail);

		m_pList->pHead = m_pList->pTail = NULL;
		m_pList->iSize = 0;

		free(m_pList);
		m_pList = NULL;

		return bRet;
	}

private:
	List<T> *m_pList;
};