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?
No products are associated with this question.
Play games and win prizes!Learn more