[자료구조] 더블 링크드 리스트(Doubly Linked List) (C++)

개념

링크드 리스트의 탐색 기능을 개선한 자료구조이다. 양방향으로 탐색이 가능하다.

 

코드 자체는 링크드 리스트와 크게 다른 게 없다. 삽입, 삭제 시 양방향인 것만 신경 쓰면 된다.

template<typename T>
struct Node
{
	T data;			// 데이터
	Node<T>* prevNode;	// 이전 노드를 가리키는 포인터
	Node<T>* nextNode;	// 다음 노드를 가리키는 포인터

	Node<T>(T value) : data(value), prevNode(NULL), nextNode(NULL) {}
};

template<typename T>
class DoublyLinkedList
{
	Node<T>* head;
	Node<T>* tail;
	int size = 0;

public:
	DoublyLinkedList() : head(NULL), tail(NULL) {}
	~DoublyLinkedList()
	{
		Node<T>* deleteNode;
		while (head->nextNode != NULL)
		{
			deleteNode = head;
			head = head->nextNode;
			delete deleteNode;
		}
	}
	// ...
}

 

 

노드 추가

void addNode(T data)
{
	Node<T>* newNode = new Node<T>(data);
	++size;

	// head가 NULL이라면 현재 Linked List는 비어 있는 상태
	if (head == NULL)
	{
		head = tail = newNode;
		return;
	}
    
	tail->nextNode = newNode;
	newNode->prevNode = tail;
	tail = newNode;
}

 

 

노드 탐색

void showList() const
{
	Node<T>* findNode = head;

	cout << "size of DLL: " << size << endl;

	while (findNode != NULL)
	{
		cout << findNode->data << " ";
		findNode = findNode->nextNode;
	}
	cout << endl;
}

Node<T>* findNode(int location) const
{
	Node<T>* searchNode = head;
	int index = location;

	while (searchNode != NULL && --index >= 0)
	{
		searchNode = searchNode->nextNode;
	}

	return searchNode;
}

T findNodeData(int location) const
{
	Node<T>* searchNode = head;
	int index = location;

	while (searchNode != NULL && --index >= 0)
	{
		searchNode = searchNode->nextNode;
	}

	return searchNode->data;
}

귀찮아서 스킵했지만(...) findNode처럼 index로 접근하는 경우, 리스트 사이즈의 절반보다 큰지, 작은지를 체크해서 분기를 나눠서 처리하면 DLL의 개선점을 활용하는 코드가 될 것 같다.

 

 

노드 삭제

void removeNode(T data)
{
	// 삭제될 Node를 가리키는 포인터
	Node<T>* deleteNode = head;

	while (deleteNode != NULL)
	{
		if (deleteNode->data == data)
			break;
		deleteNode = deleteNode->nextNode;
	}

	// nullptr이면 해당 데이터를 찾지 못함
	if (deleteNode != NULL)
	{
		if (deleteNode->prevNode != NULL)
			deleteNode->prevNode->nextNode = deleteNode->nextNode;
		if (deleteNode->nextNode != NULL)
			deleteNode->nextNode->prevNode = deleteNode->prevNode;
		--size;

		delete deleteNode;
	}
}

 

 

노드 삽입

void insertNode(T data, int index)
{
	// index가 DLL 사이즈보다 크거나 음수인 경우 예외 처리
	if (index > size || index < 0)
	{
		cout << "invalid index : " << index << endl;
		return;
	}

	Node<T>* newNode = new Node<T>(data);

	// head에 추가
	if (index == 0)
	{
		// 만약 비어 있다면
		if (head == NULL)
			tail = newNode;

		head->prevNode = newNode;
		newNode->nextNode = head;
		head = newNode;
	}
	// tail에 추가
	else if (index == size)
	{
		// 만약 비어 있다면
		if (head == NULL)
			head = tail = newNode;
		else
		{
			newNode->prevNode = tail;
			tail->nextNode = newNode;
			tail = newNode;
		}
	}
	else
	{
		Node<T>* findNode = head;

		for (int i = 1; i < index; ++i)
		{
			findNode = findNode->nextNode;
		}

		newNode->nextNode = findNode->nextNode;
		newNode->prevNode = findNode;
		findNode->nextNode = newNode;
	}

	++size;
}