[Data Structure] Doubly Linked List

이중 연결 리스트 (Doubly Linked List)

• 각 노드가 선행 노드와 후속 노드에 대한 링크를 가지는 리스트

저번에 구현한 단일 연결 리스트에 이어서 이중 연결 리스트를 구현해봤다. 

크게 어려운 것은 없었지만, 노드와 노드간 관계를 재정의 하는 것 (추가, 삭제 등)에 있어서 주의가 필요할 듯 하다.

 

이중 연결 리스트의 구조는 아래 그림을 참고하면 된다.

 

여기서 head / tail 노드는 관리를 위한 노드며, 데이터는 없다.

 

template 를 이용하여 이중 연결 리스트 클래스를 먼저 구현해보았다.

 

이중 연결 리스트의 데이터 구조

• Node 구조체

struct Node
{
	int iValue;
	Node *next; // 다음 노드
	Node *prev; // 이전 노드
};

• 연결 리스트 관리 구조체

struct List
{
	Node *Head;
	Node *Tail;
	int	iSize;
};

이중 연결 리스트 클래스

template<typename T>
class CDoublyLinkedList
{
public:
	CDoublyLinkedList(): m_List(NULL) {};
	~CDoublyLinkedList() {};

public:
	bool CreateList()
	{	
		bool bRet = false;

		for (;;)
		{
			m_List = (List<T>*)malloc(sizeof(List<T>));
			if (NULL == m_List)
				break;

			m_List->Head = (Node<T>*)malloc(sizeof(Node<T>));
			if (NULL == m_List->Head)
			{
				free(m_List);

				break;
			}
			m_List->Tail = (Node<T>*)malloc(sizeof(Node<T>));
			if (NULL == m_List->Tail)
			{
				free(m_List);
				free(m_List->Head);

				break;
			}

			m_List->Head->next = m_List->Tail;
			m_List->Head->prev = m_List->Head;
			m_List->Tail->next = m_List->Tail;
			m_List->Tail->prev = m_List->Head;
			m_List->iSize = 0;

			bRet = true;

			break;
		}

		return bRet;
	}

	bool InsertHead(T _Value)
	{
		if (NULL == m_List)
			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_List->Head->next;
		newNode->prev = m_List->Head;
		m_List->Head->next->prev = newNode;
		m_List->Head->next = newNode;
		m_List->iSize++;

		return bRet;
	}	

	bool InsertTail(T _Value)
	{
		if (NULL == m_List)
			return false;

		bool bRet = true;

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

		newNode->Value = _Value;
		newNode->prev = m_List->Tail->prev;
		newNode->next = m_List->Tail;
		m_List->Tail->prev->next = newNode;
		m_List->Tail->prev = newNode;
		m_List->iSize++;

		return bRet;
	}	

	bool removeHead()
	{
		if (NULL == m_List)
			return false;

		bool bRet = true;

		Node<T> *node;

		if (m_List->Tail != m_List->Head->next)
		{
			node = m_List->Head->next;
			m_List->Head->next->next->prev = m_List->Head;
			m_List->Head->next = m_List->Head->next->next;
			
			free(node);
			node = NULL;
			m_List->iSize--;
		}
		else
		{
			bRet = false;
		}

		return bRet;
	}

	bool removeTail()
	{
		if (NULL == m_List)
			return false;

		bool bRet = true;

		Node<T> *node;

		if (m_List->Head != m_List->Tail->prev)
		{
			node = m_List->Tail->prev;
			m_List->Tail->prev->prev->next = m_List->Tail;
			m_List->Tail->prev = m_List->Tail->prev->prev;
			
			free(node);
			node = NULL;
			m_List->iSize--;
		}
		else
		{
			bRet = false;
		}

		return bRet;
	}

	Node<T>* SearchNode(T _Value)
	{
		if (NULL == m_List)
			return NULL;

		Node<T> *node;

		node = m_List->Head->next;
		while (m_List->Tail != node)
		{
			if (_Value == node->Value)
				break;

			node = node->next;
		}
		
		if (m_List->Tail == node)
			return NULL;
		else
			return node;
	}
	
	bool RemoveNode(T _Value)
	{
		if (NULL == m_List)
			return false;

		bool bRet = true;
		Node<T> * node;

		node = SearchNode(_Value);
		if (NULL == node)
			return false;

		node->prev->next = node->next;
		node->next->prev = node->prev;
		free(node);
		node = NULL;

		m_List->iSize--;

		return bRet;
	}
	
	bool DestroyList()
	{
		Node<T> *curNode;
		Node<T> *nextNode;
		
		curNode = m_List->Head->next;
		while (m_List->Tail != curNode)
		{
			nextNode = curNode->next;
			free(curNode);
			curNode = nextNode;
		}

		free(m_List->Head);
		free(m_List->Tail);

		m_List->Head = m_List->Tail = NULL;
		
		free(m_List);
		
		m_List = NULL;

		return true;
	}

private:
	List<T> *m_List;

};