Removing "head" entry from doubly linked list

Hi,

I was experimenting with this linked list implementation: https://www.mathworks.com/help/matlab/matlab_oop/example-implementing-linked-lists.html#brik0u3

I have tried to modify the code (see lines with comments below) so that the last entry always points to the beginning and the start points back to the end.

The test ist fine,

clear all
head = dlnode(1);
for i = 10:-1:2
    new = dlnode(i);
    insertAfter(new,head);
end

but I cant figure out how to remove the first entry (and replace it by the second one) without removing the hole list.

I mean

removeNode(head.Next)

works (entry 2 is gone), but

removeNode(head)

just leaves the head object.

Implementation (just added the else statement)

classdef dlnode < handle
   properties
      Data
   end
   properties (SetAccess = private)
      Next = dlnode.empty
      Prev = dlnode.empty
   end
   methods
      function node = dlnode(Data)
         if (nargin > 0)
            node.Data = Data;
         end
      end
      function insertAfter(newNode, nodeBefore)
         removeNode(newNode);
         newNode.Next = nodeBefore.Next;
         newNode.Prev = nodeBefore;
         if ~isempty(nodeBefore.Next)
            nodeBefore.Next.Prev = newNode;
         else % Modified: Open end points back to the beginning
                nodeBefore.Prev = newNode;
                newNode.Next = nodeBefore;
         end
         nodeBefore.Next = newNode;
      end
      function insertBefore(newNode, nodeAfter)
         removeNode(newNode);
         newNode.Next = nodeAfter;
         newNode.Prev = nodeAfter.Prev;
         if ~isempty(nodeAfter.Prev)
            nodeAfter.Prev.Next = newNode;
         else % Modified: Open beginning points back to the end
            nodeAfter.Next = newNode;
            newNode.Prev = nodeAfter;
         end
         nodeAfter.Prev = newNode;
      end
      function removeNode(node)
         if ~isscalar(node)
            error('Nodes must be scalar')
         end
         prevNode = node.Prev;
         nextNode = node.Next;
         if ~isempty(prevNode)
            prevNode.Next = nextNode;
         end
         if ~isempty(nextNode)
            nextNode.Prev = prevNode;
         end
         node.Next = dlnode.empty;
         node.Prev = dlnode.empty;
      end

      function clearList(node)
         prev = node.Prev;
         next = node.Next;
         removeNode(node)
         while ~isempty(next)
            node = next;
            next = node.Next;
            removeNode(node);
         end
         while ~isempty(prev)
            node = prev;
            prev = node.Prev;
            removeNode(node)
         end
      end
   end

   methods (Access = private)
      function delete(node)
         clearList(node)
      end

   end
end

[Adam]

I'm not sure I understand the type of list you are trying to create here. From your description I assumed you wanted that the last node in the list always points back to the first node.

But your code seems to do something very different - i.e. if you try to add a node after the final one in the current list (i.e. that node has an empty 'Next' property) then instead of doing this you actually add the new node before the node you were wanting to insert it after. Likewise if you try to insert a node before the first node in the list you instead insert it after that first node.

I don't see any inherent problem with removing a head node from a circular list (though technically, by the definition of a circular list there is no head node, to my understanding), but I'm already too confused by where you add the nodes in the above two cases to look further into what is happening when you delete one...

[Adam]

Ah, OK...I'll leave my comment there in case it has already been read and there is something useful still in it, but I realise now that the only time the else clauses for adding a node before/after will trigger are at the very start of building the list when you add the second node. So maybe it does make sense for that...I'd have to take another look and get my head around that specific case!

[Konrad Warner]

I added this else statement just for the case the nodeBefore (the existing list) has no enty yet, so to speak, the first two nodes are connected. The 1st node points back to the 2nd node, the 2nd (new) node points next to the 1st node and the 2nd (new) node points back to 1st node.

In all other cases nodeBefore is already a list > 2 entries (has no empty Next/Prev) and the new node is just placed in beween the circular list entries.

Try...

head = dlnode(1);
for i = 10:-1:2
    insertAfter(dlnode(i),head);
end

...and you should see it works (at least in my case).

As I described below, my problem seems to be that head is the reference to the workspace that I cant remove without removing the hole list.

removeNode(head.Next) % works
removeNode(head.Prev) % works

head = head.Next;     %
removeNode(head.Prev) % together works

