实施双链接列表

Question

我已经得到了实现双向链表的框架。我被PushFront（）方法难住了。方法应该将提供的元素添加到链表的前面，并且应该将地址返回到新的头节点。我对如何访问列表的当前头部感到困惑，以便我可以将其分配给pNext指针。到目前为止，PushTop（）方法看起来是这样的：

Element* Element::PushFront(Element* d){
   Element* newElement = new Element(Data());    // Allocate space for new element
   newElement->ElementData = d->ElementData;    // Assign ElementData to the new  element                
   newElement->pNext = // Head address
   newElement->pPrev = NULL;
return nullptr;
}

元素类构造函数：

Element::Element(Data d){
   ElementData = d;
   pNext = NULL;
   pPrev = NULL;
}

数据类：

Data::Data(){
Name = "Unknown";
SN = 0;
Program = "Unknown";
}

Data::Data(string NameStr, unsigned int sNumber, string Prog) :
Name(NameStr), SN(sNumber), Program(Prog) {};

主要：

Element* pList = new Element(Data("Cam", 12345, "Testing1"));   
Element newE(Data("Bob", 335567, "Testing2"));
pList = pList->PushFront(&newE);

我的理解是，您通常会在调用PushFron（）时提供头的地址，但是因为我没有提供，我不确定如何访问它。

Answer 1

我对如何访问当前列表的头部感到困惑

当您在pList实例上调用PushTop方法时，这个引用将是pList，它被假定为列表的头部。主程序负责维护对头部的引用。

请注意，有时会创建另一个类来表示列表，然后该列表有一个head成员。然而，在这种情况下，您似乎没有这样一个类，主程序必须管理头部本身，即pList。

然后，PushFront方法必须“帮助”主程序执行此操作，并将引用返回到新头部。所以不要返回nullptr。

我真的不明白为什么在PushFront中创建一个新的元素，因为您已经获得了一个作为参数传递的元素。我认为目的是将该元素添加到列表中，而不是它的副本。

因此：

Element* Element::PushFront(Element* d){
   d->pNext = this;
   d->pPrev = NULL;
   return d;
}

在主程序中，我建议使用new创建两个Element实例，以便它们的内存管理相同：

Element* pList = new Element(Data("Cam", 12345, "Testing1"));   
Element* newE = new Element(Data("Bob", 335567, "Testing2"));
pList = pList->PushFront(newE);

Answer 2

使用列表定义的方法，函数可以如下所示

Element * Element::PushFront( Element *d )
{
    Element *newElement = new Element( d->ElementData );

    newElement->pNext = this;
    newElement->pPrev = this->pPrev;
    this->pPrev = newElement;

    return newElement;
}

尽管这样的函数声明意义不大。函数应至少声明为

Element * Element::PushFront( const Data &d );

而不是

Element * Element::PushFront( Element *d );

甚至像

Element * Element::PushFront( const char *Name, unsigned int SN, const char *Program );

请注意，最好再声明一个数据结构，它实际上将表示双链接列表，并包含指向列表中type元素的第一个（head）和最后一个（tail）对象的指针。