c++实现双链表的操作

曾经终败给现在 2022-03-16 10:46 239阅读 0赞

/*********************************定义*********************************/
    struct Data
    {
    	int id;
    	string name;
    	int age;
    	Data() : id(0), age(0) { }
    	Data(int i, string n, int a) : id(i), name(n), age(a) {}
    };
    
    struct Node
    {
    /*********************************定义*********************************/
    	Data data;
    	Node* prev;
    	Node* next;
    	Node() : prev(nullptr), next(nullptr) { }
    	Node(Data d, Node* p, Node* n) : data(d), prev(p), next(n) {}
    };
    /*********************************无参构造*********************************/
    class List
    {
    	Node* head;
    	Node* tail;
    	int len;
    public:
    	List() : head(nullptr), tail(nullptr), len(0) {
    		cout << "List 0" << endl;
    	}
    	/*********************************链表创建*********************************/
    	List(int n) : head(nullptr), tail(nullptr)
    	{
    		cout << "List " << len << endl;
    		Node* p = nullptr;
    		len = n<0 ? 0 : n;
    		for (int i=0; i<n; i++) {
    			p = new Node;
    			if (i == 0) {
    				head = tail = p;
    			} else {
    				tail->next = p;
    				p->prev = tail;
    				tail = p;
    			}
    		}
    	}
    	/*********************************初始化*********************************/
    	List(const List& l) : head(nullptr), tail(nullptr), len(0){
    		Node* p = l.head;
    		for (int i=0; i<l.len; i++) {
    			insert_back(p->data);
    			p = p->next;
    		}
    	}
    	/*********************************链表析构*********************************/
    	~List() {
    		Node* p = head;
    		cout << "delete " << endl;
    		while(p) {
    			cout << "delete " << p->data.id << endl;
    			head = head->next;
    			delete p;
    			p = head;
    		}
    	}
    	/*********************************前插*********************************/
    	void insert_front(Data d) {
    		head = new Node(d, nullptr, head);
    		if (len == 0) {
    			tail = head;
    		} else {
    //		p->next = head;
    //		head->prev = p;
    //		head = p;
    			head->next->prev = head;
    		}
    		len++;
    	}
    	/*********************************尾插*********************************/
    	void insert_back(Data d) {
    		Node* p = new Node(d, tail, nullptr);
    		if (len == 0) {
    			head = tail = p;
    		} else {
    			tail->next = p;
    			tail = p;
    		}
    		len++;
    	}
    	/*********************************头删除*********************************/
    	void delete_front() {
    		if (len == 0)
    			return;
    		if (len == 1) {
    			delete head;
    			head = tail = nullptr;
    		} else if (len > 1) {
    			Node *p = head->next;
    			delete head;
    			head = p;
    			head->prev = nullptr;
    		}
    		len--;
    	}
    	/*********************************尾删除*********************************/
    	void delete_back() {
    		if (len == 0)
    			return;
    		if (len == 1) {
    			delete tail;
    			head = tail = nullptr;
    		} else if (len > 1) {
    			Node* p = tail->prev;
    			delete tail;
    			tail = p;
    			tail->next = nullptr;
    		}
    		len--;
    	}
    	/*********************************id查找*********************************/
    	Node* search_by_id(int id) {
    		Node* p = head;
    		while(p) {
    			if (p->data.id == id)
    				return p;
    			p = p->next;
    		} 
    		return nullptr;
    	}
    	/*********************************通过id删除*********************************/
    	bool remove_by_id(int id) {
    		Node* p = search_by_id(id);
    		if (p == nullptr)
    			return false;
    		else if (len == 1) {
    			delete p;
    			head = tail = nullptr;
    			len = 0;
    		} else if (p == head) {
    			head = head->next;
    			head->prev = nullptr;
    			delete p;
    			len--;
    		} else if (p == tail) {
    			delete_back();
    		} else {
    			p->next->prev = p->prev;
    			p->prev->next = p->next;
    			delete p;
    			len--;
    		}
    		return true;
    	}
    	/*********************************链表遍历*********************************/
    	void show() {
    		Node * p = head;
    		cout << "++++++front -> back++++++++++++++" << endl;
    		for (int i=0; i<len; i++) {
    			cout << p->data.id << " " << p->data.name 
    				<< " " << p->data.age << endl;
    			p = p->next;
    		}
    		cout << "------back -> front-----" << endl;
    		p = tail;
    		while(p) {
    			cout << p->data.id << " " << p->data.name 
    				<< " " << p->data.age << endl;
    			p = p->prev;	
    		}
    		cout << "========================" << endl;
    	}
    };