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

출처 : https://www.geeksforgeeks.org/difference-between-singly-linked-list-and-doubly-linked-list/

- 배열과는 다르게 노드(Node) 간의 연결(Link)를 통해서 구현하는 방식이다.

- 노드들을 순서대로 나열하는 선형적(순차적)인 구조다.

- 노드는 데이터, 자신과 연결되어있는 이전, 다음 노드의 주소(메모리에 할당되어 있는 주소)를 가지고 있다.

  (단방향 리스트는 자신과 연결된 이전 노드의 주소를 가지고 있지 않는다. 오직 자신의 다음 주소만을 가지고 있다.)

---

노드 클래스의 구성

template <typename T>
class CListNode
{
private:
    CListNode()
    {
    	m_pNext = nullptr;
    	m_pPrev = nullptr;
    }    
    ~CListNode()
    {
    }

private:
    T m_data;               // 실제 데이터
    CListNode<T>* m_pNext;  // 다음 노드의 주소
    CListNode<T>* m_pPrev;  // 이전 노드의 주소
};

---

더미 노드(Dummy Node)

 - 더미 노드는 노드의 맨 처음과 끝에 Begin, End 노드를 두어서 리스트의 전체 반복을 처리할 때

   시작과 끝이 명확하므로 반복 처리하게 편한 장점이 있다.

 - 처음 생성 시 Begin, End 노드를 서로 연결시킨 후 추가되는 노드를 연결한다. 

template <typename T>
class CLinkedList
{
public:
    CLinkedList()
    {
    	m_iSize  = 0;
    	m_pBegin = new NODE;
    	m_pEnd   = new NODE;    
    	
        // 시작 노드와 끝 노드를 서로 연결한다.
    	m_pBegin->m_pNext = m_pEnd;
    	m_pEnd->m_pPrev = m_pBegin;
    }
    
    ~CLinkedList()
    {
    	// 할당된 메모리는 소멸자에서 삭제
    	clear();
    	delete m_pBegin;
    	delete m_pEnd;
    }

private:
    int   m_iSize;
    PNODE m_pBegin; // 시작 노드
    PNODE m_pEnd;   // 끝 노드
}

---

코드 첨부 파일

main.cpp

0.00MB

LinkedList.h

0.01MB