C++实现链表

/*关于链表如果感觉很迷惑就画图，这样理解起来会更容易
 *
 */

#include <iostream>
using namespace std;

typedef int T;
class List//链表类
{
	struct Node//节点类
	{
		T data;//节点里的数据
		Node* next;//指向下一个节点的指针
		Node(const T& d = T()):data(d), next(NULL){}//节点类的构造函数，零初始化
	};
	Node* head;//头指针用来保存头节点的地址，不是节点，也即指向第一个节点的指针
	int len;//链表的长度，从0开始
public:
	List ():head(NULL), len(0){}//链表的构造函数
	bool empty()const//判断链表是否为空
	{
		return head == NULL;
	}
	void push_front(const T& d)//前插，在链表的首部插入数据
	{
		Node* p = new Node(d);//动态创建链表中的节点，用数据d初始化节点，把地址赋给p。
							  //动态创建保证节点一直存在，如果用栈空间系统会自动释放
		p -> next = head;//新节点中的地址成员指向头指针所指的地方
		head = p;//头指针指向新节点
	}
	void travel()const//遍历链表
	{
		if(empty())
		{
			cerr << "链表为空！" << endl;
			return;
		}
		Node* p = head;//将头指针的值赋给p
		while(p != NULL)//只要p不等于NULL就表示没有到链表的结尾
		{
			cout << p->data << ' ';//输出节点里的数据
			p = p -> next;//让p指向下一个节点
		}
		cout << endl;
	}
	
	int size()const//节点个数
	{
		int cnt = 0;
		Node* p = head;
		while(p != NULL)
		{
			++cnt;//与遍历整个链表相似，只是这里使用计数器记录节点的个数
			p = p -> next;
		}
		return cnt;
	}
	void clear()//清空整个链表
	{
		while(head != NULL)//只要头指针没有为空，就表示链表中还有数据
		{
			Node* p = head->next;//定义一个临时指针暂存头指针指向节点里存储的下一个节点的地址
									// 如果不暂存，直接delete的话，那么下面的地址也无法获得
			delete head;//释放掉头指针所指的空间
			head = p;//让头指针再指向下一个节点的地址，以便重新来过
		}
		len = 0;//最后是链表的长度变为0
	}
	~List()//析构函数
	{
		clear();//释放所有动态申请的空间
	}
	Node*& getptr(int pos)//注意！！返回的是引用根据节点编号（从0到size（））获得指向该节点的原始地址并返回
	{
		if(pos < 0|| pos > size())//判断节点编号是否合法
			pos = 0;//如果不合法则将编号设置为0
		if(pos == 0)//如果位置为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)//根据位置插入节点
	{
		Node*& pn = getptr(pos);
		Node* p = new Node(d);
		p -> next = pn;
		pn = p;
	}
	List& push_back(const T& d)//尾插，返回的是调用该函数的对象，所以可以连续调用
	{
		insert(d, size());
		return *this;
	}
	/*void push_front(const T& d)//这样也可以
	{
	insert(d, 0);
	}*/
	void erase(int pos)//删除节点
	{
		if(pos < 0|| pos > size())
			return;
		Node*& pn = getptr(pos);
		Node* p = pn;
		pn = pn -> next;
		delete p;
		--len;
	}
	int find(const T& d)const//根据数据查找节点位置
	{
		Node* p = head;
		int pos = 0;
		while(p != NULL)
		{
			if(p->data == d)
				return pos;
			p = p -> next;
			++pos;
		}
		return -1;
	}
	void remve(const T& d)//根据节点数据删除节点
	{
		int pos;
		while((pos = find(d)) != -1)
			erase(pos);
	}
	void set(int pos, const T& d)//根据节点位置修改节点数据
	{
		if(pos < 0||pos > size())
			return;
		getptr(pos) -> data = d;
	}
	T front()const//返回首节点数据
	{
		if(empty())
			throw "空";
		return head -> data;
	}
	T back()//返回尾节点数据
	{
		if(empty())
			throw "空";
		Node*& p = getptr(size() - 1);//此处注意尾节点位置
		return p->data;
	}
};

int main()
{
	List l;
	l.push_front(10);
	l.push_front(20);
	l.push_front(30);
	l.push_front(11);
	l.push_front(22);
	l.travel();
	cout << "链表长度：" << l.size() << endl;
	cout << "链表头数据：" << l.front() << endl;
	cout << "链表尾数据：" << l.back() << endl;
	l.insert(1000, 2);
	l.travel();
	cout << "链表长度：" << l.size() << endl;
	cout << "链表头数据：" << l.front() << endl;
	cout << "链表尾数据：" << l.back() << endl;
	l.clear();
	l.travel();
	return 0;
}