[자료구조]연결 리스트(Linked List)

연결 리스트(Linked List)

연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는 데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.

따라서 연결 리스트는 연결 리스트의 전체 데이터를 순차 적으로 모두 접근하여 데이터에 따라 처리하는 용도로 사용된다.

<출처 : 위키 백과 :  https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8>

연결 리스트 삽입

연결 리스트에서 삽입 과정은 위 그림과 같습니다. 

삽입할 노드를 NewNode, 삽입할 위치의 이전 노드를 PrevNode, 다음 노드를 NextNode라고 합시다.

1. NewNode의 Next를 NextNode로 연결합니다.

2. NewNode의 Prev를 PrevNode로 연결합니다.

3. PrevNode의 Next를 NewNode로 연결합니다.

4. NextNode의 Prev를 NewNode로 연결합니다.

이 4가지의 과정이 연결 리스트에 새로운 노드를 삽입하는 과정입니다.

연결 리스트 삭제

연결 리스트에서 삭제 과정은 위 그림과 같습니다.

삭제할 노드를 DeleteNode, 삭제할 노드의 이전 노드를 PrevNode, 다음 노드를 NextNode라고 합시다.

1. DeleteNode를 가리키고 있는 PrevNode의 Next를 DeleteNode의 다음 노드인 NextNode로 연결합니다.

2. DeleteNode를 가리키고 있는 NextNode의 Prev를 DeleteNode의 이전 노드인 PrevNode로 연결합니다.

이 2가지의 과정이 연결리스트에서 노드를 삭제하는 과정입니다.

 

 

<코드>

Node Class

class C_LINKEDLIST;

class C_NODE
{
private:
	friend C_LINKEDLIST;
private:
	int m_nData;
	C_NODE* m_pNextNode;
	C_NODE* m_pPrevNode;

public:
	C_NODE();
	int getData();
	C_NODE* getNextNode();
};

연결리스트에서 노드를 구성하는 Node class입니다. LinkedList를 friend로 선언하고 있는데, 이는 LinkedList Class에서 Node Class의 private 멤버에 직접 접근을 허용하기 위해서 선언했습니다. Private 멤버로 data 부분인 int형 m_nData와 다음 노드와 이전 노드를 가리키는 C_NODE* 변수 m_pNextNode와 m_pPrevNode를 가지고 있습니다. 멤버 함수로 초기화를 위한 생성자와 data를 반환하는 getData() 함수, 다음 노드의 포인터를 반환하는 getNextNode() 함수를 가지고 있습니다.
멤버 함수의 구현은 다음과 같습니다.

C_NODE::C_NODE() : 
	m_nData(0),
	m_pNextNode(nullptr),
	m_pPrevNode(nullptr)
{
}

int C_NODE::getData()
{
	return m_nData;
}

C_NODE * C_NODE::getNextNode()
{
	return m_pNextNode;
}

 

 

LinKedList Class

#include "node.h"

class C_LINKEDLIST
{
private:
	C_NODE * m_pBeginNode;
	C_NODE * m_pEndNode;
	C_NODE m_cDummyBegin;
	C_NODE m_cDummyEnd;

public:
	C_LINKEDLIST();
	void init();
	void clear();
	bool empty();
	C_NODE* getBegin();
	C_NODE* getEnd();
	void pushBack(int nData);
	void pushFront(int nData);
	bool popBack();
	bool popFront();
	bool erase(C_NODE* pDeleteNode);
};

LinkedList Class의 모습입니다. private멤버로 처음과 끝을 가리키는 C_NODE* 형 m_pBeginNode와 _pEndNode를 가지고 있고, 이 포인터 변수가 가리키는 Dummy인 m_cDummyBegin과 m_cDummyEnd로 구성하고 있는데, 이를 통해 실제 연결 리스트에서 맨 앞과 맨 뒤 노드는 데이터를 가지고 있지 않는 Dummy노드로 구성합니다. 저는 Begin과 End를 싱글 포인터로 구성했기 때문에 이런 Dummy를 두고 있습니다. 만약 이런 Dummy가 싫다고 하신다면 더블 포인터를 사용하시면 될 겁니다.(마?)
LinkedList의 멤버 함수의 구현은 다음과 같습니다.

C_LINKEDLIST::C_LINKEDLIST() :
	m_pBeginNode(nullptr),
	m_pEndNode(nullptr),
	m_cDummyBegin(),
	m_cDummyEnd()
{
}

