time complexity of this while loop

Question

Hi I have written such a this code and I want to know that : its time complexity is O(n) ?

      DNode header = new DNode(null, null, null);
        DNode trailer = new DNode(null, header, null);
        header.next = trailer;
        for (Point point : pointList) {
            DNode node = new DNode(point, header, trailer);
            dList.addLast(node);
            header = node;
        }

I want to copying all objects from the pointList(ArrayList) to a dList(Doubly-Linked list). thanks

Jon Skeet · Accepted Answer · 2010-11-24 06:37:52Z

3

Yes. There's only one obvious loop here, which is O(n) - and everything within the loop is O(1), assuming a sensible implementation of the doubly-linked list.

answered Nov 24, 2010 at 6:37

Jon Skeet

1.5m893 gold badges9.3k silver badges9.3k bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

user472221 Over a year ago

I have a problem that adding a list to the end of the doubly linked list in such a way has O(n) or O(1)?

Jon Skeet Over a year ago

@user472221: Well you haven't told us what implementation you're using, but generally speaking a doubly-linked list has O(1) time for insertion at either end. If you're using LinkedList<T> from the JDK, that's certainly true.

user472221 Over a year ago

public void addLast(DNode v) { addBefore(trailer, v); }

Jon Skeet Over a year ago

@user472221: Well what does addBefore do?

user472221 Over a year ago

public void addBefore(DNode v, DNode z) throws IllegalArgumentException { DNode u = v.getPrev();// may throw an IllegalArgumentException!! z.setPrev(u); z.setNext(v); u.setNext(z); v.setPrev(z); size++; }

|

Collectives™ on Stack Overflow

time complexity of this while loop

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related