연결 리스트(LinkedList) - C++

후기. C로 짤때는 쉬웠던 것이 template과 객체 지향 등 C++의 문법들을 생각하면서 짜보니 쉽지 않았다.

특히 C에서는 맘대로 구조 변형하고 그랬던 것이 C++에서는 에러로 돌아왔다.. ㅋㅋ;

결국 다시 윤성우 책을 곰곰히 보면서 정석대로 다시 작성했다.

이전 선형리스트와는 다르게 분할해서 코딩하였다.

지금 약간 주먹구구식으로 짜고 있는 것 같아서 지금 부른 C++ primer plus를 보면서 C++의 특성에 대해서 다시한번 점검해볼 필요가 있어보인다.

혹시 코드를 본다면 단순 참고용으로만 확인하는게 좋을 것..

 

LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H


template
<typename T>

class List
{
private :
	typedef struct Node_
	{
		T data;
		Node_* next;
	}Node;

	Node* head;
	int numOfData;
	Node* cur;
	Node* before;
	T (*Func)(T a, T b);

public :

	List()
	{
		head = (Node*)malloc(sizeof(Node));
		head->next = nullptr;
		cur = nullptr;
		before = nullptr;
		Func = nullptr;
		numOfData = 0;
	}

	void LInsert(T data);

	void FInsert(T data);

	void SInsert(T data);

	bool LFirst(T& data);

	bool LNext(T& data);

	T LRemove();

	int LCount();

	void SetSortRule(T (*comp)(T a, T b));
};

#endif

 

LinkedList.cpp

#include  "LinkedList.h" 

template
<typename T>
	void List<T>::LInsert(T data)
	{
	if (Func == nullptr)
	{
		FInsert(data);
	}
	else
		SInsert(data);
	}

template
<typename T>
void List<T>::FInsert(T data)
{

	Node* NewNode = (Node*)malloc(sizeof(Node));
	if (NewNode == nullptr)
	{
		return;
	}
	NewNode->data = data;
	NewNode->next = head->next;
	head->next = NewNode;

	numOfData++;
}
template
<typename T>
int List<T>::LCount()
{
	return numOfData;
}

template
<typename T>
void List<T>::SInsert(T data)
{
	Node* NewNode = (Node*)malloc(sizeof(Node));
	NewNode->data = data;
	Node* pred = head; // 저장 위치 탐색을 위한 포인터

	while (pred->next != nullptr && Func(pred->next->data, data) != 1) //Func 1번 인수가 앞서면 1, 아니면 0
	{
		pred = pred->next;
	}

	NewNode->next = pred->next;
	pred->next = NewNode;

	numOfData++;
}


	template
	<typename T>
	bool List<T>::LFirst(T& data)
	{
		if (head->next == nullptr)
		{
			return false;
		}

		cur = head->next;
		before = head;
		data = cur->data;
		return true;
		
	}
	template
	<typename T>
	bool List<T>::LNext(T& data)
	{
		if (cur->next == nullptr)
		{
			return false;
		}

		before = cur;
		cur = cur->next;
		data = cur->data;

		return true;

	}

	template
	<typename T>
	T List<T>::LRemove()
	{
		T rdata = cur->data;
		Node* rpos = cur;


		before->next = cur->next;
		cur = before;
		
		free(rpos);
		numOfData--;
		return rdata;

	}

	template
	<typename T>
	void List<T>::SetSortRule(T(*comp)(T a, T b))
	{
		Func = comp;
	}

main.cpp

#include <iostream>
using namespace std;

#include "LinkedList.cpp"

template
<typename T>
void PrintList(List<T>& LinkedList)
{
	int a;
	if (LinkedList.LFirst(a) == false)
	{
		cout << "리스트가 존재하지 않습니다." << endl;
	}
	else
	{
		cout << a << " ";
		while (LinkedList.LNext(a) == true)
		{
			cout << a << " ";
		}
	}
}

int WhoIsPreced(int a, int b)
{
	if (a > b)
	{
		return 1; // a가 앞선다.
	}
	else
		return 0; // b가 앞선다.
}

int main()
{
	List<int> LinkedList;

	cout << "생존 확인" << endl;

	PrintList(LinkedList);

	LinkedList.LInsert(1);
	LinkedList.LInsert(2);
	LinkedList.LInsert(3);
	LinkedList.LInsert(4);
	LinkedList.LInsert(5);

	PrintList(LinkedList);
	
	cout << endl;

	int a;

	LinkedList.LFirst(a);

	cout << LinkedList.LRemove() << endl;

	LinkedList.LFirst(a);
	LinkedList.LNext(a);

	cout << LinkedList.LRemove() << endl;

	PrintList(LinkedList);

	cout << endl;

	LinkedList.LFirst(a);

	cout << LinkedList.LRemove() << endl;

	LinkedList.LFirst(a);

	cout << LinkedList.LRemove() << endl;

	LinkedList.LFirst(a);

	cout << LinkedList.LRemove() << endl;

	LinkedList.SetSortRule(WhoIsPreced);

	LinkedList.LInsert(1);
	LinkedList.LInsert(2);
	LinkedList.LInsert(3);
	LinkedList.LInsert(4);
	LinkedList.LInsert(5);

	PrintList(LinkedList);

	return 0;
}