C++实现双向循环链表
本文最后更新于 35 天前,其中的信息可能已经有所发展或是发生改变。

上次用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++;
}

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

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

先看前两个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);
未经允许禁止转载本站内容,经允许转载后请严格遵守CC-BY-NC-ND知识共享协议4.0,代码部分则采用GPL v3.0协议
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