Why is this implementation of linked list so slow?
1 view (last 30 days)
Show older comments
Hi all,
I have taken the example from OOP manual to implement a linked list. Then, I have written some code to see how fast it is and it turns that adding elements at the end of the list is really slow. Here is the important part of code:
classdef dlnode < handle
properties (GetAccess = public)
Data;
end
properties (GetAccess = private)
Next; % next node
Prev; % prev node
end
methods
function this = dlnode(Data) % Constructor
if nargin == 0
this.Data = [];
else
this.Data = Data;
end
end
function insertAfter(newNode,nodeBefore)
disconnect(newNode);
newNode.Next = nodeBefore.Next;
newNode.Prev = nodeBefore;
if ~isempty(nodeBefore.Next)
nodeBefore.Next.Prev = newNode;
end
nodeBefore.Next = newNode;
end
end
The code to test this class:
tic
d = dlnode(0);
tmp = dlnode(0);
for i=1:1000
tmp.insertAfter(d);
tmp = dlnode(0);
end
toc
The two problems I see are:
# it's too slow (java.util.LinkeList is hundred times faster)
# It seems to be O(n^2).
I've used the profiler with the test code and it tells me this line of code in method insertAtTail:
nodeBefore.Next = newNode;
is taking almost 97% of time.
Any idea why this is happening?
1 Comment
per isakson
on 12 May 2013
Edited: per isakson
on 12 May 2013
Which Matlab release do you use?
I assumr insertAtTail == insertAfter ?
Answers (0)
See Also
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!