list.cc

day77_1187669327.zip

#include <iostream>
using namespace std;

typedef int T;
class List{
	struct Node{
		T data;
		Node* next;
		Node(const T& d):data(d),next(NULL)
		{}
	};
	Node* head;
	int len;
public:
	List():head(NULL),len(0){}
	~List(){clear();}
	void clear(){
		while(head!=NULL){
			Node* p=head->next;
			delete head;
			head = p;
		}
		len = 0;
	}
	void travel(){
		Node* p=head;
		while(p!=NULL){
			cout << p->data << ' ';
			p = p->next;
		}
		cout << endl;
	}
	Node*& getp(int pos){
		if(pos<0||pos>len)
			pos = 0;
		if(pos==0)
			return head;
		Node* p=head;
		for(int i=1; i<pos; i++)
			p = p->next;
		return p->next;
	}
	void insert(const T& d, int pos=0){
		Node* p=new Node(d);
		p->next = getp(pos);
		getp(pos) = p;
		++len;
	}
	int find(const T& d){
		int pos=0;
		Node* p=head;
		while(p!=NULL){
			if(p->data==d)
				return pos;
			p = p->next;
			++pos;
		}
		return -1;
	}
	void update(const T& od, const T& nd){
		int pos=find(od);
		if(pos==-1)
			return;
		getp(pos)->data = nd;
	}
	void erase(const T& d){
		int pos=find(d);
		if(pos==-1)
			return;
		Node* p=getp(pos);
		getp(pos)=p->next;
		delete p;
		--len;
	}
	int size(){return len;}
	bool empty(){return head==NULL;}
	T getHead(){
		if(empty())
			return T();
		return head->data;
	}
	T getTail(){
		if(empty())
			return T();
		return getp(len-1)->data;
	}
};
int main()
{
	List ol;
	ol.insert(10,0);
	ol.insert(20,0);
	ol.insert(30,ol.size());
	ol.travel();
	ol.update(10, 100);
	ol.update(20, 200);
	ol.update(30, 300);
	ol.travel();
	ol.erase(300);
	ol.erase(20);
	ol.travel();
}