#include <bits/stdc++.h>
using namespace std;

// 双向链表结点定义
struct Node
{
	int data;	// 数据域
	Node *prev;	// 前驱指针
	Node *next;	// 后继指针

	//构造函数
	Node(int x = 0): data(x), prev(nullptr), next(nullptr) {};
};

// 双向链表类
class DLinkList
{
	private:
		Node *head;  // 头结点，不存储有效数据
	public:
		DLinkList()	// 1.初始化链表
		{
			head = new Node();
			head->prev = nullptr;
			head->next = nullptr;
		}
		~DLinkList()// 析构释放内存
		{
			clear();
			delete head;
		}

		// ===================== 核心操作 =====================
		void createList(int arr[], int n);        // 头插法建表（原方法）
		void createListTail(int arr[], int n);    // 尾插法建表（新增）
		void insertAfter(Node *pos, int x);       // 指定节点后插入
		void insertBefore(Node *pos, int x);      // 指定节点前插入
		void delNode(Node *cur);                  // 删除指定节点
		Node *find(int x);                        // 查找值为x的节点
		void traverse();                          // 遍历输出
		int getLength();                          // 获取长度
		void clear();                             // 清空链表
		Node *getHead();                          // 获取头结点
};


void DLinkList::createList(int arr[], int n)
{
	this->clear();
	for (int i = 0; i < n; i++)
		insertAfter(head, arr[i]);
}

void DLinkList::createListTail(int arr[], int n)
{
	this->clear();
	Node *tail = head;
	for (int i = 0; i < n; i++)
	{
		insertAfter(tail, arr[i]);
		tail = tail->next;
	}
}

void DLinkList:: traverse()
{
	Node *p = head->next;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

void DLinkList::clear()
{
	Node *p = head->next, *q;
	while (p)
	{
		q = p->next;
		delete p;
		p = q;
	}
	head->next = nullptr;
}

void DLinkList::insertAfter(Node *pos, int x)
{
	if (!pos)
		return;
	Node *newNode = new Node(x);
	newNode->next = pos->next;
	newNode->prev = pos;

	if (pos->next)
		pos->next->prev = newNode;
	pos->next = newNode;
}

void DLinkList::insertBefore(Node *pos, int x)
{
	if (!pos)
		return;
	insertAfter(pos->prev, x);
}

void DLinkList::delNode(Node *cur)
{
	if (!cur || cur == head)
		return;
	if (cur->prev)
		cur->prev->next = cur->next;
	if (cur->next)
		cur->next->prev = cur->prev;
	delete cur;
}

Node *DLinkList::find(int x)
{
	Node *p = head->next;
	while (p)
	{
		if (p->data == x)
			return p;
		p = p->next;
	}
	return nullptr;
}

int DLinkList::getLength()
{
	int len = 0;
	Node *p = head->next;
	while (p)
	{
		len++;
		p = p->next;
	}
	return len;
}

Node *DLinkList::getHead()
{
	return head;
}

int main()
{
	DLinkList list;
	int a[] = {1, 2, 3, 4, 5};
	int n = 5;
	//list.createList(a, n);
	list.createListTail(a, n);

	cout << "链表：";
	list.traverse();

	cout << "长度：";
	cout << list.getLength() << endl;

	Node *pos = list.find(3);
	list.insertAfter(pos, 9);
	list.insertBefore(pos, 8);

	cout << "插入后：";
	list.traverse();

	list.delNode(pos);
	cout << "删除后";
	list.traverse();

	list.clear();
	cout << "清空后长度：" << list.getLength() << endl;

	return 0;
}