记录数据结构链表学习过程（手写list）
#include <iostream> #include<bits/stdc++.h> using namespace std; typedef int Rank; template<typename T> struct ListNode{ T data; //数据域 ListNode<T> *prev;//前驱 ListNode<T> *next;//后继 ListNode() {}; //默认构造 ListNode(T e,ListNode p=NULL,ListNode q=NULL):data(e),prev(p),next(q) {}//带参构造(方便赋值) }; template<typename T> class List_Link{ private: int _size; //元素个数 ListNode<T> *head; //头指针 ListNode<T> *tail; //尾指针 void init(); //初始化 public: List_Link(){init();}//默认构造 ~List_Link(); //析构 T& operator [] (Rank ) const; //重载[]运算符 Rank size() const {return _size;} //大小 bool empty() const {return _size<=0;}//判断是否为空 void clear(); //清空 ListNode<T>* getHead(){return head;} //返回头节点 ListNode<T>* getTail(){return tail;} //返回尾节点 ListNode<T>* insert_prev(ListNode<T> *,int ); //头插法 ListNode<T>* insert_next(ListNode<T> *,int ); //尾插法 T erase(ListNode<T> *); //删除 ListNode<T>* find(T const& )const; //查找 }; template<typename T> T& List_Link<T>::operator[] (Rank r)const{ ListNode<T> *p=head->next; while(0<r--){ p=p->next; } return p->data; } template<typename T> void List_Link<T>::init(){ head=new ListNode<T>; tail=new ListNode<T>; head->prev=NULL; head->next=tail; tail->prev=head; tail->next=NULL; _size=0; } template<typename T> ListNode<T>* List_Link<T>::insert_prev(ListNode<T> *p,int e){ ListNode<T> *temp=new ListNode<T>; temp->data=e; temp->prev=p->prev; temp->next=p; p->prev->next=temp; p->prev=temp; _size++; return temp; } template<typename T> ListNode<T>* List_Link<T>::insert_next(ListNode<T> *p,int e){ ListNode<T> *temp=new ListNode<T>; temp->data=e; temp->prev=p; temp->next=p->next; p->next->prev=temp; p->next=temp; _size++; return temp; } template<typename T> T List_Link<T>::erase(ListNode<T> *p){ p->next->prev=p->prev; p->prev->next=p->next; T e=p->data; delete p; _size--; return e; } template<typename T> void List_Link<T>::clear(){ while(0<_size--){ erase(head->next); } } template<typename T> List_Link<T>::~List_Link(){ clear(); delete head; delete tail; } template<typename T> ListNode<T>* List_Link<T>::find(T const& e)const{ ListNode<T> *p=head; int n=_size; while(0<n--){ if(e == (p=p->next)->data) return p; } return NULL; } int main(){ List_Link<int> L; ListNode<int> *h=L.getHead(); for(int i=0;i<10;i++){ L.insert_next(h,i); h=h->next; } for(ListNode<int> *p=L.getHead()->next;p!=L.getTail();p=p->next)cout<<p->data<<" "; cout<<endl; cout<<L.size()<<endl; L.erase(L.find(5)); cout<<L.size()<<endl; for(ListNode<int> *p=L.getHead()->next;p!=L.getTail();p=p->next)cout<<p->data<<" "; cout<<endl; cout<<L.empty()<<endl; L.clear(); cout<<L.empty()<<endl; return 0; }效果展示
