싱글 링크드 리스트, 더블 링크드 리스트 ( Single Linked List, Double Linked List )

최근 이직 준비를 위해 기본기를 다시 공부하고 있습니다. 면접시 나오는 질문들에 우물쭈물 대답을 못한 적이 한두번이 아니라 ( 왜 아는 것들도 면접때면 생각이 안나게 될까요... ) 반복 복습만이 답인것 같습니다.

그래서 면접 질문시 자주 나오는 링크드 리스트를 구현해봤습니다.

밑의 것은 더블 링크드 리스트로 이전 노드를 가리키는 포인터만 없애면 싱글 링크드 리스트가 됩니다.

( 이걸 백지 코딩 하라고 하면 또 우물쭈물... )

리스트 맨뒤에 데이터를 추가하는 Push_Back 과 리스트 맨 앞에 데이터를 추가하는 Push_Front, 그리고 임의의 노드를 삭제하는 Erase 까지 구현했습니다. 임의의 위치에 데이터를 추가하는 Insert는 Erase를 살짝 바꿔주면 됩니다.

using namespace std;

typedef struct _stNode
{
	int iData;
	_stNode* pPrev;
	_stNode* pNext;
} stNode;

class CDoubleLinkedList
{
public:
	CDoubleLinkedList();
	~CDoubleLinkedList();
	int GetNodeCount( void ) { return m_iNodeCount; }
	void PushBack( int iData );
	void PushFront( int iData );
	void Erase( int iData );
	void Printf( void );

private:
	int m_iNodeCount;		// 현재 노드 갯수
	stNode* m_pHead;	// 리스트의 머리
	stNode* m_pTail;	// 리스트의 꼬리
};

// 생성자
CDoubleLinkedList::CDoubleLinkedList()
{
	// 초기화
	m_iNodeCount = 0;
	m_pHead = NULL;
	m_pTail = NULL;
}

// 소멸자
CDoubleLinkedList::~CDoubleLinkedList()
{
	// 소멸시 모든 노드 리스트 삭제
	stNode* pNode = m_pHead;
	stNode* pTemp = pNode;
	while( NULL != pNode )
	{
		pTemp = pNode;
		pNode = pNode->pNext;

		delete pTemp;
	}

	m_iNodeCount = 0;
}

// 리스트 맨 뒤에 추가
void CDoubleLinkedList::PushBack( int iData )
{
	stNode* pNode = new stNode;
	pNode->iData = iData;
	pNode->pNext = NULL;
	pNode->pPrev = NULL;

	// 머리가 없으면 처음 추가되는 것이므로,
	// 머리/꼬리 모두 생성된 노드로 설정.
	if( !m_pHead )
	{
		m_pHead = m_pTail = pNode;
		++m_iNodeCount;
		return;
	}

	// 마지막 노드가 새로 뒤에 추가된 노드를 가리킨다.
	// 새로 추가된 마지막 노드는 전 노드로 이전 마지막 노드를 가리킨다.
	// 새로 추가된 노드를 마지막 노드로 설정 한다.
	m_pTail->pNext = pNode;
	pNode->pPrev = m_pTail;
	m_pTail = pNode;

	++m_iNodeCount;
}

// 리스트 맨 앞에 추가
void CDoubleLinkedList::PushFront( int iData )
{
	stNode* pNode = new stNode;
	pNode->iData = iData;
	pNode->pNext = NULL;
	pNode->pPrev = NULL;

	// 머리가 없으면 처음 추가되는 것이므로,
	// 머리/꼬리 모두 생성된 노드로 설정.
	if( !m_pHead )
	{
		m_pHead = m_pTail = pNode;
		++m_iNodeCount;
		return;
	}

	// 새로 첫 번째로 추가된 노드는 이전 첫 번째 노드를 가리킨다.
	// 이전 첫 번째 노드는 새로 추가된 첫번째 노드를 이전 노드로 가리킨다.
	// 새로 추가된 노드를 첫 번째 노드로 설정 한다.
	pNode->pNext = m_pHead;
	m_pHead->pPrev = pNode;
	m_pHead = pNode;

	++m_iNodeCount;
}

// 임의의 데이터에 해당 하는 노드 삭제
void CDoubleLinkedList::Erase( int iData )
{
	stNode* pNode = m_pHead;
	while( pNode != NULL )
	{
		// 지우려고 하는 데이터와 같으면 삭제
		if( pNode->iData == iData )
		{
			stNode* pPrev = pNode->pPrev;
			stNode* pNext = pNode->pNext;

			// 이전 노드가 NULL 이라면 현재 노드는 머리다.
			// 아니라면 이전 노드와 다음 노드를 연결해주자
			if( NULL == pPrev )
				m_pHead = pNext;
			else
				pPrev->pNext = pNext;

			// 다음 노드가 NULL 이라면 현재 노드는 꼬리다.
			// 아니라면 다음 노드와 이전 노드를 연결해주자
			if( NULL == pNext )
				m_pTail = pPrev;
			else
				pNext->pPrev = pPrev;

			delete pNode;
			--m_iNodeCount;

			break;
		}
		pNode = pNode->pNext;
	}
}

// 현재 노드들을 순환해서 출력
void CDoubleLinkedList::Printf( void )
{
	stNode* pNode = m_pHead;
	while( pNode != NULL )
	{
		cout << pNode->iData << ", ";
		pNode = pNode->pNext;
	}
	cout << endl;
}

// 테스트
void main()
{
	CDoubleLinkedList* pList = new CDoubleLinkedList;
	pList->PushBack( 3 );
	pList->PushBack( 4 );
	pList->PushBack( 5 );
	pList->PushFront( 2 );
	pList->PushFront( 1 );
	pList->PushFront( 0 );
	pList->Printf();	
	pList->Erase(3);
	pList->Printf();
	pList->Erase(0);
	pList->Printf();
	pList->PushFront( -1 );
	pList->Printf();
	pList->Erase(5);
	pList->Printf();
	pList->PushBack( 6 );
	pList->Printf();

	delete pList;
}