[알고리즘/C++] - 링크드리스트안에 더블링크드리스트 더블 링크드리스트 안에 더블..더블링크드리스트,,(DoubleLInkedList)

오늘은 제가 좋아하는 옛날 아이스크림을 가져와봤습니다.

항상 생각하지만 귀멸의 칼날의 어떤 캐릭터도 이 더블더블이랑 비슷하다고 생각합니다.

아니면 말고요..

 

이전 포스팅에서 말하였듯이 연결리스트에서의 다른 구현방법인 더블 링크드 리스트에 대해서 알아보도록 하겠습니다.

더블 링크드 리스트는 연결 리스트 개념 안에 존재하는 세부 개념입니다.

 

다만, 이전에 설명했던 단일 연결리스트와는 다르게 이름대로 데이터가 서로 이중 연결을 합니다.

2번데이터는 이전데이터(1번)를 가리키는 주소값, 다음데이터(3번)을 가리키는 주소값, 그리고 자시자신 값. 총 세가지 값을 가집니다.이렇게 모든 데이터가 각각 세개의 데이터를 가지며, 이전데이터가 NULL인 경우에는 그 데이터는 첫번째 헤드. 다음 데이터가 NULL인 경우에는 그 데이터가 꼬리 데이터라는 걸 나타냅니다.

이 연결리스트는 단일 연결리스트보다 손상에 강합니다. 첫번째 데이터, 끝 데이터들이 하나 없어진다고 해도 연결점이 한 줄 남아있기 때문에 복구가 가능합니다. 

하지만 데이터를 참조하고 탐색하는 방법은 기존의 연결리스트와 같은 방식을 사용하기 때문에 O(n)의 시간복잡도를 요구합니다.

 

아래는 직접 구현해 본 더블 링크드 리스트입니다. 

#include <iostream>

using namespace std;

template <typename T>
struct DoubleLinkedList
{
	struct Node
	{
		T data;
		Node* Prev = nullptr;
		Node* Next = nullptr;
	};

	struct Iterator //iterator 구조체 생성
	{
		Node* pCurr = nullptr; //현재 노드.

		Iterator(Node* p = nullptr) {//현재 노드를 변경시킵니다. 만약 가져오는 값이 없다면 null 로 초기화합니다.
			pCurr = p;
		}
		Iterator& operator++() { //다음값을 노드의 Nect 에 저장하고, 현재값을 반환합니다. 
			pCurr = pCurr->Next;
			return *this;
		}
		T& operator*() { //현재 노드의 값을 가져옵니다.
			return pCurr->data;
		}
		bool operator==(const Iterator& ref) {  //현재값과 가져온 값이 같은지 비교합니다.
			return  pCurr == ref.pCurr;
		}
		bool operator!=(const Iterator& ref) {//현재값과 가져온 값이 같지 않은지 비교합니다.
			return  pCurr != ref.pCurr;
		}
	};

	Node* m_pHead = nullptr; //머리
	Node* m_pTail = nullptr; //꼬랑지
	Iterator Begin() {
		return Iterator(m_pHead);
	}
	Iterator End() {
		return Iterator(nullptr);
	}

	Node* Insert(Node* pPos, T data) {// pos노드 다음에 Data로 추가하고 노드를 리턴
		Node* newNode = new Node;
		newNode->data = data;
		if (IsEmpty()) { //비어있는 경우의 헤드테일 설정
			m_pHead = newNode;
			m_pTail = newNode;
		}
		else {
			newNode->Next = pPos->Next; //연결
			newNode->Prev = pPos;
			if (pPos->Next != nullptr) newNode->Next->Prev = newNode;
			pPos->Next = newNode;
			if (newNode->Next == nullptr) m_pTail = newNode; //헤드테일설정
			if (newNode->Prev == nullptr) m_pHead = newNode;
		}
		return newNode;
	}
	Node* PushBack(T data) {
		return Insert(m_pTail, data);
	}
	Node* Erase(Node* pPos) { // 노드를 지우고 다음 노드 리턴
		if (IsEmpty())return nullptr; //예외처리

		if (pPos->Prev != nullptr)pPos->Prev->Next = pPos->Next; //지우고 서로 연결하기
		if (pPos->Next != nullptr)pPos->Next->Prev = pPos->Prev;
		if (pPos->Next->Next == nullptr) m_pTail = pPos->Next;//head, tail변경
		if (pPos->Next->Prev == nullptr) m_pHead = pPos->Next;
		return pPos->Next;
	}

	bool IsEmpty() {
		if (m_pHead == nullptr && m_pTail == nullptr)	return true;
		else	return false;
	}
};

int main() {
	DoubleLinkedList<int> MyList;
	MyList.PushBack(10);
	DoubleLinkedList<int>::Node* node = MyList.PushBack(20);
	MyList.PushBack(30);
	MyList.PushBack(40);   // 추가 테스트
	MyList.Erase(node);    // 삭제 테스트
	DoubleLinkedList<int>::Iterator iter = MyList.Begin();
	for (; iter != MyList.End(); ++iter)
		std::cout << *iter << std::endl;

	return 0;
}

 

https://www.acmicpc.net/problem/3045

3045번: 이중 연결 리스트

이중 연결 리스트는 태그별 문제가 없어 그냥 문제 하나를 가져왔습니다. 

아마 전 포스팅인 연결리스트에 포함되는 개념이기에 한꺼번에 태그로 묶인 것 같습니다.

응용하는 문제를 더 풀어보고자 한다면 연결리스트 태그의 문제들을 잘 살펴보고 풀어보시면 좋을 것 같습니다.

 

이해에 도움이 되길 바랍니다!

 

그럼 오늘도 안 뇽

반응형