C++

Forum

 
 
Doubly Linked Lists - Pushing to front of List and Printing Backwards

PiggiesGoSqueal (167)
Please Note: This is a homework assignment, however, it was due ~3 weeks ago and I'm only doing it for the learning aspect.

I'm trying to make the program push an element to the front of a doubly linked list then print backwards. The problem is it works for printing the list when starting at the beginning but not when starting at the end. What am I doing wrong?

Output: (I bolded the part that applies to this question)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
Traversing (forward) doubly linked list...
[ ]
Traversing (backward) doubly linked list...
[ ]

Pushing back 10 in doubly linked list...
Pushing back 20 in doubly linked list...
Pushing back 30 in doubly linked list...

Traversing (forward) doubly linked list...
[ 10 20 30 ]
Traversing (backward) doubly linked list...
[ 30 20 10 ]

Popping back doubly linked list (deleting the last one)...

Traversing (forward) doubly linked list...
[ 10 20 ]
Traversing (backward) doubly linked list...
[ 20 10 ]

Deleting front (first) node...

Traversing (forward) doubly linked list...
[ 20 ]
Traversing (backward) doubly linked list...
[ 20 ]

Now pushing 44 to the front...

Traversing (forward) doubly linked list...
[ 44 20 ]
Traversing (backward) doubly linked list...
[ 20 ]


Problem Function (I think):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
        // inserts an element to the beginning
        /*
        Algorithm Steps:
        1. Create a newNode pointer node and allocate new memory to it.
        2. Make newNode->next = head->next (the front node, not pointer)
            - Means the node after newNode is the old front node.
        3. Make newNode->prev = head
            - Has same result as NULL..
        4. Make newNode->data = data
        5. Replace the old head with the new head: Make head->next = newNode
        6. Make newNode->next->prev = newNode (so the node after newNode will have it's prev = newNode)
        */
        void push_front(int data) {
            // FIXME - Work In Progress
            Int_Node2 *newNode = new Int_Node2; // 1.
            newNode->next = head->next; // 2. | head->next is the ACTUAL front node. Head is just the pointer. I think(?) only this way for doubly linked lists?
            //newNode->prev = head; // 3.
            // ^ Have tried doing = NULL; as well. Same result.
            newNode->data = data; // 4.
            head->next = newNode; // 5. 
            head->next->prev = newNode; // 6.

            /*
            POPPING front Code (for comparison):
            Int_Node2 *temp = new Int_Node2;
            head = head->next; 
            head->prev = NULL;
            delete temp;
            */
        }



There are two files: Main.cpp and DoublyLinkedList.h

Main.cpp:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
#include <iostream>
#include <sstream> // stringstream
#include <cassert>
#include "DoublyLinkedList.h"

int main() {
    IntDoublyList iListDouble;
	
	std::cout << "Traversing (forward) doubly linked list...\n";
	iListDouble.traverseForward();
	std::cout << "Traversing (backward) doubly linked list...\n";
	iListDouble.traverseBackward();

	std::cout << "\nPushing back 10 in doubly linked list...\n";
	iListDouble.push_back(10);
	std::cout << "Pushing back 20 in doubly linked list...\n";
	iListDouble.push_back(20);
	std::cout << "Pushing back 30 in doubly linked list...\n";
	iListDouble.push_back(30);

	std::cout << "\nTraversing (forward) doubly linked list...\n";
	iListDouble.traverseForward();
	std::cout << "Traversing (backward) doubly linked list...\n";
	iListDouble.traverseBackward();

	std::cout << "\nPopping back doubly linked list (deleting the last one)...\n";
	iListDouble.pop_back();

	std::cout << "\nTraversing (forward) doubly linked list...\n";
	iListDouble.traverseForward();
	std::cout << "Traversing (backward) doubly linked list...\n";
	iListDouble.traverseBackward();

	std::cout << "\nDeleting front (first) node...\n";
	iListDouble.pop_front();

	std::cout << "\nTraversing (forward) doubly linked list...\n";
	iListDouble.traverseForward();
	std::cout << "Traversing (backward) doubly linked list...\n";
	iListDouble.traverseBackward();

	std::cout << "\nNow pushing 44 to the front...\n";
	iListDouble.push_front(44); // <--- **Problem Part**

	std::cout << "\nTraversing (forward) doubly linked list...\n";
	iListDouble.traverseForward();
	std::cout << "Traversing (backward) doubly linked list...\n";
	iListDouble.traverseBackward(); // <-- **Has problems here**

    return 0;
}


