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

struct DoublyListNode
{
	int data;            // 数据域
	DoublyListNode *prev; // 指向前驱节点
	DoublyListNode *next; // 指向后继节点

	DoublyListNode(int x) : data(x), prev(nullptr), next(nullptr) {}
};

DoublyListNode *DoublyList_create(int n);
void DoublyList_print(DoublyListNode *head);
DoublyListNode *DoublyList_find(DoublyListNode *head, int target);
bool DoublyList_insert_after(DoublyListNode *pos, int val);
DoublyListNode *DoublyList_delete_pos(DoublyListNode *pos);
int main()


{
	int n = 5, m = 3;

	//输入12345
	DoublyListNode *head = DoublyList_create(n);
	DoublyList_print(head);

	//在3之后插入99
	DoublyListNode *pos = DoublyList_find(head, m);
	DoublyList_insert_after(pos, 99);
	DoublyList_print(head);

	//删除99
	pos = DoublyList_find(head, 99);//查找99的位置
	head = DoublyList_delete_pos(pos);
	DoublyList_print(head);
	return 0;
}

DoublyListNode *DoublyList_create(int n)
{
	if (n <= 0)
		return nullptr;

	DoublyListNode *dummy = new DoublyListNode(0);
	DoublyListNode *tail = dummy;

	for (int i = 0; i < n; i++)

	{
		int data;
		cin >> data;
		tail->next = new DoublyListNode(data);
		tail->next->prev = tail;
		tail = tail->next;
	}

	DoublyListNode *head = dummy->next;
	head->prev = NULL;
	delete dummy;

	return head;
}

void DoublyList_print(DoublyListNode *head)
{
	if (head == nullptr)
	{
		cout << "空链表" << endl;
		return;
	}

	DoublyListNode *current = head;
	while (current->next)
	{
		cout << current->data << " -> ";
		current = current->next;
	}
	cout << current->data << endl;
}

DoublyListNode *DoublyList_find(DoublyListNode *head, int target)
{
	if (head == nullptr)
		return nullptr;

	DoublyListNode *current = head;
	while (current)
	{
		if (current->data == target)
			return current;
		current = current->next;
	}

	return nullptr;
}

bool DoublyList_insert_after(DoublyListNode *pos, int val)
{
	if (pos == nullptr)
		return false;

	DoublyListNode *p = new DoublyListNode(val);
	p->next = pos->next;
	p->prev = pos;
	p->next->prev = pos;
	pos->next = p;

	return true;
}

DoublyListNode *DoublyList_delete_pos(DoublyListNode *pos)
{
	if (pos == nullptr)
		return nullptr;
	
	//如果要删除的是头节点，则需要修改头节点
	if(pos->prev == nullptr)
	{
		DoublyListNode * newhead = pos->next;
		newhead->prev = nullptr;
		delete pos;
		return newhead;
	}
	
	

}