C++实现双向循环链表 – LovelyCat的小站

本文最后更新于 44 天前，其中的信息可能已经有所发展或是发生改变。

上次用C语言写了一个简单链表：C语言实现双向链表，这次用C++实现一个双向循环链表，主要是因为C++支持类与泛型。

List接口

依然按照接口的设计原则，先写一个通用的List：

template<class T, class NodeType>
class List {
public:
    virtual void add(T value) = 0;
    virtual void add(T value, int position) = 0;
    virtual T get(int position) = 0;
    virtual NodeType* getNode(int position) = 0;
    virtual void remove(int position) = 0;
    virtual int getSize() = 0;

protected:
    int size = 0;
    void checkIndexOutOfRange(int index) {
        if (index < 0 || (index >= this->size && this->size > 0)) {
            throw IndexOutOfRangeException(this->size, index);
        }
    }
};

这个接口要求实现add、get等基本方法，现在按照这个接口，来写一个LinkedList类。

先准备一个结构体用来作为链表的元素：

template<class T>
struct LinkedListItem {
    LinkedListItem<T>* pre = nullptr;
    LinkedListItem<T>* next = nullptr;
    T value;
};

LinkedList类

template<class T>
class LinkedList : public List<T, LinkedListItem<T>> {
private:
    LinkedListItem<T>* head = nullptr;
    LinkedListItem<T>* tail = nullptr;
public:
    bool isRecursive = false;
    void setRecursive(bool recursive);

public:
    /* Implements of List.h */
    void add(T value);
    void add(T value, int position);
    T get(int position);
    LinkedListItem<T>* getNode(int position);
    void remove(int position = 0);
    int getSize();

public:
    explicit LinkedList(bool recursive = false) {
        this->setRecursive(recursive);
    }

    explicit LinkedList<T>(T headValue) {
        this->add(headValue);
    }
    ~LinkedList() = default;

    void addAll(LinkedList<T> newList);
};

在这个类中，保存了头部尾部节点的指针以及实现了List接口的方法。

另外，这个类还提供了一个额外的addAll方法用于合并两个链表。

函数实现

插入

template<class T>
void LinkedList<T>::add(T value) {
    this->add(value, this->getSize() - 1 < 0 ? 0 : this->getSize() - 1);
}

template<class T>
void LinkedList<T>::add(T value, int position) {
    this->checkIndexOutOfRange(position);

    auto* item = new LinkedListItem<T>;
    item->value = value;

    if (this->getSize() == 0) {
        // Empty insert
        this->head = item;
        this->tail = this->head;
    } else if (position == this->getSize() - 1) {
        // Tail insert
        item->next = nullptr;
        item->pre = this->tail;
        this->tail->next = item;
        this->tail = item;
    } else {
        // Insert
        LinkedListItem<T>* targetNode = getNode(position);
        LinkedListItem<T>* preNode = targetNode->pre;

        item->next = targetNode;
        targetNode->pre = item;
        if (position == 0) {
            this->head = item;
        } else {
            preNode->next = item;
            item->pre = preNode;
        }
    }

    if (isRecursive) {
        this->head->pre = this->tail;
        this->tail->next = this->head;
    }

    this->size++;
}

这个函数用于将某个元素插入到某个位置之前，但有两种特殊情况：

空链表没有任何元素，不能插入一个新元素到任何一个现有元素之前
当插入的位置等于链表尾部时，应该把新元素添加到链表尾部而不是插入到尾部元素之前

先看前两个if判断，第一个if判断链表是否为空，向空链表添加元素，即将其直接设置为头元素。

第二个if判断是否为尾部，并且将其插入到尾部，并重置新的尾元素。

最后一个if用于判断是否是循环链表，因为循环链表的头尾相接，插入元素的操作可能会影响头尾元素，这时就需要及时更新头尾元素的pre与next指针了。

第一个add方法就很好理解了，实际上就是直接把元素插入到尾部。

获取元素

template<class T>
T LinkedList<T>::get(int position) {
    return getNode(position)->value;
}

template<class T>
LinkedListItem<T>* LinkedList<T>::getNode(int position) {
    this->checkIndexOutOfRange(position);

    bool flag = position < this->getSize() / 2;

    LinkedListItem<T>* cursor = flag ? this->head : tail;
    int count = flag ? position : this->getSize() - position - 1;

    for (int i = 0; i < count; i++) {
        cursor = flag ? cursor->next : cursor->pre;
    }

    return cursor;
}

