current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

Here is my implementation for a queue using doubly linked list:

QUEUE-EMPTY
if L.head == NIL
    return True
else return False

QUEUE(x):
if L.head == NIL:
    x.prev = NIL
    L.head = x
else
    cur = L.head
    while cur.next != NIL
        cur = cur.next
    cur.next = x
    x.prev = cur
    x.next = NIL

DEQUEUE():
x = L.head
L.head = x.next
x.next.prev = L.head
return x

How to improve ? Is that correct ?

Is there a mean to make QUEUE O(1) ?

thanks !!

share|improve this question

closed as off-topic by Jamal♦ Nov 21 '13 at 16:39

  • This question does not appear to be a code review request within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.
1  
Your title doesn't match your question - you ask about SinglyLinkedLists, but your code uses a doublyLinkedList. –  Bobson Mar 28 '13 at 15:03
    
Question should be tagged with its appropriate language. –  Jamal♦ Nov 21 '13 at 16:39
add comment

1 Answer

up vote 5 down vote accepted

You can make QUEUE O(1) by maintaining a pointer to the tail. Then you can always append to the tail without walking the whole queue.

Also, in DEQUEUE, I think you want to set x.next's prev to nil, not to itself - to be consistent with how you're handling the empty case in QUEUE:

x.next.prev = NIL
share|improve this answer
    
He is also not setting x.next in QUEUE when L.head == NIL. –  konijn Mar 28 '13 at 14:11
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.