DoublyLinkedList.h: http://cpp.sh/7eaol


Help would be greatly appreciated, thanks!
keskiverto (10381)
head->next is the ACTUAL front node. Head is just the pointer.

Why? If 'head' were "just a pointer", then it would not have member 'next'.

Consider:
1
2
3
4
5
6
7
8
9
10
11
 
// empty list:
Node* head = nullptr;
Node* last = nullptr;

// create first node:
head = new Node( 42, nullptr, nullptr ); // value, prev, next
last = head;

// add another node (in front):
head = new Node( 7, nullptr, head );
head->next->prev = head;
PiggiesGoSqueal (167)
keskiverto wrote:
Why? If 'head' were "just a pointer", then it would not have member 'next'.

Consider:
1
2
3
4
5
6
7
8
9
10
11
 
// empty list:
Node* head = nullptr;
Node* last = nullptr;

// create first node:
head = new Node( 42, nullptr, nullptr ); // value, prev, next
last = head;

// add another node (in front):
head = new Node( 7, nullptr, head );
head->next->prev = head;

Thanks for your reply! That was a note to self and I meant it's a pointer from the class:
1
2
3
4
5
 
class IntDoublyList {
    private:
        Int_Node2 *head;
        Int_Node2 *tail;
        // etc..

Apologies for the confusion, I thought about removing my comments but figured it may be good to have you all see my thought process.


To clarify, I have a few questions:
Your code shows:
1
2
3
 
// empty list:
Node* head = nullptr;
Node* last = nullptr;


And my class shows:
1
2
3
4
5
 
class IntDoublyList {
    private:
        Int_Node2 *head;
        Int_Node2 *tail;
        size_t count;

1. I added = nullptr; to my code for *head & *tail, but what difference does it make?
2. Is nullptr the same as NULL but should always be used for pointers?
3. This is a constructor right?
head = new Node( 42, nullptr, nullptr ); // value, prev, next
I didn't realize (or maybe I forgot) this was possible, pretty neat!

- - -
Other than my questions above, your solution makes sense. Unfortunately, for some reason my new code is giving errors after I made the changes.

Errors:
1
2
3
4
5
6
7
 
In file included from Main.cpp:39:0:
DoublyLinkedList.h: In member function ‘void IntDoublyList::push_front(int)’:
DoublyLinkedList.h:73:34: error: expected primary-expression before ‘int’
             head = new Int_Node2(int data, nullptr, nullptr); // 1.
                                  ^~~
DoublyLinkedList.h:73:60: error: new initializer expression list treated as compound expression [-fpermissive]
             head = new Int_Node2(int data, nullptr, nullptr); // 1.

I looked it up and I know error: new initializer expression list treated as compound expression was because it didn't include a data type. So I added the int to data and that made 1 less error appear. But I don't know what datatype nullptr would be.

Main.cpp is the same.

DoublyLinkedList.h: http://www.cpp.sh/4yaerl
(The function is on line 71)
Last edited on
keskiverto (10381)
The nullptr has specific pointer type.
The NULL is a macro, like you would write .

It is (usually) a good habit to initialize variables, particularly pointers.


I wrote 42, not int 42.

You can either use aggregate initialization:
head = new Int_Node2 { data, nullptr, nullptr };
or provide a constructor:
1
2
3
4
5
6
7
8
9
10
 
struct Int_Node2 {
  int data;
  Int_Node2 *next;
  Int_Node2 *prev;
  Int_Node2( int d, Int_Node2* p, Int_Node2* n )
  : data( d ), next( n ), prev( p )
  {}
};

head = new Int_Node2( data, nullptr, nullptr );
PiggiesGoSqueal (167)
Thanks for your reply!

keskiverto wrote:
The nullptr has specific pointer type.
The NULL is a macro, like you would write .

Ah okay, I don't have a lot of experience with macros.

keskiverto wrote:
It is (usually) a good habit to initialize variables, particularly pointers.

Ah, I've heard a lot of different people say a lot of different things for this. I started doing things like int num = 0; or std::string str1 = "";, then people told me on the cplusplus forums that there's no need to do that because they are set to that by default. So I stopped doing that and now someone tells me it's a good habit. Haha..


keskiverto wrote:
I wrote 42, not int 42.

My response from above explained why I wrote int data rather than just data:
PiggiesGoSqueal wrote:
I looked it up and I know error: new initializer expression list treated as compound expression was because it didn't include a data type. So I added the int to data and that made 1 less error appear. But I don't know what datatype nullptr would be.

In other words, when I had it only has data another error appeared.

I removed the "int" from int data and got these errors:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
In file included from Main.cpp:39:0:
DoublyLinkedList.h: In member function ‘void IntDoublyList::push_front(int)’:
DoublyLinkedList.h:73:56: error: new initializer expression list treated as compound expression [-fpermissive]
             head = new Int_Node2(data, nullptr, nullptr); // 1.
                                                        ^
DoublyLinkedList.h:73:56: error: no matching function for call to ‘Int_Node2::Int_Node2(std::nullptr_t)’
DoublyLinkedList.h:8:8: note: candidate: Int_Node2::Int_Node2()
 struct Int_Node2 {
        ^~~~~~~~~
DoublyLinkedList.h:8:8: note:   candidate expects 0 arguments, 1 provided
DoublyLinkedList.h:8:8: note: candidate: constexpr Int_Node2::Int_Node2(const Int_Node2&)
DoublyLinkedList.h:8:8: note:   no known conversion for argument 1 from ‘std::nullptr_t’ to ‘const Int_Node2&’
DoublyLinkedList.h:8:8: note: candidate: constexpr Int_Node2::Int_Node2(Int_Node2&&)
DoublyLinkedList.h:8:8: note:   no known conversion for argument 1 from ‘std::nullptr_t’ to ‘Int_Node2&&’



keskiverto wrote:
You can either use aggregate initialization:
head = new Int_Node2 { data, nullptr, nullptr };

or provide a constructor:
1
2
3
4
5
6
7
8
9
10
 
struct Int_Node2 {
  int data;
  Int_Node2 *next;
  Int_Node2 *prev;
  Int_Node2( int d, Int_Node2* p, Int_Node2* n )
  : data( d ), next( n ), prev( p )
  {}
};

head = new Int_Node2( data, nullptr, nullptr );

Well, I'm thoroughly confused now. Okay, so was the first comment of head = new Int_Node2 ( data, nullptr, nullptr ); assumed I would add a constructor too? And I didn't which is why I got an error, yes?

Then the aggregate initialization method only requires that single line to work, yes?

I tried both methods. The aggregate initialization method gave a Segmentation fault when ran.

Here's the setup for that:
1
2
3
4
5
 
