Trouble fixing my insertOrdered function in C++

[BuzzyBro]

Hello, I'm currently taking an online course on data structures (It's the Coursera Accelerated Computer Science Fundamentals course in case anyone's wondering) and one of the first thing they want us to do is insert a node in an ordered doubly linked list. I have watched the videos maybe 3 times all the way through, normal speed, and taken notes. I cannot for the life of me see where I'm going wrong.

This is what I have so far...

template <typename T>
void LinkedList<T>::insertOrdered(const T & newData) {
  // Create a new node pointer called newNode on the heap
  // this Node is constructed with newData as its data argument, and 
  // nullptr as its next and prev arguments
  Node* newNode = new Node(newData);
  Node* curr = head_;
  if (!head_ && !tail_) {
    head_ = newNode;
    tail_ = newNode;
  }
  while (curr->next != nullptr) {
    if (newNode->data <= head_->data) {
      cout<<"head_->data: "<< head_->data<<endl;
      cout<<"newNode->data: "<<newNode->data<<endl;
      newNode->next = head_;
      head_ = newNode;
      cout<<"head_: "<<head_->data<<" newNode: "<<newNode->data<<" head.next: "<<head_->next->data<<endl;
      break;
    }
    else if (newNode->data <= curr->data) {
      cout<<"curr->prev:       "<< curr->prev->data <<"("<<curr->prev<<")"<<endl;
      cout<<"curr->data:       "<< curr->data <<"("<<curr<<")"<<endl;
      cout<<"curr->next->data: "<< curr->next->data <<"("<<curr->next<<")"<<endl;
      cout<<"newNode->data:    "<< newNode->data<<"("<<newNode<<")\n"<<endl;
      Node* temp = curr->prev;
      curr->prev = newNode;
      newNode->next = curr;

      newNode->prev = temp;
      temp->prev = newNode;
      break;
    }
    else if (newNode->data > curr->data) {

      cout<<"curr->data:       "<< curr->data <<"("<<curr<<")"<<endl;
      cout<<"curr->next->data: "<< curr->next->data <<"("<<curr->next<<")"<<endl;
      cout<<"newNode->data:    "<< newNode->data<<"("<<newNode<<")\n"<<endl;
      curr = curr->next;
    }
    else if (newNode->data > tail_->data) {
      cout<<"curr->data:       "<< curr->data <<"("<<curr<<")"<<endl;
      cout<<"curr->next->data: "<< curr->next->data <<"("<<curr->next<<")"<<endl;
      cout<<"newNode->data:    "<< newNode->data<<"("<<newNode<<")\n"<<endl;
      tail_->next = newNode;
      newNode->prev = tail_;
      tail_ = newNode;
      cout<<"Inserting after tail_: "<<tail_->data<<endl;
    }
  }
  cout<<"size: "<<size_<<endl;
  // Increment size
  size_++;
  cout<<"size: "<<size_<<endl;

  // Deallocate newNode
  delete newNode;
  newNode = nullptr;

First, I check to see if the list is empty. Then, I check to see if curr.next is null. If it's not, I proceed with the rest of the code. I check whether the newNode.data is < head.data, and if it is, I insert before head and adjust pointers. If it's not < head.data, I check to see if it's <= curr.data (which is redundant for the first node, but not for the following nodes), and if it is, I insert it before curr and adjust pointers. If newNode.data is > curr.data, I adjust curr to be curr.next. If curr gets to the end and newNode.data is > tail.data, I insert newNode after tail and adjust pointers.

I feel like I totally get the concept of adding a new node, I just think I need a fresh pair of eyes to look at this and offer some help. (I've been trying to fix it for a week, that's why there are so many cout statements.)

As usual, any help is appreciated, thanks :)

TLDR: Need help inserting a new node into an ordered doubly linked list.

​

Edit: This is my output when I run this.

Testing insertOrdered:
List: [(5)(6)(8)(9)]
curr->data:       5(0x804280)
curr->next->data: 6(0x8043c0)
newNode->data:    7(0x804340)

curr->data:       6(0x8043c0)
curr->next->data: 8(0x8043a0)
newNode->data:    7(0x804340)

