双向循环链表类封装实例C++代码实现

快来打我* 2023-01-12 10:12 133阅读 0赞

node.h

#pragma once
    /*
    * 节点类型。三个成员分别是：指向前一个节点的指针，元素本身，指向后一个节点的指针。
    */
    class Node {
        
    public:
    	int element;
    	Node *next;
    	Node *previous;
    	Node(int element, Node *next, Node *previous) {
        
    		this->element = element;
    		this->next = next;
    		this->previous = previous;
    	}
    };

linkedlist.h

#include "node.h"
    struct LinkedList {
        
    	LinkedList();
    	void addFirst(int);
    	void addLast(int);
    	void add(int index, int element);
    	int getFirst();
    	int getLast();
    	int get(int);
    	int removeFirst();
    	int removeLast();
    	int remove(int);
    	void iterate();
    private:
    	Node *header;
    	int size;
    };

linkedlist.cpp

#include "linkedlist.h"
    #include <iostream>
    using std::cout;
    /*
    * 构造方法。
    * 生成一个空的节点介于表头和表尾之间，初始前后指针都指向自己。
    */
    LinkedList::LinkedList() {
        
    	header = new Node(NULL, NULL, NULL);
    	header->next = header;
    	header->previous = header;
    	size = 0;
    }
    /*
    * 在链表头部添加一个元素。
    * 生成一个新的节点，向前指向空节点，向后指向原来空节点的下一个节点，即原来的第一个节点。
    * 空节点向后指向此节点，原来的第一个节点向前指向此节点。
    */
    void LinkedList::addFirst(int i) {
        
    	header->next = new Node(i, header->next, header);
    	header->next->next->previous = header->next;
    	++size;
    }
    /*
    * 在链表最后添加一个元素。
    * 生成一个新的节点，向前指向原来空节点的前一个节点，即原来的最后一个节点，向后指向空节点。
    * 原来的最后一个节点向后指向此节点，空节点向前指向此节点。
    */
    void LinkedList::addLast(int i) {
        
    	header->previous = new Node(i, header, header->previous);
    	header->previous->previous->next = header->previous;
    	++size;
    }
    /*
    * 在指定的索引前插入一个元素。0 <= 索引 <= 链表长度。
    * 如果索引值小于链表长度的一半，向后（正向）迭代获取索引值位置的节点，反之则向前（反向）。
    * 生成一个新的节点，向前指向原来这个位置的节点的前一个节点，向后指向原来这个位置的节点。
    * 原来这个位置的节点的前一个节点向后指向此节点，原来这个位置的节点向前指向此节点。
    * （在指定的索引删除一个元素实现方法类似）
    */
    void LinkedList::add(int index, int i) {
        
    	if (index > size || index < 0) {
        
    		cout << "Exception in add(): Index out of bound." << '\n';
    		return;
    	}
    	Node *entry;
    	if (index < size / 2) {
        
    		entry = header->next;
    		for (int i = 0; i < index; ++i)
    			entry = entry->next;
    	}
    	else {
        
    		entry = header;
    		for (int i = size; i > index; --i)
    			entry = entry->previous;
    	}
    	entry->previous->next = new Node(i, entry, entry->previous);
    	entry->previous = entry->previous->next;
    	++size;
    }
    /*
    * 获取链表第一个元素。
    * 空节点向后指向的节点即是第一个元素。
    */
    int LinkedList::getFirst() {
        
    	if (!size)
    		cout << "Exception in getFirst(): List is empty." << '\n';
    	return header->next->element;
    }
    /*
    * 获取链表最后一个元素。
    * 空节点向前指向的节点即是最后一个元素。
    */
    int LinkedList::getLast() {
        
    	if (!size)
    		cout << "Exception in getLast(): List is empty." << '\n';
    	return header->previous->element;
    }
    /*
    * 删除并返回链表第一个元素。
    * 链表第二个节点向前指向空节点，空节点向后指向第二个节点。
    */
    int LinkedList::removeFirst() {
        
    	int remove = header->next->element;
    	header->next->next->previous = header;
    	header->next = header->next->next;
    	--size;
    	return remove;
    }
    /*
    * 删除并返回链表最后一个元素。
    * 链表倒数第二个节点向后指向空节点，空节点向前指向倒数第二个节点。
    */
    int LinkedList::removeLast() {
        
    	int remove = header->previous->element;
    	header->previous->previous->next = header;
    	header->previous = header->previous->previous;
    	--size;
    	return remove;
    }
    /*
    * 用来输出所有元素的迭代方法。
    */
    void LinkedList::iterate() {
        
    	if (!size) {
        
    		cout << "Exception in iterate(): List is empty." << '\n';
    		return;
    	}
    	for (Node *entry = header->next; entry != header; entry = entry->next)
    		cout << entry->element << " ";
    	cout << '\n';
    }

#include"linkedlist.h"	
    #include<iostream>
    
    using namespace std;
    
    int main()
    {
        
    	LinkedList c;
    	c.addFirst(5);
    	c.addFirst(4);
    	c.addLast(3);
    	c.iterate();
    
    	system("pause");
    	return 0;
    }

[如何用C++实现双向循环链表][C]

[C]: https://www.jb51.net/article/37555.htm