CODEWITHSUNDEEP
c++linked-listdoubly-linked-list
StacksAndParsing
StacksAndParsing

Reputation: 119

Doubly Linked Lists: Properly deleting an adding something in the middle of a list?

Write the code fragment that appropriately deletes the node pointed to by p (data value 14) in the doubly linked list.

enter image description here

I think I have an idea of how to do this:

(1) Make the node on the right side's previous element point to the node on the left

(2) Make the node on the left side's next element point to the node on the right

(3) Make the node's elements which p is pointing to NULL and delete it.

However I forgot how to write this in code (it's been a while). I was thinking it would be something like this (I'm assuming node is a struct that holds an int data, node* next, and node* previous):

node* x = p->next;
node* y = p->previous;
x->previous = y;
y->next = x;
p->previous = nullptr;
p->next = nullptr;
delete p;
x->previous = y;

Write the code fragment to insert a node between 14 and 16 (same picture):

node *x = p->next;
node y;
y->previous = x->previous;
y->next = p->next;
x->previous = y; 
p->next = y;

Would this be okay?

Upvotes: 1

Views: 199

Answers (1)

Misguided
Misguided

Reputation: 1302

The deletion code is almost okay. Notice, however, a few things:

  1. You are using inconsistent naming (left should be previous).
  2. There is no need for you to set p's fields to nullptr, you're going to delete it anyways.
  3. The last x->previous = y will make this "circular" that's not what you want!.

This would be a better approximation:

node *x = p->next;
node *y = p->previous;
x->previous = y;
y->next = x;
delete p;

However, this has a caveat: what happens if the list is a singleton? that is, you only have p?. Notice that both p->next and p->previous will be NULL, and hence the assignment to x and y will error! (notice that being the first or the last element will cause the same problem, just with some side).

The second part of the code is a little bit more problematic:

  1. Notice first of all that your code won't compile: y is a variable, and you're dereferencing it through y->. This is an operation that can only be done on pointers [1]. This problem is actually more profound in the sense that y being placed in the stack will be deleted as soon as it leaves the scope, and hence you will get an undefined behavior within your linked list if you were to use &y to get a pointer.
  2. y->previous = x->previous; can be simplified to y->previous = p
  3. y->next = p->next; can be simplified to y->next = x

With those corrections, this would turn into:

node *y = new node();
y->previous = p;
y->next = p->next;
p->next->previous = y;
p->next = y;

Notice, however, that once again this does not handle the case in which p points to the end of the list! (what would happen with p->next->previous = y?), so you should correct that. Also, does it matter if p points to the beginning of the list rather than the end? Should you handle that?.

The only actual problem was the thing with dynamic memory, the rest of the corrections are just 'readability' corrections. Even though 'readability' is personal preference, you should always try to make your code as clear as possible.

[1] Unless you're actually using the operator->() overload, which I assume you are not.

Upvotes: 1

Related Questions