The C++Course provides a general introduction to programming in C++. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details. 
Home Queues and Priority Queues Veneer  
Veneer
This example demonstrates one of the nice things about a veneer, which is that it is easy to implement, and one of the dangers of using a veneer, which is the performance hazard! Normally when we invoke a method we are not concerned with the details of its implementation. But there is one "detail" we might want to knowthe performance characteristics of the method. How long does it take, as a function of the number of items in the list? First let's look at removeFirst. Node* removeFirst () {Node* result = head; if (head != null) { head = head>next; } return result; } There are no loops or function calls here, so that suggests that the run time of this method is the same every time. Such a method is called a constant time operation. In reality, the method might be slightly faster when the list is empty, since it skips the body of the conditional, but that difference is not significant. The performance of addLast is very different. void addLast (Node* node) {// special case: empty list if (head == null) { head = node; node>next = null; return; } Node* last; for (last = head; last>next != null; last = last>next) { // traverse the list to find the last node } last>next = node; node>next = null; } The first conditional handles the special case of adding a new node to an empty list. In this case, again, the run time does not depend on the length of the list. In the general case, though, we have to traverse the list to find the last element so we can make it refer to the new node. This traversal takes time proportional to the length of the list. Since the run time is a linear function of the length, we would say that this method is linear time. Compared to constant time, that's very bad.


Home Queues and Priority Queues Veneer 