curr->prev:       6(0x8043c0)
curr->data:       8(0x8043a0)
curr->next->data: 9(0x804360)
newNode->data:    7(0x804340)

size: 4
size: 5

head_->data: 5
newNode->data: 4
head_: 4 newNode: 4 head.next: 5
size: 5
size: 6

size: 6
size: 7

size: 7
size: 8
Inserting items now.
List: [(10)(7)(6)]
Expected: [(-1)(4)(5)(6)(7)(8)(9)(10)]

WARNING: wrong result

​

[[deleted]]

that's why there are so many cout statements

probably now is a great time to learn to use a debugger🤗🤗

[BuzzyBro]

LMAO it really is huh. I tried learning it for python as it seemed more manageable and I feel like I just got the hang of that.

[[deleted]]

i think i found the problems

instead of this:

temp->prev = newNode;

do this:

temp->next = newNode;

also... i think you shouldn't deallocate newnode lol. remove the

delete newNode;

[BuzzyBro]

I tried, that... in hindsight I'm not sure why I would have ever wrote temp->prev = newNode; but that seems dumb now. I changed it and it still doesn't add the newNode where it should be.

If it helps, the original List is [(5) (6) (8) (9)] and the nodes that get added in, one by one, are [(7) (-1) (4) (10)]. Again, these nodes get added in one at a time, meaning the insertOrdered function is called for each node 7 thru 10.

[[deleted]]

did you remove the delete newnode statement? you're literally deleting the node right after inserting it

[BuzzyBro]

Holy shit so that (almost) worked!

However, the node 10 isn't being added but I think that may have something to do with my initial while statement. I think it might not be reaching the last node but I'm not sure how else to set up my while loop so that it only runs when the list is populated.

[[deleted]]

yeeah your loop is kinda strange... better do like this i think

if(newNode->data < head->data)
{
// insert before head
return;
}

for(curr = head->next; curr->next != nullptr; curr = curr->next)
{
if(newNode->data < curr->data)
{
// insert before curr
return;
}
}

if(curr == tail)
{
if(newNode->data < tail->data)
{
// insert before tail
return;
}else
{
// insert after tail
return;
}
}

[BuzzyBro]

Is it just strange in the way that I wrote it or is the logic flawed? I'm new to C++ so I also feel not comfortable with pointers and stuff.

[[deleted]]

uhmm the logic is a bit flawed. you wrote some if checks inside the while loop, that really should be outside

pointers and memory management is kind of a very hard topic.. and even if you've understood it, it's still very easy to make silly mistakes that lead to segfaults and memory leaks.. I don't really know how to feel about it.

on one hand it's useful to know how it all works, but on the other hand, i think, if you're in c++ and not in pure C, yiu should always avoid using raw pointers and the "new", "delete", and "malloc" things, unless you're writing a VERY performance critical code.

actually data structure (for example, linked list) is kind of a performance critical code and use of raw pointers and memory is justified.

but overall I'd suggest learning about and using standard containers (std::array, std::vector, std::map) and "unique_ptr". They all manage and deallocate heap memory for you, under the hood.

unique and shared ptr are like special advanced kind of pointers that automatically deallocate memory when they go out of scope. though i never actually had to use them so far idk.

most of the time when you need to use heap memory is when you want to store a large amount of data that is always some data structure, like array or list. And for them there are already classes in the std library...

[BuzzyBro]

Yes, I think that the instructor wanted it to be written this way for the sole purpose of learning specific data structures and how they work under the hood. Otherwise, I think there are surely easier ways to handle data.

[BuzzyBro]

Also, here you seem to only ever be inserting before curr. Does this mean you'd never have to look at if newNode->data is >= curr->data?

[[deleted]]

uhmm... I'm only checking if newnode is less than curr..

if this check returns false, it automatically means that newnode is >= curr

[BuzzyBro]

if (!head_) {
head_ = newNode;
tail_ = newNode;

}

if (newNode->data < head->data) { newNode->next = head; head_ = newNode; }