멤버 변수들을 단순히 초기화해 주기 위한 생성자입니다.

void C_LINKEDLIST::init()
{
	m_pBeginNode = &m_cDummyBegin;
	m_pEndNode = &m_cDummyEnd;

	m_pBeginNode->m_pNextNode = m_pEndNode;
	m_pEndNode->m_pPrevNode = m_pBeginNode;
}

Begin과 End를 각각 Dummy에 연결시키고 Begin과 End를 서로 가리키도록 하는 init() 함수입니다.

LinkedList Class를 사용할 때 init() 함수를 먼저 호출해야 연결 리스트를 구성할 수 있습니다.

void C_LINKEDLIST::clear()
{
	while (!empty()) {
		popBack();
	}
}

연결리스트에 남아있는 노드를 모두 삭제하는 clear() 함수입니다.

 

bool C_LINKEDLIST::empty()
{
	if(getBegin() != getEnd())
		return false;
	return true;
}

연결리스트에 노드가 있는지를 확인하는 empty() 함수입니다.

노드가 있다면 false, 없다면 true를 반환합니다.

C_NODE * C_LINKEDLIST::getBegin()
{
	return m_pBeginNode->m_pNextNode;
}

C_NODE * C_LINKEDLIST::getEnd()
{
	return m_pEndNode;
}

연결리스트의 Begin과 End를 반환하는 함수입니다. getBegin() 함수의 경우 Begin의 다음 노드를 반환하는데 이유는 이 연결리스트가 Begin위치에서 End위치로 순차적으로 탐색하는 연결리스트이기 때문입니다.

 

void C_LINKEDLIST::pushBack(int nData)
{
	C_NODE* pNewNode = nullptr;
	pNewNode = new C_NODE();
	pNewNode->m_nData = nData;

	pNewNode->m_pNextNode = m_pEndNode;
	pNewNode->m_pPrevNode = m_pEndNode->m_pPrevNode;
	m_pEndNode->m_pPrevNode->m_pNextNode = pNewNode;
	m_pEndNode->m_pPrevNode = pNewNode;
}

void C_LINKEDLIST::pushFront(int nData)
{
	C_NODE* pNewNode = nullptr;
	pNewNode = new C_NODE();
	pNewNode->m_nData = nData;

	pNewNode->m_pPrevNode = m_pBeginNode;
	pNewNode->m_pNextNode = m_pBeginNode->m_pNextNode;
	m_pBeginNode->m_pNextNode->m_pPrevNode = pNewNode;
	m_pBeginNode->m_pNextNode = pNewNode;
}

연결리스트의 마지막과 처음에 노드를 추가하는 pushFront() 함수와 pushBack() 함수입니다.

 

bool C_LINKEDLIST::popBack()
{
	if (empty())
		return false;

	C_NODE* pDeleteNode = nullptr;
	pDeleteNode = m_pEndNode->m_pPrevNode;

	pDeleteNode->m_pPrevNode->m_pNextNode = m_pEndNode;
	m_pEndNode->m_pPrevNode = pDeleteNode->m_pPrevNode;

	delete pDeleteNode;
	return true;
}

bool C_LINKEDLIST::popFront()
{
	if (empty())
		return false;

	C_NODE* pDeleteNode = nullptr;
	pDeleteNode = getBegin();

	pDeleteNode->m_pNextNode->m_pPrevNode = m_pBeginNode;
	m_pBeginNode->m_pNextNode = pDeleteNode->m_pNextNode;

	delete pDeleteNode;
	return true;
}

연결리스트의 마지막과 처음 위치의 노드를 삭제하는 popBack() 함수와 popFront() 함수입니다.

삭제 함수의 경우 반환형이 bool인데 연결리스트에 노드가 없는 경우에 false를 반환하여 삭제할 노드가 없음을 알리기 위함입니다.

bool C_LINKEDLIST::erase(C_NODE * pDeleteNode)
{
	if (empty())
		return false;

	pDeleteNode->m_pPrevNode->m_pNextNode = pDeleteNode->m_pNextNode;
	pDeleteNode->m_pNextNode->m_pPrevNode = pDeleteNode->m_pPrevNode;

	delete pDeleteNode;
	return false;
}

마지막으로 인자로 받은 특정 노드를 연결리스트에서 삭제하는 erase() 함수입니다.