C++ 기초 : 클래스 템플릿을 이용한 리스트 구현

---

기존의 구조체로 만들었던 연결형 리스트를

클래스 템플릿을 이용하여 구현하겠습니다.

 

먼저 cList.h 파일을 만들고

 

cList라는 클래스 템플릿과 

tListNode라는 구조체 템플릿을 만들었습니다.

 

C++에서는 사실 구조체와 클래스와의 차이가 없습니다.

 

작은 차이라면 구조체는 아무 키워드도 적지 않으면

기본적으로 public으로 선언되고

클래스는 아무 키워드도 적지 않으면 기본적으로

private로 선언된다는 차이 정도죠.

 

그래서 구조체 템플릿으로 선언된 tListNode는 

사실 클래스 템플릿으로 선언해도 문제가 없습니다.

 

 

일단 클래스 템플릿 cList부터 보시죠.

 

첫 번째 노드의 주솟값을 저장할 멤버 pHead와

마지막 노드의 주솟값을 저장할 멤버 pTail이 있습니다.

 

두 멤버는 tListNode형 객체(노드)의 주솟값을 저장할 것이기 때문에

tListNode형 포인터로 선언되었죠.

 

또한 T를 붙여줌으로써 노드가 어떤 자료형이든

해당 노드를 가리킬 수 있게 하였죠.

 

변수 iCount는 현재 리스트가 관리하는 

데이터의  개수를 나타냅니다.

 

마지막으로 생성자와 소멸자를 선언하였습니다.

 

 

구조체 템플릿 tListNode는 어떤 자료형을 가진

데이터가 들어올지 모르기 때문에 데이터를 담을 T형

변수 data를 멤버로 갖고 있습니다.

 

그리고 이전 노드의 주솟값을 저장하기 위한 

멤버 pPrev와 다음 노드의 주솟값을 저장하기 위한

멤버 pNext가 있습니다.

 

---

 

 

 

cList 클래스 템플릿의 생성자 함수에

 

cList 클래스 템플릿으로 객체를 만들면

초기화가 진행될 수 있도록 이니셜라이저를 넣었습니다.

 

리스트로 활용할 객체가 만들어지면 처음에는 노드가 없기 때문에

pHead와 pTail이 아무것도 가리키지 않겠죠. 그래서

nullptr로 초기화해 주고 데이터가 없기 때문에

iCount의 값은 0으로 초기화해 줍니다.

 

 

 

---

 

 

 

 

 

소멸자는 이따가 작성하도록 하고

 

리스트 가장 앞에 노드를 추가하는 함수 push_back과

리스트 가장 마지막에 노드를 추가하는 함수 push_front를

선언하였습니다.

 

매개변수를 const T형 레퍼런스로 하는 이유는

어떤 자료형을 가진 데이터가 삽입될지 모르기 때문에 T형으로,

성능을 위해 복사 과정을 거치지 않고

바로 값을 참조하여 대입할 수 있도록 레퍼런스로, 

값을 수정하면 안되기 때문에 const로 한 겁니다.

 

 

먼저 함수 push_back부터 구현하도록 하죠.

 

아래 코드를 보시죠.

 

60번째 줄에서 동적 할당을 진행하고 있습니다. 

 

근데 구조체 템플릿을 이용하여

동적 할당을 진행하는데 인자가 있습니다.

 

 

그래서 구조체 템플릿 tListNode를 

 

살펴 보니 생성자가 추가되었습니다.

 

C++에서는 구조체와 클래스 사이의 차이가 거의 없어진 만큼

구조체에서도 생성자와 소멸자를 넣어줄 수 있습니다.

 

노드 역할을 할 tListNode에서는 소멸자는 넣어줄 필요가 없겠죠?

어차피 이러한 노드들을 관리하는 cList의 소멸자를 통해 

메모리 해제가 진행되니 말이죠.

 

생성자는 기본 생성자와 인자를 받을 시 호출되는 생성자,

총 두 개를 오버로딩을 통해 구성하였습니다.

 

 

기본 생성자를 보면 data의 자료형이 무엇이 될지 알 수 없으므로

data 자체를 기본 생성자로 호출한 것을 확인할 수 있습니다. 

pPrev와 pNext는 처음 생성될 때부터 이전 노드와 다음 노드의 주솟값을

미리 알고 넣어줄 수 없기 때문에 nullptr로 초기화해줬습니다.

 

 

인자 세 개를 받는 생성자를 보면 const T형 레퍼런스 변수와

tListNode<T>형 포인터 변수 두 개를 매개변수로 하고 있습니다.

해당 매개변수의 값으로 data, pPrev, pNext를 초기화하죠.

 

 

이렇게 해서 동적 할당하자마자 해당 공간에는 push_back 함수를 

통해 들어온 data가 들어가게 되고 이전 노드와 다음 노드를 가리키는 

멤버는 nullptr로 초기화됩니다. 기존의 push_back 함수에서 

멤버에 접근하여 하나씩 값을 초기화하였습니다.

이러한 방법 대신에 new 키워드로 동적 할당을 할 때

생성자를 호출하고 자연스럽게 초기화될 수 있도록 한 것입니다.

 

 

