[C++] 구조체 · 클래스 템플릿으로 리스트 구현

코드를 작성할 때 노드는 구조체로, 리스트는 클래스로 만들었지만, C++에서 클래스와 구조체는 같아졌기 때문에 어떤 것을 사용하든 크게 상관은 없다.

구조체도 생성자, 소멸자, 상속이 가능해졌다.

단, 클래스와 구조체의 차이점은 범위 지정자의 기본값이 다르다는 것이다.

구조체는 public이고 클래스는 private이다.

 

구조체와 클래스 중 어떤 것을 사용할지 모르겠을 때, 나름의 규칙을 만들면 좋다.

ex) 기능이 많지 않을 때(단순히 데이터를 묶어놓고 데이터를 저장하는 등)는 구조체 키워드를, 리스트처럼 컨테이너로써의 복잡한 기능이면 클래스로 선언한다.

 

※ 구조체 템플릿은 구조체가 아니다.

프로그래머는 넣은 데이터가 노드 단위인 것을 알 필요가 없어야 된다.

다시 말해서, 리스트에 데이터를 넣을 뿐, 데이터를 전달받은 대상이 노드라는 것을 만들어서 데이터를 관리하는지 사용자는 알 필요가 없어야 한다.

리스트에 `int` 데이터가 들어가는 버전을 요청했다면, 자연스럽게 리스트 클래스는 `T`에 `int`를 받아와서 `int`를 저장하는 노드를 가리키는 멤버를 가진다.

따라서 리스트의 타입을 정해주면 노드의 타입도 정해진다.

---

생성자 오버로딩

생성자도 오버로딩이 가능하다.

// 기본 생성자
tListNode()
    : data()
    , pPrev(nullptr)
    , pNext(nullptr)
{
}
// 생성자 오버로딩
	// 인자를 받아오는 버전의 생성자
	// 받아온 인자로 초기화한다.
tListNode(const T& _data, tListNode<T>* _pPrev, tListNode<T>* _pNext)
    : data(_data)
    , pPrev(_pPrev)
    , pNext(_pNext)
{

}

---

CList.h

#pragma once

// 양방향으로 관리하기 위해 노드 부분에는 pPrev를, 리스트 부분에는 m_pTail을 추가했다.
template<typename T>
struct tListNode
{
	T data;
	// 선언한 구조체 템플릿의 내부에 있기 때문에 tListNode에 <T>를 적지 않아도 되지만, 명확성을 위해 적어주는 것이 좋다.
	tListNode<T>* pPrev;  // 이전 노드 주소
	tListNode<T>* pNext;  // 다음 노드 주소

	// 기본 생성자
	tListNode()
		: data()
		, pPrev(nullptr)
		, pNext(nullptr)
	{
	}
	// 생성자 오버로딩
	tListNode(const T& _data, tListNode<T>* _pPrev, tListNode<T>* _pNext)
		: data(_data)
		, pPrev(_pPrev)
		, pNext(_pNext)
	{
		
	}

	// 소멸자는 딱히 할 일이 없어서 만들지 않았다.
};

// 구조체가 아니라 구조체 템플릿이라서 아직 정해지지 않았기 때문에 리스트도 템플릿으로 만들어야 한다.
template<typename T>
class CList
{
private:
	// 리스트는 실제로 사용하기 때문에 tListNode에 <T>를 붙여줘야 한다.
	tListNode<T>* m_pHead; // 시작 노드 주소
	tListNode<T>* m_pTail;  // 마지막 노드 주소
	int m_iCount;  // 리스트 안에 있는 데이터 개수

public:
	void push_back(const T& _data);
	void push_front(const T& _data);

public:
	CList();
	~CList();
};

