将值插入链表前面并返回类对象

Question

所以我有以下课程:

template <class T>
class List : public ContainerIfc <T> {
public:
    List();
    ~ List();
    List(const List&);
    List <T>& operator = (List&);
    List <T>& pushFront(T);
    List <T>& pushBack(T);
    List <T>& popFront(T&);
    List <T>& popBack(T&);
    int getSize();
    bool isEmpty();
    T front();
    T back();
    T& operator [](int);
private:
    Node<T> *head;
};

和以下节点:

template <class T>
class Node {
public:
    T data;
    Node<T> *next;
    Node(T e) {
        data = e;
        next = NULL;
    }
};

我想编写一个pushFront函数,它将值添加到链表的前面.我已经有了以下代码.我无法弄清楚的是如何让它返回一个List对象.我认为我的函数可以正常工作,它只是不会返回List.关于如何做到这一点的任何想法？

template <class T>
List <T>& List<T>::pushFront(T n){

    Node<T> *temp = new Node<T>(n);
    temp->next = head;



}

Answer 1

这里有几个问题.首先,您永远不会直接更新指向您添加的新节点.

其次,就返回List对象引用而言 - 您有隐含参数,this即指向您当前正在修改的对象的指针.只需返回其解除引用:

template <class T>
List <T>& List<T>::pushFront(T n){

    Node<T> *temp = new Node<T>(n); //Create a new node
    temp->next = head; //point its next to the current head
    head = temp; //Update head so our node is front of the list

    return *this; //Return a reference of ourself
}

最后,在您的Node构造函数中,请注意NULL(有关更多信息,请参见此处).

另外,作为一个快速的旁边 - 你实现链接列表的方式,你应该小心成员函数back(),push_back()和pop_back().鉴于您只有一个头指针,这些操作中的每一个都需要您遍历整个列表(这称为O(n)运行时).这可能不是小列表上的问题,但随着您的列表变大,这将变得越来越糟.

您会注意到,在广泛使用的库(如C++标准库)中,通常根本无法实现那些无效的函数(请参阅向量,注意缺少的push/pop_front).您可以通过添加尾部指针并更改为双向链接列表来解决此问题,但当然这会使您的所有其他功能更加复杂.在一天结束时,这是一个权衡.