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

더블 링크드 리스트(Double Linked List)

 

더블 링크드 리스트란?

• 노드를 연결해서 만든 리스트다.
• 데이터와 포인터를 이용하여 노드를 만들고 이것을 기차처럼 연결시켜준다.
• 머리(헤드)와 꼬리(테일)을 가지고있다.
• 싱글 링크드 리스트 보다 이전노드를 가지고있어야 하기때문에 메모리를 더 차지하게된다.
• 싱글리스트는 한쪽으로만 탐색이 가능하지만 더블 링크트 리스트는 양쪽에서 탐색이 가능하게 된다.

 

싱글 링크드 리스트 구현

• 노드 추가
• 노드 탐색
• 노드 삭제
• 노드 삽입

노드 추가

테일 뒤쪽에 노드를 추가하는 그림이다.

싱글 링크드 리스트의 경우 이전 노드를 알 수가 없어 노드를 추가할땐 무조건 끝까지 탐색 후 넣어줘야 했지만

더블 링크드 리스트의 경우 이전 노드를 알 수 있어 단순히 테일의 이전노드를 참조하여 간단히 추가 할 수 있다.

void LinkedList::Add(const int& NewData)
{
	Node* NewNode = new Node();

	if (NewNode != nullptr)
	{
		NewNode->Data = NewData;
	}
	if (Tail != nullptr)
	{
		NewNode->Prev = Tail->Prev;
		NewNode->Next = Tail;
		Tail->Prev->Next = NewNode;
		Tail->Prev = NewNode;
	}
}

노드 탐색

테일 전까지의 노드를 순회하면서 같은 데이터를 찾아야한다.

싱글 링크트 리스트와 코드차이는 없다. 다만 뒤에서 탐색하는걸 조건에 넣어 만들면 양방향 탐색이 가능해진다.

Node* LinkedList::Search(const int& Data)
{
	Node* CurrentNode = Head;

	if (CurrentNode != nullptr)
	{
		while (CurrentNode->Next != Tail)
		{
			if (CurrentNode->Next->Data == Data)
			{
				return CurrentNode->Next;
			}

			CurrentNode = CurrentNode->Next;
		}
		std::cout << "검색 할 노드가 없습니다" << std::endl;
		return nullptr;
	}
	else
	{
		std::cout << "헤드가 없습니다" << std::endl;
		return nullptr;
	}
}

 

노드 삽입

헤드의 다음노드를 첫번째 노드라고 생각하고 첫 번째 노드와 두 번째 노드사이에 새로운 노드를 넣는다.

그림에선 첫 번째 뒤에 삽입 하기 위해 1이라는 인덱스를 필요로 한다.

 

void LinkedList::Insert(const int& NewData, const int& Index)
{
	Node* CurrentNode = Head;

	if (CurrentNode != nullptr)
	{
		for (int i = 0; i < Index; ++i)
		{
			if (CurrentNode != nullptr)
			{
				CurrentNode = CurrentNode->Next;
			}
			else
			{
				std::cout << Index << "번째의 노드가 없습니다" << std::endl;
				return;
			}
		}
	}

	if (CurrentNode == nullptr)
	{
		std::cout << Index << "번째의 노드가 없습니다" << std::endl;
		return;
	}

	Node* NewNode = new Node();
	if (NewNode != nullptr)
	{
		NewNode->Data = NewData;

		CurrentNode->Next->Prev = NewNode;
		NewNode->Next = CurrentNode->Next;
		NewNode->Prev = CurrentNode;
		CurrentNode->Next = NewNode;
	}
}

노드 제거

테일 전까지 노드를 순회하면서 같은 데이터를 찾고 그 데이터가 있으면 제거를 할 수 있다.

void LinkedList::Remove(Node* InRemoveNode)
{
	Node* CurrentNode = Head->Next;
	if (CurrentNode != nullptr && InRemoveNode != nullptr)
	{
		if (CurrentNode == InRemoveNode)
		{
			Head->Next = InRemoveNode->Next;
			InRemoveNode->Next->Prev = Head;
		}
		else
		{
			InRemoveNode->Prev->Next = InRemoveNode->Next;
			InRemoveNode->Next->Prev = InRemoveNode->Prev;
		}
		delete InRemoveNode;
	}
}

메인 코드

int main()
{
	LinkedList* List = new LinkedList();

	if (List != nullptr)
	{
		List->Add(5);
		List->Add(9);
		List->Add(7);
		List->Insert(3, 1);
		std::cout << "==제거 하기전 출력==" << std::endl;
		List->Show();
		Node* RemoveNode = List->Search(9);
		if (RemoveNode != nullptr)
		{
			List->Remove(RemoveNode);
		}
		std::cout << "==제거 후 출력==" << std::endl;
		List->Show();
	}
}

Add함수를 통해 5,9,7을 추가 해주고

Insert함수를 통해 3의 데이터를 1번째에 삽입시켜주면 5,3,9,7이 출력되며

Search함수로 9의 데이터를 찾은 후 제거해준다

그럼 5,3,7 이 출력된다.