[C++] Double Linked List

※ 무엇인가

 

기존의 Linked List의 노드에 앞의 노드의 주소를 저장하는 포인터 변수가 추가 되었다.

그로 하여금, 앞 뒤 모든 방향으로 전체 무한 순환이 가능하다.

O(N) = N

O(N) => 최악의 상황에서 입력 대비 얼마나 걸리는지 나타냄(상수는 무시 ex log₂N 에서 2)

<DLinkedList.h>

#pragma once

#include <iostream>
using namespace std;

typedef int DataType;

struct Node
{
	DataType Data;
	Node* PrevNode;
	Node* NextNode;
};

Node* Create(DataType data);
void Destroy(Node** node);

void Push(Node** head, Node* node);
void insert(Node* current, Node* node);
void insertHead(Node** current, Node* head);

void Remove(Node** head, Node* remove);
Node* GetNode(Node* head, int location);
int GetNodeCount(Node* head);

 

<DLinkedList.cpp>

#include <iostream>
#include "DLinkedList.h"
using namespace std;

/*
최적화 잘된 코드: 컴파일러가 실행하기 쉬운코드 >> 유지보수 ㅈㄴ 힘들어짐
중단점에 조건식 걸 수 있음
*/

Node* Create(DataType data)
{
	Node* node = new Node();

	node->Data = data;
	node->PrevNode = NULL;
	node->NextNode = NULL;

	return node;
}

void Destroy(Node** node)
{
	delete *node;
	*node = NULL;
}

void Push(Node** head, Node* node)
{
	if ((*head) != NULL)
	{
		Node* tail = (*head);

		while (tail->NextNode != NULL)
			tail = tail->NextNode;

		tail->NextNode = node;
		node->PrevNode = tail;
	}
	else
	{
		*head = new Node();
	}
}

void insert(Node * current, Node * node)
{
	node->NextNode = current->NextNode;
	node->PrevNode = current;

	if (current->NextNode != NULL)
		current->NextNode->PrevNode = node;

	current->NextNode = node;
}

void insertHead(Node ** current, Node * head)
{
	if (current == NULL) {
		*current = head;
	}
	else
	{
		head->NextNode = *current;
		*current = head;
	}
}

Node * GetNode(Node * head, int index)
{
	Node* current = head;

	while (current != NULL && (--index >= 0))
	{
		current = current->NextNode;
	}

	return current;
}



int GetNodeCount(Node * head)
{
	int count = 0;
	Node* current = head;

	while (current != NULL)
	{
		current = current->NextNode;
		count++;
	}


	return count;
}



void Remove(Node ** head, Node * remove)
{
	if (*head == remove)
	{
		*head = remove->NextNode;
		if (*head != NULL)
			(*head)->PrevNode = NULL;

		remove->PrevNode = NULL;
		remove->NextNode = NULL;
	}
	else
	{
		Node* current = *head;
		remove->PrevNode->NextNode = current->NextNode;

		if (remove->NextNode != NULL)
			remove->NextNode->PrevNode = current->PrevNode;

		remove->PrevNode = NULL;
		remove->NextNode = NULL;
	}
	
}

 

<Main.cpp>

 

#include <iostream>
#include "DLinkedList.h"
using namespace std;

int main()
{
	Node* node = NULL;
	for (int i = 0; i < 5; i++)
	{
		Node* temp = Create(i);
		Push(&node, temp);
	}


	//시작부분에 삽입
	Node* newNode = NULL;
	{
		newNode = Create(-1);
		insertHead(&node, newNode);

		newNode = Create(-2);
		insertHead(&node, newNode);
	}

	int a = 0;

	//Print
	{
		Node* current = GetNode(node, 2);
		newNode = Create(1000);

		insert(current, newNode);

		int count = GetNodeCount(node);

		for (int i = 0; i < count; i++)
		{
			Node* current = GetNode(node, i);
			cout << "List[" << i << "} :" << current->Data << endl;
		}
		cout << "-----------------------------------" << endl << endl;
	}

	//Remove
	{
		Node* remove = GetNode(node, 3);
		Remove(&node, remove);

		int count = GetNodeCount(node);
		for (int i = 0; i < count; i++)
		{
			Node* current = GetNode(node, i);
			cout << "List[" << i << "} :" << current->Data << endl;
		}
		cout << "-----------------------------------" << endl << endl;
	}

	//Remove All
	{
		int count = GetNodeCount(node);
		
		for (int i = 0; i < count; i++)
		{
			Node* current = GetNode(node, 0);

			if (current != NULL)
			{
				Remove(&node, current);
				Destroy(&current);
				int a = 0;
			}
		}

		int a = 0;
	}

	return 0;
}