Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Why is this implementation of linked list so slow?

Asked by Carlos on 9 May 2013

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

Which Matlab release do you use?

I assumr insertAtTail == insertAfter ?

Carlos

Products

No products are associated with this question.

0 Answers

Contact us