Tell me more ×
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
1  
Your title doesn't match your question - you ask about SinglyLinkedLists, but your code uses a doublyLinkedList. – Bobson Mar 28 at 15:03

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. – tomdemuyt Mar 28 at 14:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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