연결형 리스트 구현

1. 연결형 리스트(Linked List) 란?

 

 하나의 개체를 이루는 노드가 연결되어 리스트를 이루는 "자료구조" 를 말한다.

노드에는 값을 담고 있는 '데이터'와 다음 노드를 가리키는 '링크' 정보를 저장하고 있는 것이 기본이다. '데이터'에는 숫자, 문자열, 또다른 연결리스트 등 다양한 형식을 가질 수 있다.

일반적으로 리스트의 맨 앞 노드를 헤드(Head), 맨 마지막 노드를 테일(Tail)이라고 한다.

 

2. 배열과의 차이점 

 

 배열과 연결리스트는 언뜻 비슷해 보이나, 차이점은 분명히 있다.
배열은 메모리의 연속한 위치에 저장되고, 연결 리스트는 각 노드가 임의의 위치에 저장된다.
또한 배열은 특정 원소를 지칭하는 것이 인덱스를 활용하는 등으로 간편하나(O(1)), 연결 리스트는 선형 탐색을 하듯 한 노드에서 다음 노드를 따라가야 한다(O(n)).
하지만 배열보다 연결리스트는 비교적 삽입과 삭제가 용이하다.

 

3. 연결형 리스트 구현

#pragma once

//기능이 많지 않을때
template<typename T>
struct tNode
{
	T          Data;
	tNode<T>* pPrev;
	tNode<T>* pNext;
	
public: 
	tNode()
		:Data(0)
		,pPrev(nullptr)
		,pNext(nullptr)
	{
	}
	//생성자 오버로딩
	tNode(T _Data, tNode<T>* _pPrev, tNode<T>* _pNext)
		:Data(_Data)
		,pPrev(_pPrev)
		,pNext(_pNext)
	{
	}
};

// 클래스 리스트 리스트 클래스 생성

// 클래스 = 사용자 정의 자료형
template<typename T>
class cList
{

private:

	tNode<T>* m_pHeadNode;
	tNode<T>* m_pTailNode;
	int m_iCount;

public:
	//생성자 (초기화)
	cList();

	//소멸자
	~cList();

public :

	//멤버함수
	void pushBack(const T& _Data);
	void pushFront(const T& _Data);
	
};

template<typename T>
cList<T>::cList()
//이니셜라이저
	:m_pHeadNode(nullptr)
	,m_pTailNode(nullptr)
	,m_iCount(0)
{
}

template<typename T>
cList<T>::~cList()
{
	//첫번째 노드부터 다음주소를 받아서 하나씩 지워나감
	//첫번재 노드를 가리키는 포인터 변수생성
	tNode<T>* pDeleteNode = m_pHeadNode;

	//반복문을 돌면서 첫번째 노드 부터 순차적으로 힙 메모리 영역 할당 해제
	while (pDeleteNode)  // pDeleteNode = 0 = nullptr일때까지 반복
	{
		//지우기 전에 현재 노드의 다음을 가리키는 노드주소를 변수로 받아놓음
		tNode<T>* pNextNode = pDeleteNode->pNext;
		
		delete(pDeleteNode); //할당해제
		
		pDeleteNode = pNextNode; //pDeleteNode = 받아놓았던 다음노드
	}
	
}

template<typename T>
void cList<T>::pushBack(const T& _Data)
{
	// 노드 변수 선언 및 초기화, 생성자 오버로딩으로 코드가 간결해짐
	tNode<T>* pNode = new tNode<T>(_Data, nullptr, nullptr);
	
	// 데이터가 없을경우 
	if (m_pHeadNode == nullptr)
	{
		//기존에 가리키던 노드가 없었기 때문에 처음 들어온 노드를 가리킴
		m_pHeadNode = pNode;
		m_pTailNode = pNode;
	}

	// 기존에 데이터가 있을경우
	else
	{
		//서로를 이어줌
		m_pTailNode->pNext = pNode;
		pNode->pPrev = m_pTailNode;
		m_pTailNode = pNode;
	}
	// count 값 증가
	
	++m_iCount;
	
}

template<typename T>
void cList<T>::pushFront(const T& _Data)
{
	// 기존에 데이터가 있을경우 pushFront이기 때문에
	// 원래 헤드 노드의 앞자리에 오기때문에 pNode->pNext = m_pHeadNode 이다 
	tNode<T>* pNode = new tNode<T>(_Data, nullptr, m_pHeadNode);

	//서로 연결해줌
	m_pHeadNode->pPrev = pNode;

	m_pHeadNode = pNode;

	//카운트 값 증가
	++m_iCount;
}

 

 

4. 연결형 리스트 실행