만약 데이터가 처음 들어와 첫 번째 노드가 생성될 때에는

첫 번째 노드를 가리키는 pHead가 nullptr일 겁니다.

 

이 경우 pHead가 새로 생성된 노드를 가리킬 수 있도록 하고

처음 생성된 노드는 첫 번째 노드이자 마지막 노드이므로

마지막 노드를 가리키는 pTail도 새로 생성된 노드를 가리킬 수 

있도록 합니다.

 

 

데이터를 삽입하여 노드가 생성될 때 이미 다른 노드가 존재하였다면

새로운 노드의 멤버 pPrev가 pTail이 가리키는 노드를 가리키게 합니다.

push_back 함수이므로 새로운 노드는 맨 뒤에 위치할 것이므로

새로운 노드의 멤버 pPrev는, 과거 맨 뒤에 위치했었던 노드를 가리켜야 하겠죠.

 

그리고 과거 맨 뒤에 위치했었던 노드는 이제 앞에 새로 생성된 

노드가 존재하므로 pNext로 새로 생성된 노드를 가리켜야 합니다.

 

마지막으로 새로 생성된 노드가 마지막 노드이므로 

pTail은 새로 생성된 노드를 가리켜야 하죠.

 

 

push_back 함수로 인해 값이 하나 더 생겼으므로 

iCount의 값을 하나 올립니다.

 

 

 

 

---

 

 

 

 

이제 push_front 함수를 구현하겠습니다.

 

해당 함수를 통해 맨 앞에 들어갈 노드를 만드는 겁니다.

 

그러므로 동적 할당하면서 노드의 생성자를 호출할 때 

해당 함수로 받은 데이터, nullptr, pHead를 인자로 넘깁니다.

 

그러면 동적 할당한 공간의 data 값은 인자로 받은 값, 

pPrev는 nullptr, pNext는 pHead를 가리키게 될 겁니다.

pNext로 pHead가 가리키는 노드,

즉 과거 맨 앞에 위치했었던 노드를 가리킵니다.

 

 

그리고 과거 맨 앞에 위치했었던 노드는 이제 

두 번째 노드로 밀려났으므로 해당 노드 입장에서 

이전 노드는 새로 생성된 노드겠죠.

그래서 pPrev에 pNewNode(새로 생성된 노드)의 주솟값을 저장합니다.

 

 

이제 맨 앞에 노드를 가리키는 pHead로 새로 생성된 노드를 가리킵니다.

 

 

그리고 노드 하나가 추가되었으므로

iCount의 값을 하나 올려 줍니다.

 

 

 

---

 

 

 

cList 클래스 템플릿의 소멸자도 마저 작성하겠습니다.

 

소멸자가 호출되면

tListNode<T>형 포인터 deleteNode가

첫 번째 노드의 주솟값을 저장합니다.

 

그리고 반복문을 돌 건데,

tListNode<T>형 포인터 nextNode가 

deleteNode가 가리키는 노드의 다음 노드 

주솟값을 저장합니다.

 

그리고 deleteNode가 가리키는 노드를 해제합니다.

 

이후 deleteNode에 nextNode가 저장한 주솟값을 저장합니다.

즉 방금 해제된 노드의 다음 주솟값을 저장하는 거죠.

 

다음 노드가 존재하여서 deleteNode에 다음 노드의

주솟값이 저장되었다면 다시 반복문을 반복하고

다음 노드가 존재하지 않아서 deleteNode에 값이 

저장되지 않았다면 while문이 false가 

되므로 while문을 빠져나갑니다.

 

 

 

---

 

 

 

main.cpp에서

 

cList<int>형 객체 list를 만들고

push_back 함수를 통해

노드 세 개에 1, 2, 3을 대입하겠습니다.

 

실행 결과를 보겠습니다.

 

위 결과에서 첫 번째 노드를 가리키는 pHead를 보니

값이 1이 들어가 있고 이전 노드를 나타내는 pPrev는

nullptr로 나타납니다. 첫 번째 노드니까 이전 노드가

존재하지 않아 그렇겠죠.

 

 

pNext로 가 보니 

 

2라는 값이 있는 두 번째 노드가 나오는군요.

 

 

두 번째 노드의 pPrev로 가 보니 

 

1이 대입되어 있는 첫 번째 노드를 가리키고 있는 것이 보입니다.

 

 

두 번째 노드의 pNext로 가 보니

 

3이 대입되어 있는 세 번째 노드가 나옵니다.

 

 

세 번째 노드의 pPrev로 가 보니

 

2가 대입된 두 번째 노드가 나오는 것을 확인할 수 있습니다.

 

 

또한 세 번째 노드의 pNext로 가 보니

 

nullptr이 대입되어 있어 메모리를 읽을 수 없네요.

마지막 노드이기 때문에 다음 노드가 존재하지 않아서

그렇겠죠?

 

 

다시 객체 list로 돌아가 pTail로 가 보니

 

3이 대입된 마지막 노드를 가리키고 있습니다.

 

 

강의 출처 : https://www.youtube.com/watch?v=PFc4g8mxOiI&list=PL4SIC1d_ab-aOxWPucn31NHkQvNPHK1D1&pp=iAQB

---