【数据结构】动态单链表

#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>
class LinkedList
{
public:
  LinkedList();
  LinkedList(T arr[], int n);
  ~LinkedList() {};
  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>
LinkedList<T>::LinkedList()
{
  first = new Node <T>;
  first->next_pos = NULL;
}

template<class T>
LinkedList<T>::LinkedList(T arr[], int n) 
{
  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>
T LinkedList<T>::Get(int n)
{
  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>
int LinkedList<T>::Locate(T x)
{
  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>
void LinkedList<T>::Insert(T x,int i)
{
  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>
T LinkedList<T>::Delete(int i)
{
  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>
void LinkedList<T>::PrintList()
{
  p=first->next_pos;
  while (p != NULL)
  {
    cout << p->data << " ";
    p = p->next_pos;
  }
  cout << endl;
}


template<class T>
int LinkedList<T>::length()
{
  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;
  LinkedList<int> ab(a, 10);
  ab.PrintList();
  ab.Insert(100, 2);
  ab.PrintList();
  cout << ab.length() << endl;
  cout << ab.Get(2) << endl;
  ab.Delete(2);
  ab.PrintList();
  cout << ab.length() << endl;
  cout << ab.Get(2) << endl;
  ab.PrintList();
}