양방향 연결 리스트 (Doubly Linked List)

양방향 연결 리스트란?

데이터를 가지고 있는 노드가 이전 노드와 다음 노드의 주소를 가지고 있는 리스트이다.

양방향 연결리스트의 특징

단방향 연결리스트는 이전 노드로 돌아가려면 저장을 해둬야했던 반면에,

양방향은 자유롭게 노드 이동이 가능하다.

 

그 대신에 이전 노드를 저장하는 변수가 하나 더 추가된다.

 

상황에 따라 사용하면 된다.

 

탐색이 빠르다고 하는 게시글도 몇몇 있는데, 정렬된 리스트가 아니면 의미 없기에 특징으로 적지 않겠다.

 

양방향 연결리스트 구현 (그림 설명)

2021/01/15 - [프로그래밍/자료구조 & 알고리즘] - 연결 리스트 (Linked List)

연결 리스트 (Linked List)

여기에서 이전 노드를 가리키는 주소만 추가된 것이기 때문에, 따로 그림은 그리지 않겠다.

 

양방향 연결리스트 구현 (C++) 

DLinkedList.h

#pragma once
#include <assert.h>

template <typename T>
class DListNode
{
	template<typename T>
	friend class DLinkedList;
private:
	DListNode() :
		mData{}
	{
		mPrev = nullptr;
		mNext = nullptr;
	}
	~DListNode()
	{

	}
private:
	T mData;
	DListNode<T>* mPrev;
	DListNode<T>* mNext;
};

/*
* Add_Front(T Data);
* Add_End(T Data);
* Remove_Front();
* Remove_End();
* 
* Clear();
* GetValueAt(int Index);
*/

template <typename T>
class DLinkedList
{
public :
	DLinkedList()
	{
		// 시작 노드와 마지막 노드를 더미로 미리 생성.
		mBegin = new DListNode<T>();
		mEnd = new DListNode<T>();
		mSize = 0;

		mBegin->mNext = mEnd;
		mEnd->mPrev = mBegin;
	}
	~DLinkedList()
	{
		Clear();
		delete mBegin;
		delete mEnd;
	}
private:
	DListNode<T>* mBegin;
	DListNode<T>* mEnd;
	int mSize = 0;

public:
	int Size()
	{
		return mSize;
	}
	bool IsEmpty()
	{
		return mSize == 0;
	}
	void Add_Front(T Data)
	{
		// 입력받은 데이터를 가지는 노드 생성
		DListNode<T>* NewNode = new DListNode<T>();
		NewNode->mData = Data;
		
		// 기존의 첫번째 노드 받아와서, 새로 만든 노드와 연결
		DListNode<T>* FirstNode = mBegin->mNext;
		NewNode->mNext = FirstNode;
		FirstNode->mPrev = NewNode;

		// 새로 만든 노드를 시작 노드로 설정
		mBegin->mNext = NewNode;
		NewNode->mPrev = mBegin;
		mSize++;
	}
	void Add_End(T Data)
	{
		// 입력받은 데이터를 가지는 노드 생성
		DListNode<T>* NewNode = new DListNode<T>();
		NewNode->mData = Data;

		// 기존의 마지막 노드 받아와서, 새로 만든 노드와 연결
		DListNode<T>* LastNode = mEnd->mPrev;
		NewNode->mPrev = LastNode;
		LastNode->mNext = NewNode;

		// 새로 만든 노드를 마지막 노드로 설정
		mEnd->mPrev = NewNode;
		NewNode->mNext = mEnd;
		mSize++;
	}
	void Remove_Front()
	{
		// 리스트가 비어있으면 실행 안함.
		assert(!IsEmpty());

		// 첫번째 노드를 삭제할 노드로 지정하고, 그 다음 노드 백업함.
		DListNode<T>* RemoveNode = mBegin->mNext;
		DListNode<T>* NextNode = RemoveNode->mNext;

		// 노드 삭제하고,
		delete RemoveNode;
		
		// 연결
		mBegin->mNext = NextNode;
		NextNode->mPrev = mBegin;

		mSize--;
	}
	void Remove_End()
	{
		// 리스트가 비어있으면 실행 안함.
		assert(!IsEmpty());

		// 마지막 노드를 삭제할 노드로 지정하고, 그 이전 노드 백업함.
		DListNode<T>* RemoveNode = mEnd->mPrev;
		DListNode<T>* PrevNode = RemoveNode->mPrev;

		// 노드 삭제하고,
		delete RemoveNode;

		// 연결
		mEnd->mPrev = PrevNode;
		PrevNode->mNext = mEnd;

		mSize--;
	}

	void Clear()
	{
		// 시작 노드부터 끝까지 삭제.
		DListNode<T>* CurrentNode = mBegin->mNext;
		while (CurrentNode != mEnd)
		{
			DListNode<T>* NextNode = CurrentNode->mNext;
			delete CurrentNode;
			CurrentNode = NextNode;
		}

		mSize = 0;

		// 시작 노드와 마지막 노드는 더미였으므로, 서로 연결시켜줌.
		mBegin->mNext = mEnd;
		mEnd->mPrev = mBegin;
	}

	T GetValueAt(int Index)
	{
		assert(Index < mSize);
		int mIndex = 0;
		DListNode<T>* CurrentNode = mBegin->mNext;

		// 해당 인덱스까지 링크타고 넘어감.
		while (mIndex<Index)
		{
			CurrentNode = CurrentNode->mNext;
			mIndex++;
		}

		// 데이터 반환
		return CurrentNode->mData;
	}
};

 리스트 사용

#include <iostream>
#include "DLinkedList.h"

int main()
{
    DLinkedList<int> DListInt;
    for (int i = 0; i < 10; i++)
    {
        DListInt.Add_Front(i);
        printf("Add Front --> %d\n", i);
    }

    printf("\n\n");
    printf("value : %d", DListInt.GetValueAt(8));
}

출력

Add Front --> 0
Add Front --> 1
Add Front --> 2
Add Front --> 3
Add Front --> 4
Add Front --> 5
Add Front --> 6
Add Front --> 7
Add Front --> 8
Add Front --> 9


value : 1