123-C++用类来实现双向链表

1.用类来实现双向链表

#include 
using namespace std;

//要求：用C++类来实现双向链表

class Node
{
private:
	int _val;
	Node* _next;
	Node* _pre;
public:
	//构造函数
	Node(int val = int())
		:_val(val), _next(nullptr)
	{}

	//拷贝构造函数
	Node(const Node& src)
		:_val(src._val), _next(src._next),_pre(nullptr)
	{}

	//等号运算符重载
	Node& operator = (const Node& src)
	{
		if (this == &src)
		{
			return *this;
		}

		_val = src._val;
		_next = src._next;
		_pre = src._pre;
		
		return *this;
	}

	//设置_val的值
	void set_val(int val)
	{
		_val = val;
	}

	//设置_next的值
	void set_next(Node* next)
	{
		_next = next;
	}

	//设置_pre的值
	void set_pre(Node* pre)
	{
		_pre = pre;
	}

	//获取_val的值
	int get_val()
	{
		return _val;
	}

	//获取_next的值
	Node* get_next()
	{
		return _next;
	}

	//获取_pre的值
	Node* get_pre()
	{
		return _pre;
	}
};

class List
{
private:
	Node* _head;
	Node* _tail;
public:
	typedef Node LIST_NODE_TYPE;
	//构造函数
	List()
	{
		cout << "List()" << endl;
		_head = new LIST_NODE_TYPE();
		_tail = _head;
	}

	//析构函数
	~List()
	{
		cout << "~List()" << endl;
		while (!empty())
		{
			pop_front();
		}
		delete _head;
		_head = _tail = nullptr;
	}

	//拷贝构造函数
	List(const List& src)
	{
		_head = new LIST_NODE_TYPE();
		_tail = _head;

		LIST_NODE_TYPE* p = src._head->get_next();
		while (p != nullptr)
		{
			push_back(p->get_val());
		}
	}
	
	//等号运算符重载
	List& operator = (const List& src)
	{
		if (this == &src)
		{
			return *this;
		}
		
		while (!empty())
		{
			pop_front();
		}

		LIST_NODE_TYPE* p = src._head->get_next();
		while (p != nullptr)
		{
			push_back(p->get_val());
		}

		return *this;
	}

	//头插
	void push_front(int val)
	{
		LIST_NODE_TYPE* p = new LIST_NODE_TYPE(val);
		p->set_next(_head->get_next());//和后面连接
		_head->set_next(p);//和前面相连
		if (p->get_next() != nullptr)
		{
			p->get_next()->set_pre(p);//和后面相连
		}
		p->set_pre(_head);//和前面相连
	}

	//尾插
	void push_back(int val)
	{
		LIST_NODE_TYPE* p = new LIST_NODE_TYPE(val);

		_tail->set_next(p);//前面连接
		p->set_pre(_tail);
		_tail = p;
	}

	//头删
	void pop_front()
	{
		if (empty())
		{
			return;
		}

		LIST_NODE_TYPE* p = _head->get_next();
		if (p->get_next() != nullptr)
		{
			p->get_next()->set_pre(_head);
		}
		else
		{
			_tail = _head;
		}
		_head->set_next(p->get_next());

		delete p;
	}

	//尾删
	void pop_back()
	{
		if (empty())
		{
			return;
		}

		LIST_NODE_TYPE* p = _tail;
		_tail->get_pre()->set_next(_tail->get_next());
		_tail = _tail->get_pre();
		delete p;
	}

	//返回第二个元素的值
	int back()
	{
		return _tail->get_val();
	}

	//返回第一个元素的值
	int front()
	{
		return _head->get_next()->get_val();
	}

	//打印
	void show()
	{
		LIST_NODE_TYPE* p = _head->get_next();
		while (p != nullptr)
		{
			cout << p->get_val() << "->";
			p = p->get_next();
		}
		cout << endl;
	}

	//判空
	bool empty()
	{
		//如果头指针==尾指针，说明为空
		return _head == _tail;
	}
};

//测试
//--------------------------------测试----------------------------------

#include 
#include "mylist.h"
using namespace std;

int main()
{
	List plist;
	for (int i = 0; i < 5; i++)
	{
		plist.push_back(i);//尾插
	}
	plist.show();
	for (int i = 5; i < 10; i++)
	{
		plist.push_front(i);//头插
	}
	plist.show();

	cout << plist.front() << endl;//打印第一个元素的值
	cout << plist.back() << endl;//打印第二个元素的值

	for (int i = 0; i < 5; i++)
	{
		plist.pop_back();//尾删
	}
	plist.show();
	for (int i = 5; i < 10; i++)
	{
		plist.pop_front();//头删
	}
	plist.show();

	return 0;
}

2.用链表实现栈

#pragma once
#include "mylist.h"

//用链表实现栈
class Stack
{
public:
	Stack()
	{}
	~Stack()
	{}
	int top()
	{
		return _list.front();
	}
	void pop()
	{
		_list.pop_front();
	}
	void push(int val)
	{
		_list.push_front(val);
	}
	bool empty()
	{
		return _list.empty();
	}
private:
	List _list;
};

3.用链表实现队列

#pragma once
#include "mylist.h"

//用链表实现队列
class Queue
{
public:
	Queue()
	{}
	~Queue()
	{}
	int top()
	{
		return _queue.front();
	}
	void pop()
	{
		_queue.pop_front();
	}
	void push(int val)
	{
		_queue.push_back(val);
	}
	bool empty()
	{
		return _queue.empty();
	}
private:
	List _queue;
};