        void push_front(int data) {
            // FIXME - Work In Progress
            head = new Int_Node2 { data, nullptr, nullptr };
            head->next->prev = head;
        }


Then I commented out that line and tried with the constructor:
- Here is the part for the struct code:
1
2
3
4
5
6
7
8
 
struct Int_Node2 {
    int data;
    Int_Node2 *next; // address of the next node
    Int_Node2 *prev; // address of the previous node
    Int_Node2( int d, Int_Node2* p, Int_Node2* n )
        : data( d ), next( n ), prev( p )
        {}
};


- Here is the part for the actual member function:
1
2
3
4
5
6
 
        void push_front(int data) {
            // FIXME - Work In Progress
            //head = new Int_Node2 { data, nullptr, nullptr };
            head = new Int_Node2( data, nullptr, nullptr );
            head->next->prev = head;
        }


This gave errors when I tried to compile it:
http://cpp.sh/6leuq
(I put in a cpp.sh link because I reached maxed post length when I pasted it)
Last edited on
keskiverto (10381)
Lets look at the first error:
DoublyLinkedList.h:34:35: error: no matching function for call to ‘Int_Node2::Int_Node2()’
             Int_Node2 *temp = new Int_Node2; // create head node
                                   ^~~~~~~~~
DoublyLinkedList.h:12:5: note: candidate: Int_Node2::Int_Node2(int, Int_Node2*, Int_Node2*)
     Int_Node2( int d, Int_Node2* p, Int_Node2* n )
     ^~~~~~~~~
DoublyLinkedList.h:12:5: note:   candidate expects 3 arguments, 0 provided
DoublyLinkedList.h:8:8: note: candidate: constexpr Int_Node2::Int_Node2(const Int_Node2&)
 struct Int_Node2 {
        ^~~~~~~~~
DoublyLinkedList.h:8:8: note:   candidate expects 1 argument, 0 provided
DoublyLinkedList.h:8:8: note: candidate: constexpr Int_Node2::Int_Node2(Int_Node2&&)
DoublyLinkedList.h:8:8: note:   candidate expects 1 argument, 0 provided
DoublyLinkedList.h:41:24: error: no matching function for call to ‘Int_Node2::Int_Node2()’

Your code calls:
Int_Node2 *temp = new Int_Node2;
Where you provide 0 arguments for the constructor of Int_Node2.
The constructor that takes no arguments is known as the default constructor.

However, currently there are only three constructors to choose from:
1
2
3
 
Int_Node2(int, Int_Node2*, Int_Node2*) // the one you wrote
Int_Node2(const Int_Node2&) // copy constructor
Int_Node2(Int_Node2&&) // move constructor

None of those matches the "0 arguments" requirement.

The copy and move constructors are generated automatically by the compiler.
The default constructor is generated automatically by the compiler too, if user adds no custom constructors.

There are two options:

1. Provide the three arguments everywhere that you construct Int_Node2's. (Why would you create a node, if you don't have data anyway?)

2. Add explicit default constructor. We can ask the compiler to write it for us:
1
2
3
4
5
6
7
8
9
 
struct Int_Node2 {
    int data;
    Int_Node2 *next; // address of the next node
    Int_Node2 *prev; // address of the previous node
    Int_Node2() = default;
    Int_Node2( int d, Int_Node2* p, Int_Node2* n )
        : data( d ), next( n ), prev( p )
        {}
};
dhayden (5798)
Push_front is wrong. Uncomment step 3 and fix step 6:
1
2
3
4
5
6
7
8
9
10
 