template<typename T>
void CList<T>::push_back(const T& _data)
{
	// 노드 생성
		// 입력된 데이터를 지정할 노드를 동적할당했다.
	//tListNode<T>* pNewNode = new tListNode<T>;  // new하고 옆에 아무것도 적지 않으면 기본 생성자를 호출한다.
	// 받아온 데이터는 tListNode의 T data; 부분에 data에 들어간다.
	// 만약 기본 생성자로 호출했다면 pNewNode를 만들고 나서 일일이 구조체로 접근해서 각각의 파트에 맞는 것을 넣어줘야 한다.
	// 때문에 초기값을 생성자로 한 번에 호출하는데, 전달해준 인자로 초기화를 하기 위해 인자를 전달받아서 초기화되는 버전의 생성자를 오버로딩했다.
	tListNode<T>* pNewNode = new tListNode<T>(_data, nullptr, nullptr);

	// 처음 입력된 데이터라면
	if (nullptr == m_pHead)
    // 헤드 포인터가 null이면 데이터가 처음 입력된 데이터이다.
	{
		m_pHead = pNewNode;
		m_pTail = pNewNode;
	}
	else
	// (강의 영상의 설명)
	// 처음 입력된 데이터가 아니라면
		// 데이터가 1개 이상 입력된 경우
		// 현재 가장 마지막 데이터(tail)를 지정하고 있는 노드와 새로 생성된 노드가 서로 가리키게 한다.
	{
	// (내가 강의 듣고 작성한 내용)
		// 현재 가장 마지막 노드를 알아야 생성시킨 노드를 연결해줄 수 있다.
			// 그 마지막 노드에서 다음 주소를 가르키는 부분이 null이면 현재 가장 마지막 노드이다.
			// 다음 주소를 가리키는 부분에 생성시킨 노드의 주소를 넣어준다.
		// 양방향이기 때문에 새로운 노드도 생성시킨 노드를 가리켜야 된다.
		m_pTail->pNext = pNewNode;
		pNewNode->pPrev = m_pTail;

		// 리스트가 마지막 노드의 주소값을 새로 입력된 노드로 갱신한다.
		m_pTail = pNewNode;  // 현재 가장 마지막 노드를 생성시킨 노드로 갱신시킨다.
	}

	// 데이터 개수 증가
	++m_iCount;
}

template<typename T>
void CList<T>::push_front(const T& _data)
// 노드를 하나 생성시켜서 리스트가 생성시킨 노드를 헤드로 가리키고, 생성시킨 노드는 원래 헤드였던 노드를 가리킨다.
{
	// 생성시킨 노드는 이전이 존재하면 안 된다. => _pPrev는 null
	// 생성시킨 노드는 원래 헤드의 주소값을 가르켜야 한다. => _pNext는 m_pHead
		// 새로 생성된 노드의 다음을 현재 헤드 노드의 주소값으로 채운다.
	tListNode<T>* pNewNode = new tListNode<T>(_data, nullptr, m_pHead);

	// 현재 헤드 노드의 이전 노드 주소값을 새로 생성된 노드의 주소로 채운다.
	m_pHead->pPrev = pNewNode;

	// 리스트가 새로 생성된 노드를 새로운 헤드 주소로 갱신한다.
	m_pHead = pNewNode;

	// 데이터 개수 증가
	++miCount;
}

// 생성자
template<typename T>
CList<T>::CList()
	: m_pHead(nullptr)
	, m_pTail(nullptr)
	, m_iCount(0)
{

}

// 소멸자
template<typename T>
CList<T>::~CList()
{
	tListNode<T>* pDeleteNode = m_pHead;  // 첫 번째 노드를 받아온다.

	while (pDeleteNode)
	{
		// 다음 노드의 다음 꺼를 기억해두고 지우는 것을 반복한다.
		tListNode<T>* pNext = pDeleteNode->pNext;  // 삭제할 노드(pDeleteNode)의 다음 노드(pNextNode)를 pNext에 넣는다.
		delete(pDeleteNode);  // 해당 메모리 해제
		pDeleteNode = pNext;  // 삭제할 노드를 다음 노드로 갱신시킨다.
	}
}

 

