#include <iostream>
using namespace std;

//节点类
class Node {
	public:
		int data;
		Node* next;//后继
		Node* prev; //前驱
		Node() {
			cout<<"节点被创建！"<<endl;
		}
		~Node() {
			cout<<"节点被销毁！"<<endl;
		}
};

//双向链表
class LinkedList {
	private:
		Node* head;
		Node* tail;
		int length;

	public:
		LinkedList(int length);//构造方法
		~LinkedList();//析构方法
		void display();//正向遍历
		void reverseDisplay();//逆向遍历
		int getLength();//获取长度
		void sortList();//冒泡排序
		void changeList(int position,int num);//修改指定位置的节点
		void insertList(int position,int num);//插入节点
		void clearList();//清空
		void deleteList(int position);//删除指定位置的节点
		Node* getNode(int position);//查找指定位置的节点
};

//构造方法的实现
LinkedList::LinkedList(int length) {
	this->length = length;//链表长度
	head = new Node();//头结点
	head->prev = NULL;//头结点没有前驱
	tail = head;

	//读入这些元素
	for(int i = 0; i < length; i++) {
		Node* temp = new Node();
		cout<<"请输入第"<<(i + 1)<<"个节点的值："<<endl;
		cin>>temp->data;
		temp->next = NULL;
		temp->prev = tail;
		tail->next = temp;
		tail = temp;
	}
}

//析构方法
LinkedList::~LinkedList() {
	Node* p = head->next;
	while(head) {
		p = head->next;
		delete head;
		head = p;
	}

}

//正向遍历
void LinkedList::display() {
	cout<<"正向遍历链表：";
	Node* p = head->next;
	while(p) {
		cout<<p->data<<" ";
		p = p->next;
	}

	cout<<endl;
}

//逆向遍历
void LinkedList::reverseDisplay() {
	cout<<"逆向遍历链表：";
	Node*p = tail;
	while(p->prev) {
		cout<<p->data<<" ";
		p = p->prev;
	}

	cout<<endl;
}

//获取链表长度
int LinkedList::getLength() {
	return length;
}

//冒泡排序
void LinkedList::sortList() {
	//排序轮数
	int i,j,t;
	Node *p,*q;
	for(i = 1; i < length; i++) {
		for(j = 1; j < length - i + 1; j++) {
			p = getNode(j);
			q = getNode(j + 1);

			if(p->data > q->data) {
				t = p->data;
				p->data = q->data;
				q->data = t;
			}
		}
	}
}

//修改链表中指定位置的值
void LinkedList::changeList(int position,int num) {
	Node* p = head->next;
	if(position > length || position <= 0) {
		cout<<"越界异常"<<endl;
	} else {
		//找到需要修改值的节点
		for(int i = 1; i <= position - 1; i++) {
			p = p->next;
		}

		p->data = num;
	}
}

//插入数据
void LinkedList::insertList(int position,int num) {
	Node* p = head->next;
	if(position <= 0 || position > length) {
		cout<<"下标越界"<<endl;
	} else {
		//找到待插入的节点
		for(int i = 1; i < position; i++) {
			p = p->next;
		}

		Node* node = new Node();
		node->data = num;//要插入的节点

		node->next = p;
		node->prev = p->prev;
		p->prev->next = node;
		p->prev = node;

		length++;
	}
}

//清空数据
void LinkedList::clearList() {
	Node *p = head;
	while(head) {
		p = head->next;
		delete head;
		head = p;
	}
}

//删除指定位置的节点
void LinkedList::deleteList(int position) {
	Node* p = head->next;

	if(position < 0 || position > length) {
		cout<<"下标越界"<<endl;
	} else {
		for(int i = 1; i < position; i++) {
			p = p->next;
		}

		if(p == tail) {
			tail = p->prev;
			p->prev->next = NULL;
		} else {
			p->prev->next = p->next;
			p->next->prev = p->prev;
		}
		delete p;

		length--;

	}
}

//获取第i个节点
Node* LinkedList::getNode(int position) {
	Node *p = head->next;
	if(position < 0 || position > length) {
		cout<<"数组越界"<<endl;
		return NULL;
	} else {
		for(int i = 1; i < position; i++) {
			p = p->next;
		}

		return p;
	}
}

int main() {
	int n;
	cout<<"请输入链表的长度："<<endl;
	cin>>n;
	LinkedList* list = new LinkedList(n);
	list->display();
	list->reverseDisplay();
	cout<<"链表长度为："<<list->getLength()<<endl;
	list->changeList(3,123);
	list->display();
	list->insertList(2,234);
	list->display();
	list->deleteList(3);
	list->display();

	Node *p = list->getNode(2);
	cout<<"第2个节点的值为："<<p->data<<endl;

	list->sortList();
	list->display();

	delete list;
	return 0;
}
