Removing "head" entry from doubly linked list

7 views (last 30 days)
Hi,
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
  5 Comments
Konrad Warner
Konrad Warner on 17 Nov 2021
Sure, you were quicker than I could answer

Sign in to comment.

Accepted Answer

Adam
Adam on 17 Nov 2021
Edited: Adam on 17 Nov 2021
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.
  6 Comments
Adam
Adam on 18 Nov 2021
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.

Sign in to comment.

More Answers (1)

Adam Danz
Adam Danz on 16 Nov 2021
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
  2 Comments
Adam Danz
Adam Danz on 17 Nov 2021
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)

Sign in to comment.

Categories

Find more on Entering Commands in Help Center and File Exchange

Products


Release

R2020a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!