removeNode(head)    % doesn't work (actually looking for the behavior of the upper two lines)

[Adam]

See my answer below for related to that problem. It's the same as you get in languages like C++ if you setup a pointer to point at some data then you change what the pointer is pointing at - the original data still exists in the memory, you just removed your only way of accessing it.

[Konrad Warner]

Sure, you were quicker than I could answer

Answer 1

[Adam]

Unless I am totally misunderstanding (possible given my initial confusion in my comment) your class works fine.

What isn't fine is the way you test it, because you create nodes in a for loop, but don't store any of them anywhere other than in the .Next or .Prev of another node in the list.

The head node is the only one you keep a copy of in your workspace. So when you remove that from the list it becomes detached and the rest of the list will still exist correctly in memory, but you just lost any access to it because the only node you stored as a variable is the head, which is no longer part of the list.

The following code works fine to test:

>> n1 = dlnode(1);
>> n2 = dlnode(2);
>> n3 = dlnode(3);
>> 
>> n2.insertAfter( n1 )
>> n3.insertAfter( n2 )
>> removeNode( n1 )
>> 
>> n1

n1 = 

  dlnode with properties:

    Data: 1
    Next: [0×0 dlnode]
    Prev: [0×0 dlnode]

>> n2.Next

ans = 

  dlnode with properties:

    Data: 3
    Next: [1×1 dlnode]
    Prev: [1×1 dlnode]

>> n2.Prev

ans = 

  dlnode with properties:

    Data: 3
    Next: [1×1 dlnode]
    Prev: [1×1 dlnode]

>> n3.Next

ans = 

  dlnode with properties:

    Data: 2
    Next: [1×1 dlnode]
    Prev: [1×1 dlnode]

>> n3.Prev

ans = 

  dlnode with properties:

    Data: 2
    Next: [1×1 dlnode]
    Prev: [1×1 dlnode]
    

Here you see that n1 (which was what you might call the 'head') is now a detached node, but n2 and n3 are still connected in a circular fashion to each other. The only difference from your code is that I keep references to those nodes as variables so that I could still access them when I removed n1 from the list.

[Adam]

In terms of a practical suggestion, maybe return the next node after the one you just removed from this function:

function nextNode = removeNode(node)
    if ~isscalar(node)
        error('Nodes must be scalar')
    end
    prevNode = node.Prev;
    nextNode = node.Next;
    if ~isempty(prevNode)
        prevNode.Next = nextNode;
    end
    if ~isempty(nextNode)
        nextNode.Prev = prevNode;
    end
    node.Next = dlnode.empty;
    node.Prev = dlnode.empty;
end

Then when you remove a node you will always have access to an active node still in the list. For clarity, all I changed there is to return nextNode from the function that previously returned nothing.

[Adam Danz]

@Konrad Warner Adam's suggestion above is virtually the same as mine but 1 step simpler. I saw it after writing my comment.

[Konrad Warner]

I suspected something similar, but your examples get more to the heart of the problem (at least make it more clear). The reference to the workspace is cut by executing removeNode(head). I'm definitly learning a lot new stuff about object handling.

The return of nextnode by removeNode is also a great idea, thank you both @Adam @Adam Danz

However, I still found a strange behaviour when I tried to futher extand the dlnode class by a popFirst method:

function data  = popFirst(node)
    data  = node.Data;
    % - remove Node
    nextnode = removeNode(node);
    % replace properties of the current obj by nextnode (not very elegant?)
    node.Data = nextnode.Data;
    node.Next = nextnode.Next;
    node.Prev = nextnode.Prev;
end % pop_first

Now the first run looks as supposed (return: data = 1 and head(2) = head.Next)

head = dlnode(1);
for i = 10:-1:2
    insertAfter(dlnode(i),head);
end
data = popFirst(head); % 1x

Also the second run (return: data = 2 and head(3) = head.Next)

data = popFirst(head); % 2x

But the third time...

data = popFirst(head); % 3x

... the error occurs "Insufficient number of outputs from right hand side of equal sign to satisfy assignment."

Error in dlnode/popFirst (line 95)

node.Data = nextnode.Data;

Any idea what's wrong?

[Adam]

What are you trying to do with this popFirst function? It seems to do what I would expect it to without these lines, which seem to do something I wouldn't expect to be desirable:

node.Data = nextnode.Data;
node.Next = nextnode.Next;
node.Prev = nextnode.Prev;

