COMP 250 Lecture Notes - Lecture 18: Linked List, Double-Ended Queue

• School: McGill University
• Department: Computer Science (Sci)
• Course: COMP 250
• Professor: Mathieu Blanchette

Document Summary

Void enqueue(object o): add o to rear of queue. Object dequeue(): removes objects at front of queue; exception thrown if queue is empty. Object front(): returns object at front of queue but does not remove it from the queue, exception if queue empty int size(): returns the number of objects in the queue. Boolean isempty(): returns true if queue is empty. Front of queue = head, end of queue = tail. With o(1) running time: enqueue addlast(o, dequeue removefirst(, front() getfirst(, empty() empty() With o(n) running time: size() size() Known as a deque, allows insertions and removal from the front and back. O(1) running time: object getfirst(, object getlast(, addfirst(object o, addlast(object o, boolean isempty(, object removefirst() O(n) running time: object removelast() int size() The drawback is that each node is now bigger than before, so more memory will be needed.