# 【数据结构】动态单链表

#include <iostream>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
template<class T>
struct Node
{
T data;
Node<T> *next_pos;
};

template<class T>
{
public:
T Get(int i);
int Locate(T x);
void Insert(T x,int i);
T Delete(int i);
void PrintList();
int length();
private:
Node<T> *first,*p,*s;
};

template<class T>
{
first = new Node <T>;
first->next_pos = NULL;
}

template<class T>
{
first = new Node<T>;
first->next_pos = NULL;
for (int i = 0; i < n; i++)
{
p = new Node<T>;
p->data = arr[i];
p->next_pos = first->next_pos;
first->next_pos = p;
}
/*尾插法
first = new Node<T>;
first->next_pos = NULL;
p = first;
for (int i = 1; i <= n; i++)
{
s = new Node<T>;
s->data = arr[i];
s->next_pos = NULL;
p->next_pos = s;
p = p->next_pos;
}*/
}

template<class T>
{
p = first->next_pos;
for (int i = 0; i < n - 1 && p != NULL; i++)
{
p = p->next_pos;
}
return p == NULL ? -1 : p->data;
}

template<class T>
{
p = first->next_pos;
int count = 1;
while (p!=NULL)
{
if (p->data == x)
{
return count;
}
}
return p == NULL ? -1 : p->data;
}

template<class T>
{
p = first->next_pos;
int count = 1;
while (p!=NULL && count <= i-1)
{
p = p->next_pos;
count++;
}
if (p == NULL) throw "error";
else {
s = new Node<T>;
s->data = x;
s->next_pos = p->next_pos;
p->next_pos = s;
}
}

template<class T>
{
p = first->next_pos;
int count = 0;
while (p != NULL && count < i - 1)
{
p = p->next_pos;
count++;
}
if (p == NULL||p->next_pos == NULL) throw "error";
else {
s = p->next_pos;
p->next_pos = p->next_pos->next_pos;
T ans=s->data;
delete s;
return ans;
}

}

template<class T>
{
p=first->next_pos;
while (p != NULL)
{
cout << p->data << " ";
p = p->next_pos;
}
cout << endl;
}

template<class T>
{
p = first->next_pos;
long long int count = 0;
while (p != NULL)
{
p = p->next_pos; count++;
}
return count;
}
int main()
{
int a[9999];
for (int i = 0; i < 100; i++)
a[i] = i;