        void push_front(int data) {
            // FIXME - Work In Progress
            Int_Node2 *newNode = new Int_Node2; // 1.
            newNode->next = head->next; // 2. | head->next is the ACTUAL front node. Head is just the pointer. I think(?) only this way for doubly linked lists?
            newNode->prev = head; // 3.
            // ^ Have tried doing = NULL; as well. Same result.
            newNode->data = data; // 4.
            head->next = newNode; // 5. 
            newNode->next->prev = newNode; // 6.
        }
MikeyBoy (5631)
PiggiesGoSqueal wrote:
I started doing things like int num = 0; or std::string str1 = "";, then people told me on the cplusplus forums that there's no need to do that because they are set to that by default.

Either:

(a) They were lying to you, or

(b) They were talking about one of the very specific circumstances where variables are default-initialised, and you've misread that to mean all variables everywhere are default-initialised.

In any case, it is not true that, in general, variables are automatically initialised to zero by default.
Last edited on
keskiverto (10381)
int and std::string do follow different rules, for int is a primitive, built-in type while string is a class that has default constructor. Therefore, a string object has always a known, consistent state.
PiggiesGoSqueal (167)
keskiverto wrote:
Lets look at the first error:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
DoublyLinkedList.h:34:35: error: no matching function for call to ‘Int_Node2::Int_Node2()’
             Int_Node2 *temp = new Int_Node2; // create head node
                                   ^~~~~~~~~
DoublyLinkedList.h:12:5: note: candidate: Int_Node2::Int_Node2(int, Int_Node2*, Int_Node2*)
     Int_Node2( int d, Int_Node2* p, Int_Node2* n )
     ^~~~~~~~~
DoublyLinkedList.h:12:5: note:   candidate expects 3 arguments, 0 provided
DoublyLinkedList.h:8:8: note: candidate: constexpr Int_Node2::Int_Node2(const Int_Node2&)
 struct Int_Node2 {
        ^~~~~~~~~
DoublyLinkedList.h:8:8: note:   candidate expects 1 argument, 0 provided
DoublyLinkedList.h:8:8: note: candidate: constexpr Int_Node2::Int_Node2(Int_Node2&&)
DoublyLinkedList.h:8:8: note:   candidate expects 1 argument, 0 provided
DoublyLinkedList.h:41:24: error: no matching function for call to ‘Int_Node2::Int_Node2()’


Your code calls:
Int_Node2 *temp = new Int_Node2;

<rest of msg...>

Thanks for your response! That was very informative/useful. I've solved my problem with your help & understand why it was a problem. :)

dhayden wrote:
Push_front is wrong. Uncomment step 3 and fix step 6:
1
2
3
4
5
6
7
8
9
10
 
