#ifndef _SINGLYLINKEDLIST_
#define _SINGLYLINKEDLIST_
using namespace std;
template <class T>
class SinglyLinkedList;
template <class T>
class ChainNode
{
friend class SinglyLinkedList<T>;
private:
T data;
ChainNode<T>* link;
public:
/* constructor */
ChainNode() {}
ChainNode(const T& data) {this->data = data;}
ChainNode(const T& data, ChainNode<T> *link) {this->data = data; this->link = link;}
};
template <class T>
class SinglyLinkedList
{
private:
ChainNode<T> *first;
public:
/* constructor */
SinglyLinkedList() { first = 0; }
/* destructor */
~SinglyLinkedList();
/* method */
bool IsEmpty() const { return first == 0;} // 리스트가 empty인지 확인한다
int SearchofIndex(const T& theElement) const; // 리스트의 원소를 조사해 인덱스를 출력
void Delete(int theIndex); // 리스트의 index번째 원소를 제거한다.
T DeleteFront(); // 리스트의 첫 원소를 제거하고 제거되는 원소를 반환한다.
void Insert(int theIndex, const T& theElement); // 리스트의 index번째에 원소를 추가한다.
T GetElement(int theIndex); // 리스트의 index번째 원소를 가져온다.
int GetLength() const; // 리스트의 전체 길이를 가져온다.
void ShowLinkedList(); // 전체 리스트를 출력한다.
};
template <class T>
SinglyLinkedList<T>::~SinglyLinkedList()
{
// Deleted All nodes in LinkedList
while(first != NULL) {
ChainNode<T> *next = first->link;
delete first;
first = next;
}
}
template <class T>
int SinglyLinkedList<T>::SearchofIndex(const T& theElement) const
{
// search the chain for the Element
ChainNode<T>* currentNode = first;
int index = 0; // index of currentNode
for(int index = 0;index<GetLength();index++) {
if(currentNode->data == theElement)
return index;
currentNode = currentNode->link;
}
return -1;
}
template <class T>
T SinglyLinkedList<T>::DeleteFront()
{
T item;
if(this->IsEmpty() == true)
item = (T)-1;
else {
cout<<"!"<<endl;
item = first->data;
ChainNode<T> * deleteNode = first;
first = first->link;
delete deleteNode;
}
return item;
}
template <class T>
void SinglyLinkedList<T>::Delete(int theIndex)
{
// Deleted the chain of index;
ChainNode<T>* deleteNode = first;
if(theIndex < 0)
throw "Bad insert Index";
if(first == 0)
throw "Cannot delete from empty chain";
if(theIndex == 0) {
first = first->link;
}
else {
ChainNode<T>* bfDeleteNode = first;
for(int i=0; i<theIndex-1; i++) { //moving the index
bfDeleteNode = bfDeleteNode->link;
}
if(bfDeleteNode == NULL)
throw "Delete element does not exist";
deleteNode = bfDeleteNode->link;
bfDeleteNode->link = bfDeleteNode->link->link;
}
delete deleteNode;
}
template <class T>
void SinglyLinkedList<T>::Insert(int theIndex, const T& theElement)
{
// Inserted the chain of index;
ChainNode<T> *bfInsertNode = first;
if(theIndex < 0)
throw "Bad insert Index";
if(theIndex == 0) { // Insert at front
first = new ChainNode<T>(theElement,first);
}
else
{
for(int i=0; i<theIndex-1; i++) { //moving the index
bfInsertNode = bfInsertNode->link;
}
bfInsertNode->link = new ChainNode<T>(theElement,bfInsertNode->link);
}
}
template <class T>
T SinglyLinkedList<T>::GetElement(int theIndex)
{
T element;
ChainNode<T>* currentNode = first;
if(theIndex < 0)
throw "Bad insert Index";
for(int i=0; i<theIndex; i++) { //moving the index
if(currentNode == NULL) {
cout<<"Bad insert Index"<<endl;
return (T)-1;
}
currentNode = currentNode->link;
}
element = currentNode->data;
return element;
}
template <class T>
int SinglyLinkedList<T>::GetLength() const
{
int count = 0;
ChainNode<T>* searchNode = first;
for(int i=0; searchNode != NULL; i++) {
count ++;
searchNode = searchNode->link;
}
return count;
}
template <class T>
void SinglyLinkedList<T>::ShowLinkedList()
{
cout<<"Current State : first ";
for(int i=0; i<GetLength();i++) {
cout<<GetElement(i)<<" ";
}
}
#endif
