자료구조...20

데이터 삽입 메서드 구현

데이터 삽입 연산에 필요한 메서드들을 구현한다.

 

DoublyLinkedList.cpp

/// <summary>
/// SinglyLinkedList의 시작 위치에 지정한 값이 포함된 새 노드를 추가한다.
/// </summary>
/// <param name="value">추가할 값</param>
void DoublyLinkedList::AddFirst(int value)
{
	DoublyLinkedListNode* newNode{ PopNode(value) };
	AddFirst(newNode);
}

/// <summary>
/// SinglyLinkedList의 시작 위치에 지정한 노드를 추가한다.
/// </summary>
/// <param name="node">추가할 새 노드</param>
void DoublyLinkedList::AddFirst(DoublyLinkedListNode* node)
{
	if (node == nullptr || node->m_prev != nullptr || node->m_next != nullptr)
	{
		throw std::invalid_argument("node");
	}

	node->m_next = m_head;
	if (m_head != nullptr)
	{
		m_head->m_prev = node;
		m_head = node;
	}
	else
	{
		m_head = m_tail = node;
	}

	m_count++;
}

/// <summary>
/// SinglyLinkedList의 끝 위치에 지정한 값이 포함된 새 노드를 추가한다.
/// </summary>
/// <param name="value">추가할 값</param>
void DoublyLinkedList::AddLast(int value)
{
	DoublyLinkedListNode* newNode{ PopNode(value) };
	AddLast(newNode);
}

/// <summary>
/// SinglyLinkedList의 끝 위치에 지정한 노드를 추가한다.
/// </summary>
/// <param name="node">추가할 새 노드</param>
void DoublyLinkedList::AddLast(DoublyLinkedListNode* node)
{
	if (node == nullptr || node->m_prev != nullptr || node->m_next != nullptr)
	{
		throw std::invalid_argument("node");
	}

	node->m_prev = m_tail;
	if (m_tail != nullptr)
	{
		m_tail->m_next = node;
		m_tail = node;
	}
	else
	{
		m_head = m_tail = node;
	}

	m_count++;
}

/// <summary>
/// DoublyLinkedList의 지정한 인덱스에 해당하는 위치에 지정한 값이 포함된 새 노드를 추가한다.
/// </summary>
/// <param name="index">값을 추가할 인덱스</param>
/// <param name="value">추가할 값</param>
void DoublyLinkedList::Insert(int index, int value)
{
	DoublyLinkedListNode* newNode{ PopNode(value) };
	Insert(index, newNode);
}

/// <summary>
/// DoublyLinkedList의 지정한 인덱스에 해당하는 위치에 지정된 노드를 추가한다.
/// </summary>
/// <param name="index">새 노드를 추가할 인덱스</param>
/// <param name="node">추가할 새 노드</param>
void DoublyLinkedList::Insert(int index, DoublyLinkedListNode* node)
{
	if (index < 0)
	{
		throw std::out_of_range("index");
	}

	if (node == nullptr || node->m_next != nullptr)
	{
		throw std::invalid_argument("node");
	}

	if (index > m_count)
	{
		index = m_count;
	}

	DoublyLinkedListNode* curNode{ m_head };
	while (index--)
	{
		curNode = curNode->m_next;
	}

	DoublyLinkedListNode* prevNode{ curNode != nullptr ? curNode->m_prev : nullptr };
	node->m_prev = prevNode;
	if (prevNode != nullptr)
	{
		prevNode->m_next = node;
	}
	node->m_next = curNode;
	if (curNode != nullptr)
	{
		curNode->m_prev = node;
	}

	if (node->m_prev == nullptr)
	{
		m_head = node;
	}
	if (node->m_next == nullptr)
	{
		m_tail = node;
	}

	m_count++;
}