Arr.h

#pragma once

// 가변 배열 자료형 tArr (int)
typedef struct _tagArr
{
	int* pInt;
	int iCount;
	int iMaxCount;
}tArr;

// 배열 초기화(초기값을 줄뿐 문법적으로 진짜 초기화는 아니다.) 함수
void InitArr(tArr* _pArr);

// 데이터 추가 함수
void PushBack(tArr* _pArr, int _iData);

// 공간 추가 확장 함수
void Reallocate(tArr* _pArr);

// 배열 메모리 해제 함수
void ReleaseArr(tArr* _pArr);

 

Arr.cpp

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

// 배열 초기화
void InitArr(tArr* _pArr)
{
	_pArr->pInt = new int[2];  // new[]를 사용하여 메모리 할당
	_pArr->iCount = 0;
	_pArr->iMaxCount = 2;
}

// 공간 추가 확장
void Reallocate(tArr* _pArr)
{
	// 1. 2배 더 큰 공간을 동적할당한다.
	int* pNew = new int[_pArr->iMaxCount * 2];

	// 2. 기존 공간에 있던 데이터들을 새로 할당한 공간으로 복사시킨다.
	for (int i = 0; i < _pArr->iCount; ++i)
	{
		pNew[i] = _pArr->pInt[i];
	}

	// 3. 기존 공간은 메모리 해제
	delete[] _pArr->pInt;

	// 4. 배열이 새로 할당된 공간을 가리키게 한다.
	_pArr->pInt = pNew;

	// 5. iMaxCount 변경점 적용
	_pArr->iMaxCount *= 2;
}

// 뒤에 데이터 추가
void PushBack(tArr* _pArr, int _iData)
{
	if (_pArr->iMaxCount <= _pArr->iCount)
	{
		// 재할당
		Reallocate(_pArr);
	}

	// 데이터 추가
	_pArr->pInt[_pArr->iCount++] = _iData;
}

// 배열 메모리 해제
void ReleaseArr(tArr* _pArr)
{
	delete[] _pArr->pInt;
	_pArr->iCount = 0;
	_pArr->iMaxCount = 0;
}

 

linkedList.h

#pragma once

// 노드 => 저장하고자 하는 데이터 + 다음 노드의 주소
typedef struct _tagNode
{
	int iData;
	struct _tagNode* pNextNode;
}tNode;

typedef struct _tagList
{
	tNode* pHeadNode; // 노드 주소
	int iCount;  // 데이터 개수
}tLinkedList;

 

linkedList.cpp

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

void InitList(tLinkedList* _pList)
{
	_pList->pHeadNode = nullptr;
	_pList->iCount = 0;
}

void PushBack(tLinkedList* _pList, int _iData)
{
	tNode* pNode = (tNode*)malloc(sizeof(tNode));  // 노드 사이즈만큼 만들고 주소는 노드 단위로 데이터를 사용할 것이기 때문에 tNode*로 받아온다.
	pNode->iData = _iData;
	pNode->pNextNode = nullptr;

	// 지금 들어온 데이터(추가한 데이터)가 처음인지 아닌지를 따져봐야 한다.
	// 만약 현재 들어온 데이터의 개수가 0(또는 pHeadNode(첫 번째 노드)가 nullptr)이라면
	if (0 == _pList->iCount)
	{
		_pList->pHeadNode = pNode;  // 노드의 주소를 저장한다.
	}
	// 노드 안에 데이터가 1개 이상이면 else에 걸린다.
	else
	{
		// 현재 가장 마지막 노드 즉, 바로 앞전의 노드를 찾아서 해당 노드의 pNextNode를 생성시킨 노드의 주소로 채운다.
		// 단방향에서 양방향으로 하려면 Head뿐만 아니라 제일 마지막 노드인 Tail도 알아야 한다.
		tNode* pCurFinalNode = _pList->pHeadNode;
		// pNextNode가 nullptr이면 0이고, 이는 false를 뜻하므로 반복문이 끝나게 된다.
		// 반대로 0이 아닌 모든 수는 true이기 때문에 pNextNode가 존재한다면 반복문이 실행된다.
		while (pCurFinalNode->pNextNode)
		{
			// 헤드 노드의 다음이 있다면, 주소 변수를 본인이 가리키고 있는 pNextNode로 갱신시킨다.
			pCurFinalNode = pCurFinalNode->pNextNode;
		}

		pCurFinalNode->pNextNode = pNode;  // pNextNode를 지금 생성시킨 노드의 주소로 넣는다.
	}

	++_pList->iCount;  // 데이터 하나가 들어왔으니 카운트 하나 증가한다.
}

