[Data Structure] C++로 구현한 더블 링크드 리스트

더블 링크드 리스트 - 앞쪽삽입 / 끝쪽삽입 / 특정값 삭제 # 기능 구현

#pragma once
#include <iostream>
// Node Class
class Node {
	friend class LinkedList; // LinkedList가 Node의 멤버 변수에 접근 허용

private:
	int data;
	Node* next;
	Node* prev; // Double LinkedList에 추가된 멤버 변수

public:
	Node(int data) : data(data), next(nullptr), prev(nullptr) {}
};

//
class LinkedList {
private:
	Node* head; // 첫번째 노드
	Node* tail; // 마지막 노드

public:
	LinkedList() :head(nullptr), tail(nullptr) {}
	~LinkedList(); // 메모리 관리를 위해

	// func
	bool isEmpty();
	void InsertFront(int val);
	void InsertBack(int val);
	void DeleteNode(int val);
	void Display() const;
};

LinkedList::~LinkedList() {
	Node* curr = head;
	while (curr) {
		Node* tmp = curr->next; // 이렇듯 Node 변수에 접근하려면 friend 선언이 되어있어야 한다.
		delete curr;
		curr = tmp;
	}
}

void LinkedList::InsertFront(int val) {
	Node* newNode = new Node(val);
	// newNode->next = head;
	if(isEmpty()){
		tail = newNode;
	}
	else{
		newNode->next = head;
		head->prev = newNode;
	}
	head = newNode;
}

void LinkedList::InsertBack(int val) {
	Node* newNode = new Node(val);
	// newNode->prev = tail;
	if(isEmpty()){
		head = newNode;
	}
	else{
		newNode->prev = tail;
		tail->next = newNode;
	}
	tail = newNode;
}

void LinkedList::DeleteNode(int val) {
	Node* curr = head;
	while (curr) {
		if (curr->data == val) {
			if (curr->prev) {
				curr->prev->next = curr->next;
			} // prev가 없다는건 현재 node가 head임
			else {
				head = curr->next;
				if (head) {
					head->prev = nullptr;
				}
			}

			if (curr->next) {
				curr->next->prev = curr->prev; 
			}
			else {
				tail = curr->prev;	
				if (tail) {
					tail->prev = nullptr;
				}
			}

			Node* tmp = curr->next;
			delete curr;
			curr = tmp;
		}
		else{curr = curr->next;}
	}
}

void LinkedList::Display() const {
	Node* curr = head;
	while (curr) {
		std::cout << curr->data << " ";
		curr = curr->next;
	}
	std::cout << "\n";
}

int main() {
	std::ios::sync_with_stdio(false);
	LinkedList linkedList = LinkedList();

	linkedList.InsertFront(1);
	linkedList.InsertFront(2);
	linkedList.InsertFront(3);
	linkedList.InsertBack(4);

	linkedList.Display();

	linkedList.DeleteNode(2);

	linkedList.Display();

	return 0;
}

deleteNode()를 경우의 수로 분기하여 구현

void deleteNode(int val) {
	Node* curr = head;
	while (curr) {
		if (curr->data == val) {
			// 여기서부터 다름
			if (head == tail) {
				head = nullptr;
				tail = nullptr;
			}
			else if (curr == head) {
				head = curr->next;
				curr->next->prev = curr->prev;
			}
			else if (curr == tail) {
				tail = curr->prev;
				curr->prev->next = curr->next;
			}
			else {
				curr->prev->next = curr->next;
				curr->next->prev = curr->prev;
			}
			Node* tmp = curr->next;
			delete curr;
			curr = tmp;
			continue;
		}
		curr = curr->next;
	}
}

deleteNode()에서 해당하는 값의 모든 노드를 지우려면,

void DoubleLinkedList::deleteNode(int val) {
	Node* curr = head;
	while (curr) {
		if (curr->data == val) {
			if (curr->next) {
				curr->next->prev = curr->prev;
			}
			else {
				tail = curr->prev;
				tail->next = nullptr;
			}
			
			if (curr->prev) {
				curr->prev->next = curr->next;
			}
			else {
				head = curr->next;
				head->prev = nullptr;
			}
			/// 현재 노드를 삭제하고 넘어가자
			Node* tmp = curr->next;
			delete curr;
			curr = tmp;
		}
		else{curr = curr->next;}
	}
}