double linked list 구현

싱글 링크드 리스트와는 다르게 노드가 이전 노드와 이후 노드를 둘 다 가르기코 있음!.!

특이하게도 처음 생성자에서 head와 tail이 아무런 값을 가지고 있지 않은 더미 노드를 가르키게 만들어 준당

더블 링크드 리스트에선 특정 위치의 노드를 삭제하거나 삽입 할 때 노드들을 연결해주는 linkNodes를 구현했다 :)

 

template <typename T>
class doubleLinkedList
{
public:
	// push back element!
	void push_back(T element)
	{
		node<T>* newNode = new node<T>(element);

		linkNodes(tail, newNode);

		++size;
	}

	// find element at selected index
	node<T>* findNode(int findIndex)
	{
		node<T>* ptr = head->next;

		for (int index = 0; index < size; ++index)
		{
			if (index == findIndex)
			{
				return ptr;
			}

			ptr = ptr->next;
		}

		return nullptr;
	}

	// insert element at selected index
	void insertNode(T element, int insertIndex)
	{
		if (size < insertIndex || insertIndex < 0)
		{
			cout << "Can't insert index :(!" << endl;
			return;
		}

		node<T>* newNode = new node<T>(element);
		node<T>* nextNode = findNode(insertIndex);

		linkNodes(nextNode, newNode);

		++size;
	}

	// delete element at selected index
	void deleteNode(int insertIndex)
	{
		if (size < insertIndex || insertIndex < 0)
		{
			cout << "Can't delete index :(!" << endl;
			return;
		}

		node<T>* nextNode = findNode(insertIndex + 1);
		node<T>* deleteNode = nextNode->prev;

		linkNodes(nextNode, deleteNode->prev);
		delete deleteNode;

		--size;
	}
	
    // link nodes
	void linkNodes(node<T>* nextNode, node<T>* newNode)
	{
		nextNode->prev->next = newNode;
		newNode->prev = nextNode->prev;
		newNode->next = nextNode;
		nextNode->prev = newNode;
	}

	// return size of container
	int Size(void) const
	{
		return size;
	}

	// delete all nodes in container
	void Clear(void)
	{
		node<T>* tempPtr = head->next;
		node<T>* deletePtr = head->next;

		for (int index = 0; index < size; ++index)
		{
			tempPtr = deletePtr->next;
			delete deletePtr;
			deletePtr = tempPtr;
		}

		delete head;
		delete tail;

		size = 0;
	}

private:
	node<T>* head;
	node<T>* tail;
	int size;

public:
	doubleLinkedList() : size(0), head(nullptr), tail(nullptr) 
	{
		head = new node<T>();
		tail = new node<T>();
		head->next = tail;
		tail->prev = head;
	};

	~doubleLinkedList() {};
};