You get the data property from the node you want to pop, then you remove that node. This seems to me like the full functionality. Removing that node will cause the remaining nodes in the linked list to relink in the expected manner and you have your data returned.

What the code above does is replace what is in the node you just popped off the list with the values from the next node (which is still in the list). This will effectively put it back into the linkage, but now you will have multiple nodes with the same 'Next' and 'Prev' linkage in your tree, and the node you just popped will contain the data of the next node in the tree, which doesn't seem like usual 'pop' behaviour?

What behaviour are you looking to setup with those lines of code?

Because you are working with a handle class, the changes you make within the class to the node will be reflected in the one you have stored in the workspace, but again this seems odd then that you replace its data, unless you want that node to now represent the next one in the list within your workspace? If so it isn't quite working that way because you have repeat nodes instead now.

[Konrad Warner]

I see, what I had in mind doesn't work like that.

Basically, I was looking for this line of code

data = popFirst(head);  

where just the data of head is returned and the whole list (head) is upadating itself within the method popFirst (that head = nextNode in workspace)

But a method probably cannot replace its own object (self).

The way to go for a "popFirst -> data-method" seems just to work over returning the new (next) list.

function [nextnode,data]  = popFirst(node)
data  = node.Data;
nextnode = removeNode(node);
end % pop_first

But that's fine.

[Adam]

That is how I would do it I think with this setup. It keeps the list setup as it should and you get back both the data and the link to the next node in the list from the one you removed. You can then assign this as:

[head, data] = popFirst( head );

to replace the same workspace variable.

Answer 2

[Adam Danz]

To achieve a circular list where the first and last nodes are circularly connected, follow these 2 steps.

Step 1: Modify the classdef

Add this public method to the dlnode classdef. This function returns the n^th object from the linked list. So head.nthNode(5) would return the 5th node. This is the only modification needed from the demo in the documentation.

function obj = nthNode(obj, n)
    for i  = 1:n-1
        if all(size(obj.Next)==0)
            % This prevents exceeding number of nodes
            continue
        end
        obj = obj.Next;
    end
end

Step 2: link the first and last nodes

Add 1 line after your initial for-loop

head = dlnode(1);
for i = 10:-1:2
    new = dlnode(i);
    insertAfter(new,head);
end
head.nthNode(10).insertBefore(head);  % for 10 nodes

[Konrad Warner]

Thank you, definitely a useful method in this context!

But I already created a circular list with some little changes (looks fine to me at this point), my problem is somewhat different. To be more clearly: to implent a popFirst method I can't remove the head without disconnecting the hole list.

My attempt (not working):

function data  = popFirst(node)
%pop_first returns first element of the list and removes it
data  = node.Data;
removeNode(node)
end 

Similar to a popLast method (working)

function data  = popLast(node)
%pop_last returns last (before first) element of the list and removes it
data = node.Prev.Data;
removeNode(node.Prev);
end % pop_last

removeNode(node) removes the hole list, can't figure out how to jump to node = node.Next as new head object after removing

test:

head = dlnode(1);
for i = 10:-1:2
    insertAfter(dlnode(i),head);
end

popLast(head)    % working
popFirst(head)   % notworking same as removeNode(head)

[Adam Danz]

I agree with the other Adam's opinion that one source of difficulty is not storing the objects in separate variables. However, you can still achieve what you're describing with your current approach.

First understand why it appears to work when replacing the 2nd node but not the first. The removeNode function does not delete the object. It only replaces the "Next" and "Prev" properties of the nodes after and before the selected node and then sets those properties of the selected node to empty/missing. But since node #2 isn't stored anywhere, it's no longer accessibly. However, the first node is stored as a variable so even though the Next and Prev properties are cleared, it still exists but the other nodes no longer exist.

If you want to replace the first node in the circular list, you'll need to modify the removeNode method.

• Add an output to removeNode
• Replace "node" in the last line

function node = removeNode(node)    % add output
     if ~isscalar(node)
        error('Nodes must be scalar')
     end
     prevNode = node.Prev;
     nextNode = node.Next;
     if ~isempty(prevNode)
        prevNode.Next = nextNode;
     end
     if ~isempty(nextNode)
        nextNode.Prev = prevNode;
     end
     node.Next = dlnode.empty;
     node.Prev = dlnode.empty;

     node = nextNode;   % replace node
end

Now, you can call removeNode with an output,

head = removeNode(head)