When a Node is Removed in Double Linked List?

[sobias]

Hi Guys,

There's something bugging me in the past 2 days. In Doubly Linked Lists, when will a Node get comepletely deallocated? is it when both Next and Previous references points to NULL? forget about the class and the method remove() and such.

Let me make an example so you get what I mean,

// Let's say we have this DLList. [1,2,3,4,5] and we make it a circular like this

head.prev = tail;
tail.next = head;

//Now 
//If I do the following:

head.next.next.next = head.prev;  //That will points to 5 not 4 anymore. But does it mean 4 still not removed?

//If I write another line:

head.prev.prev.info()  // info() or whatever method to print the element , why do I get 4??

My understanding is that a Node get deallocated by the garbage collecter automatecly when there is at least 1 reference is removed. is that right? correct me if I'm wrong.

I haven't dealt with Doubly Linked list that much. That's why I'm confiused. This deallocating thing always comes to my mind when I deal with Linked Lists. Which some say that I should not care about deallocating at all. but still worries me.

[deepecstasy]

Bro, 1st off, use pointer to operator with pointers instead of dot to call its members, i.e. ->
Now,dynamic memory, which you get from new operator & store its address into some pointer like *temp = new NODE<args> . You have to manually deallocate(return memory to OS) it using delete operator.
In your EXAMPLE: Yes, 5th node is still not removed, you just lost its address. So what you ought to do is after making it circular, do... delete tail;
& I don't see a reason for prev.prev.info problem. Try prev->prev->info & I hope you'll be good.

[Taywin]

@deepecstasy, there is no (visible) pointers in Java. There is NO need to manually deallocate memory in Java because the GC will automatically do it for you. Simply stop referring to the created object for a while, and the GC will wipe it out from the memory. If you comes from other languages such as C or C++, you may need to explain it in a different way.

When you are dealing with a doubly linked list, you must deal with both next and previous at the same time while inserting, removing a node. If you deal with only next but not previous, your double linked list will be broken (not be the same when you traversal in different direction).

In your case, what you did was...

/*
A doubly linked list of 1,2,3,4,5
  +-----------------------+
  V                       V
  1 <-> 2 <-> 3 <-> 4 <-> 5
  ^
  |
 head

When you do...
head.next.next.next = head.prev;
The list will be come...
  +-----------------------+    head.next is element 2
  V                       V    head.next.next is element 3
  1 <-> 2 <-> 3 <-  4 <-> 5    so element 3.next is no longer to 4
  ^     ^     |                but point back to element 2
  |     +-----+
 head     prev

Do you see the broken link now? The element 4 is now hanging in there with
broken link. When you call head.prev.prev, the link going backward direction
still give you the way to get back to element 4.

What you need to do is that you must fix it when you attempt to update the link
both way at the same time. If you want to get rid of the last 2 elements, you
must update the head as well.

head.next.next.next = head.prev;
  +-----------------------+
  V                       V
  1 <-> 2 <-> 3 <-  4 <-  5
  ^     ^     |
  |     +-----+
 head     

head.prev = head.next.next;
  +-----------+
  V           V               // now you see that elements 4 and 5 are left hanging
  1 <-> 2 <-> 3 <-  4 <-  5   // without being referenced, and will be GCed later
  ^     ^     |
  |     +-----+
 head     
*/

Look at the diagram above, you will see that you need to update the link from both directions when you deal with insertion & removal of a node. Doing it correctly, the left over nodes that are not being referenced will be removed from the memory by the GC. Therefore, I am sure that your current removal method is incorrect.

PS: When you do a removal in linked list, you should remove ONE at a time if you are not clearing the whole list. Don't do that kind of jumping removal because you get confused easily.

My understanding is that a Node get deallocated by the garbage collecter automatecly when there is at least 1 reference is removed. is that right? correct me if I'm wrong.

No, it is incorrect. This is a doubly linked list, not a singly linked list. If you remove one reference direction, it is not lost. If it is ever true, Java is a really broken language. Think about it, if you tie 2 stings to a small rock. Let say that 1 string is enough to hold the rock's weight. And then you cut one string off. Would the rock fall off and hit the ground? No. You still have another string to tie to it. So compare the example to doubly linked list. You represent the head node and the rock represent the next node you want to remove. Each string represents the link of next and prev. The GC is the ground.

I hope you see the picture.

[JamesCherrill]

My understanding is that a Node get deallocated by the garbage collecter automatecly when there is at least 1 reference is removed. is that right? correct me if I'm wrong.

No, that's not right. An object can only get garbage collected when there are zero remaining references to it (ps technically speaking there are also things called weak references that behave differently, but you can safely ignore those for the moment)

[sobias]

@Taywin, how exactly head.next.next.next = head.prev outputs 2? but not 5? The link from Node 3 is going to the prev link of head which is Node 5.

EDIT: Remember it's a circular so there is no end point.

[Taywin]

Oh, it appears that I am showing you a circular doubly linked list which is more complicated that your current problem. Sorry for the mistake. The statement of head.next.next.next = head.prev; blew me off.

Anyway, the head.next.next.next is equivalent to element2.next. The reason is if the statement is on the left hand side of an assignment sign, it attempts to reassign the propery/variable of the left hand side statement. If, however, the same statement is on the right hand side of an assignment sign, it will take the value of the statement and attempt to assign the value to the current left hand side variable.

/*
A doubly linked list of 1,2,3,4,5
    null<-1 <-> 2 <-> 3 <-> 4 <-> 5->null
          ^                       ^
          |                       |
         head                    tail

When you do...
head.next.next.next = head.prev;
The list will be come...
                                       head.next is element 2
                                       head.next.next is element 3
null<-1 <-> 2 <-> 3 <-  4 <-> 5->null  so element 3.next is no longer to 4
      ^           |           ^        but point to null (head.prev should be null)
      |           +-> null    |
     head                    tail

how exactly head.next.next.next = head.prev outputs 2? but not 5?

Now, when you said output is 2, do you mean head.next.next.info();?

Anyway, even though there is still a reference of element 4 pointing back to element 3 in this case, the last 2 elements should never be reached again and will be GCed if you construct the doubly linked list correctly! The problem is that you have the tail variable which to me is ambiguous. If you do head.next.next.next = head.prev; then what the tail variable is still referencing to? That's the reason why those last 2 elements are not removed by the GC -- they are still reachable in the program.

// i.e. traversal from head to tail after you modified your list
node = head;
while (node!=null) {
  System.out.print(node.info()+" ");
  node = node.next;
}
// this would result --> 1 2 3

// now traversal backward from tail (you didn't modify the tail)
node = tail;
while (node!=null) {
  System.out.print(node.info()+" ");
  node = node.prev;
}
// this would result --> 5 4 3 2 1

// Therefore, the link is broken.

[sobias]

Sorry for my very late reponse. Was having my break :). I clearly understand now. You guys been such a great help to me. I really really appreciate all your effort. My hat off to you.