        void push_front(int data) {
            // FIXME - Work In Progress
            Int_Node2 *newNode = new Int_Node2; // 1.
            newNode->next = head->next; // 2. | head->next is the ACTUAL front node. Head is just the pointer. I think(?) only this way for doubly linked lists?
            newNode->prev = head; // 3.
            // ^ Have tried doing = NULL; as well. Same result.
            newNode->data = data; // 4.
            head->next = newNode; // 5. 
            newNode->next->prev = newNode; // 6.
        }

Thanks for your reply! Unfortunately, I didn't read past keskiverto's message until after I had finished fixing it (oops). However, I greatly appreciate your response! :)


MikeyBoy wrote:

Either:

(a) They were lying to you, or

(b) They were talking about one of the very specific circumstances where variables are default-initialised, and you've misread that to mean all variables everywhere are default-initialised.

In any case, it is not true that, in general, variables are automatically initialised to zero by default.

Ah okay, thanks for letting me know! To clarify, from now on I should always initialize the variables right? Or only in particular situations? For example, if I were to write:
1
2
3
4
5
6
7
8
9
 
#include <iostream>
#include <string>

int main() {
    std::string hello = ""; // should I just do "std::string hello;"?
    std::cin >> hello;
    std::cout << hello << '\n';
    return 0;
}
Last edited on
keskiverto (10381)
http://www.cplusplus.com/reference/string/string/string/
empty string constructor (default constructor)
Constructs an empty string, with a length of zero characters.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <iostream>
#include <string>

int main() {
    std::string defa;
    std::cout << defa.empty() << '\t' << defa.length() << '\n'; // true 0

    std::string hello = "";
    std::cout << hello.empty() << '\t' << hello.length() << '\n'; // true 0
    std::cout << (hello == defa) << '\n'; // true

    std::string full = "xyz";
    std::cout << full.empty() << '\t' << full.length() << '\n'; // false 3
    std::cout << (full == defa) << '\n'; // false
}

1	0
1	0
1
0	3
0

The defa and hello have identical content and the content of defa is defined.
MikeyBoy (5631)
PiggiesGoSqueal wrote:
To clarify, from now on I should always initialize the variables right? Or only in particular situations?


As keskivertohas very sensibly pointed out, std::string has a default constructor. So it is automatically initialised to an empty string. Sorry - I was thinking of primitive types when I wrote my last message

You're looking for a simple one-size-fits-all rule, but there isn't one. The real answer is that you should understand the thing you are using, and how it works.

This may be useful:

http://www.enseignement.polytechnique.fr/informatique/INF478/docs/Cpp/en/cpp/language/default_initialization.html
Last edited on
keskiverto (10381)
Sorry - I was thinking of primitive types when I wrote my last message

We got into this due to my initial note that was a "blunt rule". My bad.

However, a blunt rule is not that bad as long as "you understand the thing you are using, and how it works".

For example:
1
2
3
4
 
{
  std::vector<int> Y;
  int* X {nullptr};
}

We do initialize the Y in the above code, because Y has a constructor that does it on our behalf.
The X has no such luxury. Hence the explicit initializer.

Put other way: all types are not initialized the exact same way. The rule applies, but polymorphically.
PiggiesGoSqueal (167)
Thanks for your replies keskiverto and MikeyBoy! Very informative. Apologies for the late reply, focusing on Finals at the moment.
Topic archived. No new replies allowed.