8 Replies - 2268 Views - Last Post: 19 April 2013 - 03:34 AM Rate Topic: -----

#1 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 24-October 12

Time complexity for linked lists

Posted 17 April 2013 - 03:03 PM

4- Consider a queue implemented using a singly linked list, what is the time complexity of enqueue() assuming the start of the queue is the start of the list?
a- O(n) linear time
b- O(log n) logarithmic time
c- O(1) constant time
d- O(n2) polynomial time


5- Consider a queue implemented using a doubly linked list, what is the time complexity of enqueue() assuming the start of the queue is the start of the list?
a- O(n) linear time
b- O(log n) logarithmic time
c- O(1) constant time
d- O(n2) polynomial time

Im kind of confused isnt a linked listed just a list that can have either one direction or two? how does that effect complexity. For a queue when you enqueue and the front of the list is at position 0 you have O(1) and when you dequeue you have O(n), whyy arent these the same answers for linked list??
Answers are A and C, thank you

Is This A Good Question/Topic? 0
  • +

Replies To: Time complexity for linked lists

#2 Romeo1  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 30-September 10

Re: Time complexity for linked lists

Posted 17 April 2013 - 05:31 PM

View Postmedaa, on 17 April 2013 - 03:03 PM, said:

4- Consider a queue implemented using a singly linked list, what is the time complexity of enqueue() assuming the start of the queue is the start of the list?
a- O(n) linear time
b- O(log n) logarithmic time
c- O(1) constant time
d- O(n2) polynomial time


5- Consider a queue implemented using a doubly linked list, what is the time complexity of enqueue() assuming the start of the queue is the start of the list?
a- O(n) linear time
b- O(log n) logarithmic time
c- O(1) constant time
d- O(n2) polynomial time

Im kind of confused isnt a linked listed just a list that can have either one direction or two? how does that effect complexity. For a queue when you enqueue and the front of the list is at position 0 you have O(1) and when you dequeue you have O(n), whyy arent these the same answers for linked list??
Answers are A and C, thank you




Big Oh notation is something that can be very hard to understand, and I have taken many classes and it can still be hard to get, but lets take a look here.

When implementing a queue you can choose to insert in two ways, but not matter what way you choose the remove or insert will be affected.

1.) If you want to have constant time insertion:

Inserting on the front of a linked list is constant time because you have a pointer to the front of the list, you just make a new node and fix up the pointers.

            public void insert(int val)//inserts at beginning of list
            {
                 Node newNode = new Node(val);
                 newNode.next = first;
                 first = newNode;
           }



Above is code for inserting on the front of the linked list, if you analyze the code you will see all the operations can be done in constant time. If you choose to do this your dequeue will be affected because deletion is no longer constant, you have to traverse the linked list and remove the last element the following is code to do this.

       
    public Node delete(int val)
    {
        Node current = first;
        Node previous = first;
        while(current.item != val)
        {
            if(current.next == null)
                return null;
            else
            {
                previous = current;
                current = current.next;
            }
        }
        if(current == first)
            first = first.next;
        else
            previous.next = current.next;
        return current;
    }


As you can see this code has a loop that has to run N times because you have to traverse the entire list to do the removal.

2.) If you chose to have removal a constant time operation you will just reverse these functions, not you would have to traverse the list to find the end and then do some more pointer arithmetic to hook up the list.

This means the way you implement the linked list on a queue matters not matter what way you choose you have to deal with one O(n) operation for either removal or deletion.

If you want to have a queue that is bound above by some constant you can implement a queue using two stacks.


Here is a little chart showing some running times:

Posted Image

Please let me know if you would like some more explanation on this.
Was This Post Helpful? 0
  • +
  • -

#3 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2153
  • View blog
  • Posts: 3,311
  • Joined: 21-June 11

Re: Time complexity for linked lists

Posted 18 April 2013 - 04:14 AM

View Postmedaa, on 18 April 2013 - 12:03 AM, said:

Im kind of confused isnt a linked listed just a list that can have either one direction or two?


If by two directions you mean that each node knows its predecessor and its successor (as opposed to knowing just one of the two, which would be "one direction"), then yes, that's true.

Quote

how does that effect complexity.


If you have a reference to the last node of the list, then you can delete that node, by setting its predecessor's successor to None. If the node knows its predecessor that just means the following code:

def dequeue(this):
    second_to_last_node = this.last_node.predecessor
    second_to_last_node.successor = None
    this.last_node = second_to_last_node



If the node doesn't know its predecessor, you'd need to loop through the entire list to find the second to last node.


Quote

For a queue when you enqueue and the front of the list is at position 0 you have O(1) and when you dequeue you have O(n), whyy arent these the same answers for linked list??


The assignment's comparing a queue that's implemented as a singly linked list versus a queue that's implemented as a doubly linked list. You're talking like it's comparing a queue with a linked list. I'm not sure what you mean by that because both kinds of queues that it's comparing are linked lists.

View PostRomeo1, on 18 April 2013 - 02:31 AM, said:

This means the way you implement the linked list on a queue matters not matter what way you choose you have to deal with one O(n) operation for either removal or deletion.


That's not true. When using a doubly linked list, both enqueue and dequeue are O(1) - no matter which end of the list you define to be the start of the queue. The direction only matters for singly linked lists.

