Implementing doubly linked list

Question

I have been given the framework to implement a doubly linked list. I am stumped on the PushFront() method. The method should add the provided element to the front of the linked list and it should return the address to the new head node.

I am confused about how to access the current head of the list so I can assign it to the pNext pointer.

The PushFront() method looks like this so far:

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 class constructor:

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

Data class:

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

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

Main:

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

My understanding is that you would typically provide the address of the head when calling PushFront(), however since I am not provided that I am unsure of how I can access it.

Rubber Duckie wants to know what you plan on using Element* d for. Just to get the data out of it? There has to be a better use for it or you'd just pass in the data. — user4581301
– user4581301, Commented Sep 24, 2021 at 20:13
pList is the head of the list. Inside the PushFront method, pList is referred to as this. — user3386109
– user3386109, Commented Sep 24, 2021 at 20:17
I think you are conflating the linked list with the links in the list. Element looks like it should be a link. It should not know what a head is because the only things a link should know is what other links it's been attached to and the data it contains. A Link might be a head, but it shouldn't know that. The head is a detail only the linked list should know. Similar with PushFront. A Link shouldn't have a front. It's just got a prev and next, so perhaps an insert_before and an insert_after. The linked list, that has a front. — user4581301
– user4581301, Commented Sep 24, 2021 at 20:23
Sometimes the jester in me fights to come out... so my apologies for this remark: Is the name of the class "leaky c++ 101"? :) If Element*p is passed into PushFront(), then you could as well write in main: ... Element (Data("Cam", 12345, "Testing1")); And then pass the address of the automatic variable. Which in turn would render destruction, removal etc. nigh impossible to implement :) — BitTickler
– BitTickler, Commented Sep 24, 2021 at 20:38

Vlad from Moscow · Accepted Answer · 2021-09-24 20:35:48Z

1

Using your approach to the list definition the function can look the following way

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

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

    return newElement;
}

Though such a declaration of the function does not make a great sense. The function should be declared at least like

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

instead of

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

Or even like

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

Pay attention to that it is much better to declare one more data structure that indeed will represent the doubly-linked list and that will contain pointers to the first (head) and the last (tail) objects of the type Element in the list.

edited Sep 24, 2021 at 20:35

answered Sep 24, 2021 at 20:19

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

trincot · Accepted Answer · 2021-09-25 10:29:50Z

I am confused about how to access the current head of the list

As you call the PushFront method on the pList instance, the this reference will be pList, which is assumed to be the head of the list. The main program is responsible for maintaining a reference to the head.

Note that sometimes another class is created for representing the list, which then has a head member. However, in this case, you seem not to have such a class, and the main program must manage the head itself, i.e. pList.

The PushFront method must then "help" the main program in doing this, and return the reference to the new head. So don't return nullptr.

I don't really understand why in PushFront you create a new Element, since you already get an element passed as argument. I would think the purpose is to add that element to the list, and not a copy of it.

So:

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

In the main program I would suggest creating both Element instances with new, so that their memory management is the same:

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

Collectives™ on Stack Overflow

Implementing doubly linked list

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related