# linked list


---

### The Template Class ChainNode
:::spoiler **code**

template<class T>
class ChainNode
{
   friend class Chain;
   public:
   ChainNode(T element=0,ChainNode *next=0)
   {
       data=element;link=next;
   }
    private:
    T data;
    ChainNode *link;
}

:::
### The Template Class Chain
:::spoiler **code**

template<class T>
class Chain
{
   public:
      Chain() {first = 0;} 
         // constructor, empty chain
      ~Chain(); // destructor
      bool IsEmpty() const {return first == 0;}
      // other methods defined here
   private:
      ChainNode<T>* first; 
};
 

:::
### The Destructor
:::spoiler **code**

template<class T>
chain<T>::~chain()
{// Chain destructor. Delete all nodes 
 // in chain.
   while (first != NULL)
   {// delete first
      ChainNode<T>* next = first->link;
      delete first;
      first = next;
   }
}

:::

---
### Delete An Element
### **(1)deleteNode先存要被刪除節點的位置**
### **(2)first指向下一個位置**
### **(3)刪除節點**

### Delete(2)
### **(1)(2)將beforeNode的link指向後兩個位置(d)的link**
### **(3)刪除節點**
:::spoiler **code**

template<class T>
void Chain<T>::Delete(int theIndex)
{
	ChainNode<T>* deleteNode;
	if (theIndex == 0)
	{// remove first node from chain
		deleteNode = first;
		first = first->link;
	}
	else
	{  // use p to get to beforeNode
		ChainNode<T>* p = first;
		for (int i = 0; i < theIndex - 1; i++)
		{
			if (p == 0)
				throw "Delete element does not exist";
			p = p->link;
		}
		deleteNode = p->link;
		p->link = p->link->link;
	}
	delete deleteNode;
}

:::

---

### One-Step Insert(0,’f’)
### **(1)新增一節點data=f，link指向first指向的位置**
### **(2)first指向新節點**

### Two-Step Insert(3,’f’)
### **(1)新增一節點data=f，link指向d**
### **(2)c指向新節點f**
:::spoiler **code**

void Insert(int theIndex,const T& theElement)
{
	if (theIndex < 0)
		throw "Bad insert index";
	if (theIndex == 0)
		// insert at front
		first = new ChainNode<T>(theElement, first);
	else
	{  // find predecessor of new element
		ChainNode<T>* p = first;
		for (int i = 0; i < theIndex - 1; i++)
		{
			/*if (p == 0)
				throw "Bad insert index";*/
			p = p->link;
		}
		// insert after p
		p->link = new ChainNode<T>(theElement, p->link);
	}
}

:::

---

:::spoiler **entire code**

#include<iostream>
using namespace std;
template<class T>class Chain;
template<class T>
class ChainNode
{
	friend class Chain<T>;
public:
	ChainNode(T data1, ChainNode<T>* link1) :data(data1), link(link1) {}
private:
	T data;
	ChainNode* link;
};
template<class T>
class Chain
{
private:
	ChainNode<T>* first;
public:
    Chain() { first = 0; }
	~Chain()
	{
		while (first != NULL)
		{
			ChainNode<T>* next = first->link;
			delete first;
			first = next;
		}

	}
    bool IsEmpty() const { return first == 0; }
	int IndexOf(const T& theElement) const
	{
		ChainNode<T>* currentNode = first;
		int index = 0; 
		while (currentNode != NULL && currentNode->data != theElement)
		{
			currentNode = currentNode->link;
			index++;
		}
		if (currentNode == NULL)
			return -1;
		else
			return index;
	}
	void Delete(int theIndex)
	{
		/*if (first == 0)
			throw "Cannot delete from empty chain";*/
		ChainNode<T>* deleteNode;
		if (theIndex == 0)
		{// remove first node from chain
			deleteNode = first;
			first = first->link;
		}
		else
		{  // use p to get to beforeNode
			ChainNode<T>* p = first;
			for (int i = 0; i < theIndex - 1; i++)
			{
				if (p == 0)
					throw "Delete element does not exist";
				p = p->link;
			}
			deleteNode = p->link;
			p->link = p->link->link;
		}
		delete deleteNode;
	}
    void Insert(int theIndex,const T& theElement)
	{
		if (theIndex < 0)
			throw "Bad insert index";

		if (theIndex == 0)
			// insert at front
			first = new ChainNode<T>(theElement, first);
		else
		{  // find predecessor of new element
			ChainNode<T>* p = first;
			for (int i = 0; i < theIndex - 1; i++)
			{
				/*if (p == 0)
					throw "Bad insert index";*/
				p = p->link;
			}
			// insert after p
			p->link = new ChainNode<T>(theElement, p->link);
		}
	}
	void ChainList()
	{

		if (first == 0) {                      // 如果first node指向NULL, 表示list沒有資料
			cout << "List is empty.\n";
			return;
		}

		ChainNode<T> *current = first;             // 用pointer *current在list中移動
		while (current != 0) {                 // Traversal
			cout << current->data << " ";
			current = current->link;
		}
		cout << endl;
	}
};
int main()
{
	Chain<char> a;
	a.Insert(0,'a');
	a.Insert(1,'b');
	a.Insert(2,'c');
	cout << a.IndexOf('a') << endl;
	a.ChainList();
	a.Delete(1);
	a.ChainList();
	a.Insert(0, 'd');
	a.ChainList();
}

:::