链表

 #include <iostream>
#include <iterator>
using namespace std;
template<typename T>
class Node{
 public:
 T key;
 Node<T>* prev;
 Node<T>* next;
 Node(const T& theKey, Node<T>* p=nullptr, Node<T>* n=nullptr);
 ~Node(){}
};
template<typename T>
Node<T>::Node(const T& theKey, Node<T>* p, Node<T>* n)
          :key(theKey),
     prev(p),
           next(n)
{
 //
}
template<typename t>
class List{
 private:
  Node<t>* head;
  void destroy(Node<t>* n);
  public:
   List();
   ~List();
   void destroy();//销毁链表. 
   Node<t>* search(const t& k);//搜索链表内的元素.
   Node<t>* insert(const t& k);//返回插入的节点. 
   void listDelete(const t& k);
   void print();
};
template<typename t>
List<t>::List()
        :head(nullptr)
{
 //
}
template<typename t>
List<t>::~List()
{
 destroy();
}
template<typename t>
void List<t>::destroy()
{
 destroy(head);
}
template<typename t>
void List<t>::destroy(Node<t>* n)
{
 if(n == nullptr) return;
 
 if(n->prev != nullptr) destroy(n->prev);
 
 if(n->next != nullptr) destroy(n->next);
 delete n;
 n=nullptr;
}
template<typename t>
Node<t>* List<t>::search(const t& k)
{
 Node<t>* temp = this->head;
 while(temp != nullptr && temp->key != k){
  temp=temp->next;
 }
 
 return temp;
}
template<typename t>
Node<t>* List<t>::insert(const t& k)
{
 Node<t>* x=new Node<t>(k);//创建一个新的节点. 
 x->next=head;//另该节点的下一个节点等于链表的头. 
 
 if(head != nullptr){
  head->prev=x;
 }
 head=x;
 x->prev=nullptr;
 return x;
}
template<typename t>
void List<t>::listDelete(const t& k)
{
 Node<t>* temp=this->head;
 
 while(head != nullptr && head->key != k){
  temp=head->next;
 }
 
 (temp->prev)->next=temp->next;//另被删除的节点的父节点的next=被删除节点的下一个节点. 
 (temp->next)->prev=temp->prev;
 
 delete temp;
}
template<typename t>
void List<t>::print()
{
 Node<t>* temp=head;
 while(temp != nullptr){
  cout<<temp->key<<endl;
  temp=temp->next;
 }
 
}
int main()
{
 List<int> MyList;
 MyList.insert(int(10));
 MyList.print();
 Node<int>* p=MyList.search(int(10));
 cout<<p->key;
 return 0;
}

你可能感兴趣的