这一段写得比较抽象，主要是双向链表遍历可以从头部或者尾部开始。

flag用于判断从哪个方向开始遍历，依据是目标位置是否大于链表长度的一半。

删除

template<class T>
void LinkedList<T>::remove(int position) {
    this->checkIndexOutOfRange(position);

    LinkedListItem<T>* targetNode = getNode(position);
    LinkedListItem<T>* preNode = targetNode->pre;
    LinkedListItem<T>* nextNode = targetNode->next;

    if (position == 0) {
        // Remove head node
        this->head = nextNode;
        this->head->pre = isRecursive ? this->tail :nullptr;
    } else if (position == this->getSize() - 1) {
        // Remove tail node
        this->tail = preNode;
        if (isRecursive) {
            this->head->pre = this->tail;
            this->tail->next = this->head;
        } else {
            this->tail->next = nullptr;
        }
    } else {
        preNode->next = nextNode;
        nextNode->pre = preNode;
    }

    this->size--;
}

同样地，删除元素也需要考虑删除的位置是头部尾部还是中间，不同情况做不同处理即可。

设置循环链表

template<class T>
void LinkedList<T>::setRecursive(bool recursive) {
    this->isRecursive = recursive;

    if (this->head != nullptr){
        this->head->pre = isRecursive ? this->tail : nullptr;
    }

    if (this->tail != nullptr) {
        this->tail->next = isRecursive ? this->head : nullptr;
    }
}

通过这一方法可以将链表设置为循环链表，也可以取消其循环，主要是对头尾元素的pre、next指针进行操作。

合并链表

template<class T>
void LinkedList<T>::addAll(LinkedList<T> newList) {
    LinkedListItem<T>* cHead = newList.head;
    LinkedListItem<T>* cTail = newList.tail;

    this->tail->next = cHead;
    cHead->pre = this->tail;

    this->tail = cTail;

    // Update new list size
    this->size += newList.getSize();

    // Update recursive status
    this->setRecursive(this->isRecursive);
}

这个方法将newList合并到当前链表，需要考虑当前链表的尾部与元素长度的变化。

链表测试

下面来测试一下可用性，先写一个通用的方法用来打印链表元素：

template<class T>
static void printLinkedList(LinkedList<T> list) {
    for (int i = 0; i < list.getSize(); i++) {
        LinkedListItem<int>* item = list.getNode(i);
        cout << "read: " << item->value << " pre: " << item->pre << " ptr: " << item << " next: " << item->next << endl;
    }
}

创建两种双向链表

cout << "+ Create recursive linked list" << endl;
LinkedList<int> recursiveList(true);
recursiveList.add(1);
printLinkedList(recursiveList);

cout << "+ Create recursive linked list" << endl;
LinkedList<int> list(false);
list.add(2);
printLinkedList(list);

元素的相关操作

cout << "+ Init recursive linked list, elements: {1, 2, 3, 4, 5}" << endl;
LinkedList<int> recursiveList(true);
recursiveList.add(1);
recursiveList.add(2);
recursiveList.add(3);
recursiveList.add(4);
recursiveList.add(5);
printLinkedList(recursiveList);
cout << "+ Insert head, value 111" << endl;
recursiveList.add(111,0);
printLinkedList(recursiveList);
cout << "+ Remove head" << endl;
recursiveList.remove(0);
printLinkedList(recursiveList);
cout << "+ Remove tail" << endl;
recursiveList.remove(recursiveList.getSize() - 1);
printLinkedList(recursiveList);
cout << "+ Insert before index 2, value 999" << endl;
recursiveList.add(999,2);
printLinkedList(recursiveList);

链表合并

cout << "+ Init recursive linked list, elements: {1, 2, 3, 4, 5}" << endl;
LinkedList<int> recursiveList(true);
recursiveList.add(1);
recursiveList.add(2);
recursiveList.add(3);
recursiveList.add(4);
recursiveList.add(5);
printLinkedList(recursiveList);
cout << "+ Init linked list2, elements: {4, 3, 2, 1}" << endl;
LinkedList<int> newList(false);
newList.add(4);
newList.add(3);
newList.add(2);
newList.add(1);
printLinkedList(newList);
cout << "+ Merge 2 linked list by addAll()" << endl;
recursiveList.addAll(newList);
printLinkedList(recursiveList);