Removing "head" entry from doubly linked list

2 次查看（过去 30 天）
Konrad Warner
Konrad Warner 2021-11-16
评论： Adam 2021-11-18
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
  5 个评论
显示 3更早的评论
Adam
Adam 2021-11-17
编辑：Adam 2021-11-17
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.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Adam
Adam 2021-11-17
编辑：Adam 2021-11-17
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 个评论
显示 4更早的评论
Konrad Warner
Konrad Warner 2021-11-18
编辑：Konrad Warner 2021-11-18
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
Adam 2021-11-18
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.

请先登录，再进行评论。

更多回答（1 个）

Adam Danz
Adam Danz 2021-11-16
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 个评论
Konrad Warner
Konrad Warner 2021-11-16
编辑：Konrad Warner 2021-11-16
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
Adam Danz 2021-11-17
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)

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Sample Class Implementations 的更多信息

标签

产品


版本

R2020a

Community Treasure Hunt

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

Start Hunting!

Translated by