Also a singly linked list can implement both enqueue and dequeue if we define the beginning of the queue to be the end of the list instead of the beginning. That is adding to the end of a singly linked and removing from the beginning of a singly linked list can both be implemented in O(1) time.

This post has been edited by sepp2k: 18 April 2013 - 04:18 AM

Was This Post Helpful? 0
  • +
  • -

#4 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7999
  • View blog
  • Posts: 13,701
  • Joined: 19-March 11

Re: Time complexity for linked lists

Posted 18 April 2013 - 07:19 AM

If you're having trouble with the abstractions, make a picture.

Take the queue a,b,c,d, where a is at the front of the queue (ie, the next item to be removed) and d is at the tail. (you need four deq operations to get d).

Suppose first that this queue is built on a singly-linked list, and the start of the queue is at the head of the list. What do you have to do to enqueue node e? What nodes do you have to touch? How about for the dequeue operation? Then assume that the queue is built on a doubly-linked list, and ask the same questions.

Again, it helps to draw a picture. (a whiteboard is an invaluable tool for thinking about code)

This post has been edited by jon.kiparsky: 18 April 2013 - 07:19 AM

Was This Post Helpful? 0
  • +
  • -

#5 Romeo1  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 30-September 10

Re: Time complexity for linked lists

Posted 18 April 2013 - 04:26 PM

View Postsepp2k, on 18 April 2013 - 04:14 AM, said:

View Postmedaa, on 18 April 2013 - 12:03 AM, said:

Im kind of confused isnt a linked listed just a list that can have either one direction or two?


If by two directions you mean that each node knows its predecessor and its successor (as opposed to knowing just one of the two, which would be "one direction"), then yes, that's true.

Quote

how does that effect complexity.


If you have a reference to the last node of the list, then you can delete that node, by setting its predecessor's successor to None. If the node knows its predecessor that just means the following code:

def dequeue(this):
    second_to_last_node = this.last_node.predecessor
    second_to_last_node.successor = None
    this.last_node = second_to_last_node



If the node doesn't know its predecessor, you'd need to loop through the entire list to find the second to last node.


Quote

For a queue when you enqueue and the front of the list is at position 0 you have O(1) and when you dequeue you have O(n), whyy arent these the same answers for linked list??


The assignment's comparing a queue that's implemented as a singly linked list versus a queue that's implemented as a doubly linked list. You're talking like it's comparing a queue with a linked list. I'm not sure what you mean by that because both kinds of queues that it's comparing are linked lists.

View PostRomeo1, on 18 April 2013 - 02:31 AM, said:

This means the way you implement the linked list on a queue matters not matter what way you choose you have to deal with one O(n) operation for either removal or deletion.


That's not true. When using a doubly linked list, both enqueue and dequeue are O(1) - no matter which end of the list you define to be the start of the queue. The direction only matters for singly linked lists.

Also a singly linked list can implement both enqueue and dequeue if we define the beginning of the queue to be the end of the list instead of the beginning. That is adding to the end of a singly linked and removing from the beginning of a singly linked list can both be implemented in O(1) time.


A doubly linked list does not have constant insertion on the end unless you keep a pointer to the last element, all that list has is a pointer pointing back down the list making insertion easier.
Was This Post Helpful? 0
  • +
  • -

#6 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2153
  • View blog
  • Posts: 3,311
  • Joined: 21-June 11

Re: Time complexity for linked lists

Posted 18 April 2013 - 05:06 PM

View PostRomeo1, on 19 April 2013 - 01:26 AM, said:

A doubly linked list does not have constant insertion on the end unless you keep a pointer to the last element


And why wouldn't you do that? I've never seen an implementation of a doubly linked list that did not keep a pointer to the last node.

Note that even the chart you've posted agrees that insertion at the end is O(1) for linked lists.

This post has been edited by sepp2k: 18 April 2013 - 05:08 PM

Was This Post Helpful? 0
  • +
  • -

#7 Romeo1  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 30-September 10

Re: Time complexity for linked lists

Posted 18 April 2013 - 05:12 PM

View Postsepp2k, on 18 April 2013 - 05:06 PM, said:

View PostRomeo1, on 19 April 2013 - 01:26 AM, said:

A doubly linked list does not have constant insertion on the end unless you keep a pointer to the last element


And why wouldn't you do that? I've never seen an implementation of a doubly linked list that did not keep a pointer to the last node.

Note that even the chart you've posted agrees that insertion at the end is O(1) for linked lists.


yes my chart assumes a correctly implemented linked list, but these questions say nothing about this, so I took the worst case senario.
Was This Post Helpful? 0
  • +
  • -

#8 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7999
  • View blog
  • Posts: 13,701
  • Joined: 19-March 11

Re: Time complexity for linked lists

Posted 18 April 2013 - 05:15 PM

Oh heavens, a geek getting pedantic. What will they think of next?
Was This Post Helpful? 0
  • +
  • -

#9 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2153
  • View blog
  • Posts: 3,311
  • Joined: 21-June 11

Re: Time complexity for linked lists

Posted 19 April 2013 - 03:34 AM

Hm, actually looking at the assignment again, I notice that it asked about enqueue and dequeue and gives O(n) as the correct answer for singly linked list. So it must assume that doubly linked lists have a reference to the end, but singly linked lists do not. That's... arbitrary.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1