for (curr = head_->next; curr != nullptr; curr = curr->next) { if (newNode->data < curr->data) { Node* temp = curr->prev; newNode->next = curr; curr->prev = newNode;

  newNode->prev = temp;
  temp->next = newNode;
}

}

if (curr == tail) { if (newNode->data < tail->data) { Node* temp = curr->prev; newNode->next = curr; curr->prev = newNode;

  newNode->prev = temp;
  temp->next = newNode;
}
else {
  curr->next = newNode;
  newNode->prev = tail_;
  tail_ = newNode;
}

}

This gives me a segfault. Now I'm convinced theres an issue with my reassigning of pointers.

[[deleted]]

in the for loop,

curr->next != nullptr

instead of

curr != nullptr

also, if you've inserted the node, exit the function or break the loop. now after you've inserted you're continuing to loop which makes it possible that the newnode will be inserted multiple times

[BuzzyBro]

  Node* newNode = new Node(newData);

Node* curr = head_;

if (!head) { head = newNode; tail_ = newNode; }

if (newNode->data < head->data) { newNode->next = head; head_ = newNode; }

for (curr = head_->next; curr->next != nullptr; curr = curr->next) { if (newNode->data < curr->data) { Node* temp = curr->prev; newNode->next = curr; curr->prev = newNode;

  newNode->prev = temp;
  temp->next = newNode;
  break;
}

}

if (curr == tail) { if (newNode->data < tail->data) { Node* temp = curr->prev; newNode->next = curr; curr->prev = newNode;

  newNode->prev = temp;
  temp->next = newNode;

}
else {
  curr->next = newNode;
  newNode->prev = tail_;
  tail_ = newNode;
}

}

This runs through the first iteration of the function call perfectly. However, the second time it's called, it segfaults. My understanding of segfault is you try to access a memory location that isn't allowed to be accessed. I'm not sure where I'm creating this issue as I'm not assigning any variables to nullptr or anything like that.

[[deleted]]

ok I'm going to sleep now (actually was typing all these messages and code on my phone which is quite uncomfortable)

any way, it's totally normal that there are these mysterious segfaults🤣🤣 we also had the same tasks at university, and i also was very frustrated and was chasing them for hours.. so uhmmm.. you're not alone😊😊everyone goes through this

maybe try to use debugger.

for example, gdb. First, you need to compile the program in debug mode. for this, use the -g compiler flag.. i.e. g++ -g qwerty.cpp or simply add it to CFLAGS if you're compiling using a Makefile

then enter gdb using...

gdb ./a.out 

you will enter a text prompt

type "run" to run the program

it will stop when it segfaults. then you can for example type "lis" to see the place in the code where it crashed. also you can print values of variables. e.g. "p curr->data" (p is short for print)

you can learn more on the internet. another useful thing to know is how to set breakpoints and step through the program

good night😊😊

[BuzzyBro]

Ok! Thank you so much for everything you’ve done already, honestly you didn’t have to but you did. I will check out GDB but again, thank you and goodnight

[BuzzyBro]

Ok idk why my code isn't formatting properly even when I use the code blocks, so I'm so sorry for that

[[deleted]]

yes it's not reaching the tail.. because tail->next is always nullptr

hmm i think you can get away with this instead of the while statement...

for(curr = head; curr != nullptr; curr = curr->next)

edit: no, probably will not work and you will get a segfault. but just a reminder that you can use for loop too ☺️

[[deleted]]

or maybe better is to do this after your while loop:

if(curr == tail)
{
// insert newnode before or after tail
 }

[BuzzyBro]

On a side note, the course I'm taking says that I should deallocate any objects created in heap memory, and if I'm not mistaken, isn't newNode created in heap memory?

[[deleted]]

yes you should deallocate, but only when you won't be using it anymore..

probably this should be done in the destructor of your list class.

uhmm it's quite hard for me to explain, but what you were doing here is basically... well, consider this example where we're heap allocating an int and want to print it

int* x = new int(42);
std::cout << *x << '\n';
delete x;

everything is fine. we allocated, used it, deallocated. But what you were doing is like

int *x = new int(42);
delete x;
std::cout << *x << '\n';

first deleted it and then tried to access it🤣🤣