双链表创建、删除、添加节点

骑猪看日落 2021-12-16 07:41 230阅读 0赞

## 双链表创建、删除、添加节点 ##

--------------------

#include<queue>
    #include<iostream>
    using namespace std;
    // 有序链表
    const int arrrlens = 9;
    int arr[arrrlens] = { 0, 1, 2, 3, 5, 6, 7, 8, 9 };
    
    class Node {
    public:
    	Node(int el = 0, Node* pNext = NULL, Node * pPre = NULL) {
    		data = el;
    		next = pNext;
    		pre = pPre;
    	}
    	int data;
    	Node* next, *pre;
    };
    class NodeList {
    public:
    public:
    	NodeList() {
    		head = new Node();
    		tail = new Node();
    	}
    	~NodeList() {
    		delete head;
    		delete tail;
    	}
    	int initList();
    	int addElem(int);
    	int delElem(int);
    	int printList();
    private:
    	Node* head, *tail;
    };
    int NodeList::initList()
    {
    	Node* p = head;
    	for (int i = 0; i < arrrlens; i++)
    	{
    		Node* node = new Node(arr[i]);
    		p->next = node;
    		node->pre = p;
    		p = node;
    	}
     
    	return 0;
    }
    int NodeList::addElem(int node)
    {
    	Node* p = head, *cur = NULL;
    	Node* newnode = new Node(node);
    	// 越过头节点
     
    	while (p->next != NULL && p->next->data <= node)
    		p = p->next;
    	if (p->next != NULL)
    	{
    		newnode->next = p->next;
    		newnode->pre = p;
    		p->next->pre = newnode;
    		p->next = newnode;
    		cout << "从中间插入节点..." << endl;
    		return 1;
    	}
    	else {
    		p->next = newnode;
    		newnode->pre = p;
    		cout << "从尾部插入节点..." << endl;
    		return 1;
    	}
    	
    	return 0;
    }
    int NodeList::delElem(int node)
    {
    	Node* p = head, * q, *cur;
    	// 越过头节点
    	p = p->next;
    	while (p != NULL && p->data != node)
    		p = p->next;
    	if(p != NULL && p->next != NULL)
    	{ 
    		p->pre->next = p->next;
    		p->next->pre = p->pre;
    		cout << "从中间删除节点..." << endl;
    		return 1;
    	}
    	if (p != NULL && p->next == NULL)
    	{
    		p->pre->next = NULL;
    		cout << "从尾部删除节点..." << endl;
    		return 1;
    	}
    	cout << "该节点不存在..." << endl;
    	return 0;
    }
    int NodeList::printList()
    {
    	Node* p = head;
    	// 越过头节点
    	p = p -> next;
    	while (p != NULL)
    	{
    		cout << p->data << " ";
    		p = p->next;
    	}
    	cout << endl;
    	return 0;
    }
    int main()
    {
    	NodeList list;
    	list.initList();
    	list.printList();
    	list.addElem(31);
    	list.printList();
    	list.addElem(2);
    	list.printList();
    	list.delElem(31);
    	list.printList();
    	list.delElem(3);
    	list.printList();
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70]: /images/20211214/6c2a1c65464d47e0a5f887a5a4716c13.png