void PushFront(tLinkedList* _pList, int _iData)
{
	// 새로 생성시킨 노드의 다음을 기존의 헤드로 지정한다.
	tNode* pNewNode = (tNode*)malloc(sizeof(tNode));
	pNewNode->iData = _iData;
	pNewNode->pNextNode = _pList->pHeadNode; // 원래 리스트가 가리키고 있던 헤드가 다음 노드가 되어야 들어올 노드가 그 앞에 들어와서 리스트가 이를 헤드로 지정한다.

	// 리스트의 헤드 노드 포인터를 갱신한다.
	_pList->pHeadNode = pNewNode;

	// 데이터가 들어왔으니 카운트를 증가시킨다.
	++_pList->iCount;
}

// 연결형 리스트 메모리 해제 방법 2가지
// 1. 재귀함수(효율은 좋지 않다.)
// 함수가 데이터의 개수만큼 호출되기 때문에 데이터의 양이 많아지면 효율이 좋지 않기 때문에 구현 방법은 간단하지만 좋은 방법은 아니다.
void Release(tNode* _pNode)
{
	// 탈출 조건
	// 들어온 포인터가 null일 경우에 아무것도 하지 않고 리턴한다.
	if (nullptr == _pNode)
		return;

	//free(_pNode);  // 받자마자 해제하면 데이터가 다 날라가버려서 다음 노드로 갈 수가 없다.

	// Release로 먼저 호출하여 먼저 pNextNode의 주소를 받아서 그 다음 노드를 지운다.
	// 그럼 맨 마지막 노드부터 차례대로 지워진다.
	Release(_pNode->pNextNode);
	free(_pNode);  // 그렇게 메모리가 해제되다가 첫 번째 노드까지 돌아오고 나면 free() 함수로 인해 메모리가 해제된다.
}

// 2. 반복문
void ReleaseList(tLinkedList* _pList)
{
	tNode* pDeleteNode = _pList->pHeadNode;  // 첫 번째 노드를 받아온다.

	// pDeleteNode가 null이 될 때까지 반복문은 반복된다.
	while (pDeleteNode)
	{
		// 다음 노드의 다음 꺼를 기억해두고 지우는 것을 반복한다.
		tNode* pNext = pDeleteNode->pNextNode;  // 삭제할 노드(pDeleteNode)의 다음 노드(pNextNode)를 pNext에 넣는다.
		free(pDeleteNode);  // 해당 메모리 해제
		pDeleteNode = pNext;  // 삭제할 노드를 다음 노드로 갱신시킨다.
	}
}

 

main.cpp

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

int main()
{
    // int버전 리스트
    CList<int> list;

    // 0~3까지 넣기
    for (int i = 0; i < 4; ++i)
    {
        list.push_back(i);
    }

    // std:cout vs. printf => std:cout은 치환될 부분을 적지 않고 작성할 내용을 쭉 작성하면 된다.
    // << => 비트 연산자와 똑같이 생겼지만 출력에 사용하고 적어나가는 느낌이다.
    // 1. C++ printf
    std::cout << "안녕" << 10 << std::endl;

    // 2. C++ scanf
    int iInput = 0;
    std::cin >> iInput;

    return 0;
}