이중 링크드 리스트 만들기 (Making double linked list)

링크드 리스트가 단일인 경우에는 포인터로 처리하는 것이 좋겠지만,  이중인 경우에는 그게 만만치 않아요.  포인터로 관리하려면, 포인터가 NULL인 경우 처리가 필요합니다.  새로운 노드를 추가하는 경우에는 포인터가 NULL인지 검사해야 하고, 기존 노드를 삭제하는 경우에는 노드의 갯수가 1개인지를 검사해야 합니다.

 

그래서 사용하는 방법은 바로 이것입니다.

클래스만 설계해보면,

 

class CNode
{
public:
  CNode *m_pPrev;
  CNode *m_pNext;
};

class CIntNode : public CNode
{
public:
  int data;
};

class CDLinkedList
{
public:
  CDLinkedList() { m_kRoot.m_pPrev = &m_kRoot; m_kRoot.m_pNext = &m_kRoot; }
  ~CDLinkedList() { while(m_kRoot.m_pNext != &m_kRoot) Remove(m_kRoot.m_pNext); }
  CNode *Add(int data)
  {
    CIntNode *pTmp = new CIntNode;
    pTmp->data = data;
    pTmp->m_pNext = m_kRoot.m_pNext;
    pTmp->m_pPrev = &m_kRoot;
    m_kRoot.m_pNext->m_pPrev = pTmp;
    m_kRoot.m_pNext = pTmp;
    return pTmp;
  }
  CNode *Remove(CNode *pTmp)
  {
    pTmp->m_pNext->m_pPrev = pTmp->m_pPrev;
    pTmp->m_pPrev->m_pNext = pTmp->m_pNext;
    return pTmp;
  }
private:
  CNode m_kRoot;
};

 

포인터를 사용치 않고, 더미 노드를 사용하면 위의 예외처리하는 부분이 깨끗이 없어집니다.

어차피 메모리상 노드 하나 더 쓰는 것이니까요..  노드 상속을 이용하면 메모리상에서도 전혀 문제없이 처리를 할 수 있습니다.  이중 연결 리스트를 구현한 곳을 보면, head와 tail이라는 노드 포인터를 어차피 이용하거든요.  이곳에서는 비어있는 노드(데이터 영역을 전혀 쓰지 않아서 그만큼 메모리를 낭비하는.)를 이용했지만, 상속형태가 된다면 그마저도 필요가 없습니다.  단지 형변환이 필요할 수 있기 때문에 그까짓 데이터 하나정도의 낭비는 프로그래머로서의 귀치니즘에 비해서는 별거 아닙니다.
그리고 기본 노드가 있는 것이 다형성면에서 매우 유리하니까요..