Linked List Queue Implementation

Question

I implemented a Queue using linked list data structure. This is also my first time using templates in C++.

OVERVIEW

Queue is a data-structure that supports only minimal functionalites such as push, pop, front, back, empty and size.

PURPOSE

1. I aim to have a deeper understanding of templates in C++
2. I aim to make it look and feel close to the standard library's implementation in terms of memory usage, speed and readability

MAJOR CONCERNS

1. I initially didn't want to write the implementation of Queue in its header files, but it resulted to all sort of errors. Can Implementation be seprated from its interface whilst using templates?
2. The standard library performance was twice as better as mine. What may be reasons?

ListNode.h

#ifndef LINKEDQUEUE_LISTNODE_H_
#define LINKEDQUEUE_LISTNODE_H_
template< typename T > struct ListNode
{
 ListNode() : next_ptr( nullptr ) {}
 T data;
 ListNode *next_ptr;
};
#endif

LinkedQueue.h

#ifndef LINKEDQUEUE_QUEUE_H_
#define LINKEDQUEUE_QUEUE_H_
#include "ListNode.h"
#include <iostream>
#include <initializer_list>
template<typename T> class Queue
{
 friend std::ostream &operator<<( std::ostream &os, const Queue &q )
 {
 ListNode<T> *temp = q.head;
 while( temp != nullptr )
 {
 os << temp->data << " ";
 temp = temp->next_ptr;
 }
 return os;
 }
 private:
 ListNode<T> node;
 ListNode<T> *head, *tail;
 size_t queue_size;
 public:
 Queue() : head( nullptr ), tail( nullptr ), queue_size( 0 ) {}
 Queue( std::initializer_list< T > list ) : Queue()
 {
 for( const T &item : list )
 push( item );
 }
 ~Queue() 
 {
 delete head, tail;
 }
 inline void push( T x )
 {
 ListNode<T> *new_node = new ListNode<T>;
 new_node->data = x;
 
 if( head == nullptr ) head = tail = new_node;
 else
 {
 tail->next_ptr = new_node;
 tail = new_node;
 }
 ++queue_size;
 
 }
 inline void pop()
 {
 if( head == nullptr ) throw std::out_of_range( "Queue is empty" );
 
 ListNode<T> *temp = head;
 if( head == tail ) head = tail = nullptr;
 else head = head->next_ptr;
 delete temp;
 --queue_size;
 }
 inline T& front()
 {
 if( head != nullptr ) return head->data;
 else throw std::out_of_range( "Queue is empty" );
 }
 inline T& back()
 {
 if( tail != nullptr ) return tail->data;
 else throw std::out_of_range( "Queue is empty" );
 }
 inline bool empty()
 {
 if( head == nullptr ) return true;
 return false;
 }
 inline size_t size() { return queue_size; }
};
#endif

main.cpp

#include "LinkedQueue.h"
#include <iostream>
#include <chrono>
#include <string>
#include <queue>
int main()
{
 auto start = std::chrono::high_resolution_clock::now();
 Queue< int > q;
 for( int i = 0; i != 1000000; ++i )
 q.push( i );
 std::cout << "Size of queue is " << q.size() << "\n"; 
 std::cout << "Front of queue: " << q.front() << "\n";
 std::cout << "Back of queue: " << q.back() << "\n";
 std::cout << "Queue is empty: " << std::boolalpha << q.empty() << "\n";
 for( int i = 0; i != 1000000; ++i )
 q.pop();
 std::cout << "Queue is empty: " << std::boolalpha << q.empty() << "\n";
 auto end = std::chrono::high_resolution_clock::now();
 auto elapsed = std::chrono::duration_cast<std::chrono::microseconds>( end - start );
 std::cout << "\nMy runtime : " << elapsed.count() << "ms";
 std::cout << "\n\n";
 start = std::chrono::high_resolution_clock::now();
 std::queue<int> q2;
 for( int i = 0; i != 1000000; ++i )
 q2.push( i );
 std::cout << "Size of queue is " << q2.size() << "\n"; 
 std::cout << "Front of queue: " << q2.front() << "\n";
 std::cout << "Back of queue: " << q2.back() << "\n";
 std::cout << "Queue is empty: " << std::boolalpha << q2.empty() << "\n";
 for( int i = 0; i != 1000000; ++i )
 q2.pop();
 std::cout << "Queue is empty: " << std::boolalpha << q2.empty() << "\n";
 end = std::chrono::high_resolution_clock::now();
 elapsed = std::chrono::duration_cast<std::chrono::microseconds>( end - start );
 std::cout << "\nStandard library runtime : " << elapsed.count() << "ms";
 std::cout << "\n\n";
}

On executing main, the following output were produced

Size of queue is 1000000
Front of queue: 0
Back of queue: 999999
Queue is empty: false 
Queue is empty: true
My runtime : 75378ms
Size of queue is 1000000
Front of queue: 0
Back of queue: 999999
Queue is empty: false
Queue is empty: true
Standard library runtime : 55720ms

Compiled and executed using std=c++14 on a unix operating system

• Loki Astari: More importantly than C++ version did you do timings with optimized builds?
• theProgrammer: No, I didn't use optimized builds.
• Loki Astari: Then the numbers are not really useful to make a comparison with.

Answer 1

First of all, this is well-written code.

Ordering members of a class

Currently, your Queue class has the following order

class Queue
{
 private:
 // private stuff
 
 public:
 // public stuff
 
};

A lot of C++ programmers, including me, like to have public declarations first.
To quote from this thread on Stack Overflow

It's my opinion, and I would wager a guess that most people would agree, that public methods should go first. One of the core principles of OO is that you shouldn't have to care about the implementation. Just looking at the public methods should tell you everything you need to know to use the class.

class Queue 
{
 public:
 //...
 private:
 //...
}

---

Use a constant reference

take your push() function as an example

inline void push(T x);

Me, a random C++ developer decides to use your library and creates a queue in the following manner

class My_HUGE_class
{
 // ...
};
int main()
{
 Queue < My_Huge_class > foo;
 My_Huge_class x;
 foo.push(x);
}

Look at what you've done! You have just copied the whole x object when the user merely tried to append something. A really expensive operation!

If you had a doubt whether inlining the function would change that, no it won't. You should always pass by a constant reference.

void push(const T& x);

This will avoid any unnecessary copies.

---

Delete your linked list

This one is important

~Queue()
{
 delete head;
 delete tail;
}

• Edit: As pointed out by @1201ProgramAlarm in the comments, you can't use a single delete keyword for multiple pointers - delete x,y, you will have to use one for each.

There is a problem here, assume you have a Queue<int> x

After deletion, look at what happens

ll

You deleted the head and tail, everything else is floating around since it doesn't get deleted automatically.
<You need to traverse through the list, and delete the nodes one by one. Here is the implementation

void deleteList() 
{ 
 ListNode<T> * current = head; 
 ListNode<T> * next; 
 while (current != NULL) 
 { 
 next = current->next; 
 delete current;
 current = next; 
 } 
 head = NULL; 
 tail = NULL;
} 

---

Should you overload the << operator?

I strongly believe that this is a bad idea. I can explain in a very simple manner

Queue < int > a{1,2,3,4,5};
Queue < int > b{5,4,3,2,1};
std::cout << a; // valid!
Queue < Queue < int > > c{a,b};
std::cout << b; // illegal `<<` operator for class!

Your overload will only work for types that can be printed using <<, nothing else at all.

---

Nitpicks

inline T& front()
{
 if (head != nullptr) return head->data;
 else throw std::out_of_range("Queue is empty");
}
inline T& back()
{
 if (tail != nullptr) return tail->data;
 else throw std::out_of_range("Queue is empty");
}

The else isn't necessary here, because if the previous condition is true, the control never reaches the front.

inline T& front()
{
 if (head != nullptr) return head->data;
 throw std::out_of_range("Queue is empty");
}
inline T& back()
{
 if (tail != nullptr) return tail->data;
 throw std::out_of_range("Queue is empty");
}

• consider using const - inline bool empty() const if you aren't modifying any member variables

• it is always good practice to have a comment after your endif to state which if it ends

---

Copy constructor

consider this scenario

Queue < int > a{1, 2, 3, 4, 5};
Queue < int > b(a);
std::cout << b;

On my visual c++ compiler, this directly triggers an assertion and fails. You haven't declared a constructor in Queue that takes in another Queue, so C++ did that for you. But this performs a shallow copy. Very bad for these kinds of classes

This is because shallow copies of a pointer just copy the address of the pointer -- it does not allocate any memory or copies the contents being pointed to!

You must define your own copy constructor

---

More functionality

A few things I would like to see

• Overload of the equality operators to compare two lists
• Ability to delete a single node

Regarding splitting into a .cpp file

You have defined all the functions in your header file, after reading your question

Can Implementation be separated from its interface whilst using templates?

No :(, not neatly at least. Do read the link I cited.

That is the price you pay with templates,

---

Comparing to the STL library

^{all code here is from the Standard Template library}

Let's see what actually happens when you create a std::queue in your tests.

if you see the constructor of queue

template <class _Ty, class _Container = deque<_Ty>>
class queue;
///
template <class _Ty, class _Container>
class queue {
};

This means that when you created your queue<int>, you just created a new deque. So when you do .push() in a queue, whats really happening is just push_back(), which is defined in class deque. If you have a look at those functions

 void push_front(_Ty&& _Val) {
 _Orphan_all();
 _PUSH_FRONT_BEGIN;
 _Alty_traits::construct(_Getal(), _Unfancy(_Map()[_Block] + _Newoff % _DEQUESIZ), _STD move(_Val));
 _PUSH_FRONT_END;
 }
 void push_back(_Ty&& _Val) {
 _Orphan_all();
 _Emplace_back_internal(_STD move(_Val));
 }

The code is already getting out of control. Time to stop

std::deque is not a linked list. It is a circular buffer, which is very different from a linked list, which is already extremely in-efficient

Hence, it is not a fair comparison. A deque is more like a vector. Both of them are fundamentally very different.

std::deque vs std::list in C++.

• Loki Astari: It's my opinion, and I would wager a guess that most people would agree. I disagree: Private members first. Public methods. Private methods. Is the best order. There should be very few private members so putting them at the top is not an issue and they are easily ignored it you just want the public interface (for why see below). Then public methods as this is what most people want to read. Private methods last as they may be large and inconsequential to a lot of readers.
• Loki Astari: The reason to put private members first is to make the job of code review and validation easy for reviewers and people that are interested in how the code works. The first thing I check is that the constructors/destructors and assignment operators all work correctly with the members and the object is initialized correctly. Having to scroll to the bottom then scroll to the top and jump backwards and forwards to validate these is harder when they are not next to the initialization routines (which are usually the first public methods).
• Loki Astari: Don't agree with your logic for not overloading the output operator. Its pretty standard. Just because you may not always be able to print out members does not mean I don't want to be able to print out a container.
• Loki Astari: When mentioning the issue with the copy constructor (self copy and shallow copy). You should talk about the rule of three.
• Loki Astari: Can Implementation be separated from its interface whilst using templates? Yes. Easily. Just use a *.tpp file for the implementation. This is included by the header file. Relatively common for non trivial templates. In this case its not worth it.

Answer 2

Comments:

I aim to have a deeper understanding of templates in C++

Good example to use to develop these skills:

---

I aim to make it look and feel close to the standard library's implementation in terms of memory usage, speed and readability.

That will be harder. You have the same characteristics as std::list while the standard version std::queue uses a std::deque as the underlying container that has very different characteristcs.

See this question for the differences: What are the complexity guarantees of the standard containers?

The standard library performance was twice as better as mine. What may be reasons?

Though they will look very similar. The technique of creating a new node dynamically for every push (std::list) is relatively expensive. This cost is amortized by allocating space for a bunch of objects (std::dequeue) in one go and then using them up as you need them.

The other benefit is locality of reference. In a (std::deque) objects are close to each other and thus likely to more efficiently accessed because of hardware caching that will make sure objects close to each other become available quicker.

---

I initially didn't want to write the implementation of Queue in its header files, but it resulted to all sort of errors. Can Implementation be seprated from its interface whilst using templates?

It can. But for such a simple class I would not bother.

// LinkeddList.h
#ifndef INCLUDE_GUARD
#define INCLUDE_GUARD
namespace Stuff
{
 class LinkedList
 {
 // STUFF
 public:
 void push(int);
 };
}
#include "LinkedList.tpp"
#endif
// LinkedList.tpp
#ifndef INCLUDE_GUARD
#error "You should include LinkedList.h" not this file.
#endif
inline void Stuff::LinkedList::push(int x)
{
 // STUFF
}
....

---

Overview

You have missed the rule of three.
i.e. CopyConstruction and Copy Assignment does not work.

You have not considered move semantics. Big objects are copied into your queue. You could make this a lot more efficient by moving objects into your queue.

Once you have added move semantics you need to remember the rule of five.

The ListNode type is tightly coupled to the Queue type. There is no benifit to exposing the ListNode to users of your class as this simply locks you into maintaining for all future versions (what happens if you want to change it to doubly linked at some future time). Make this a private member of the Queue class so that your implementation details don't leak.

Code Review

Please add a namespace to wrap your personal stuff.

---

That is a long line with lots of data:

template< typename T > struct ListNode

Normally I would see this:

template<typename T>
struct ListNode

---

Sure that's a constructor:

 ListNode() : next_ptr( nullptr ) {}

But why not initialize all members?

The problem this causes is that if T does not have a default constructor (A constructor that takes no arguments) you can not create objects of ListNode. So I would add a constructor that allows you to pass the data object.

So you should do:

 ListNode(T const& data): data(data), next_ptr( nullptr ) {}
 ListNode(T&& data): data(std::move(data), next_ptr( nullptr ) {}

But looking at your code you always set next_ptr just after creating the node. Why not then pass the next pointer as an argument to the constructor to simplify this processes.

 ListNode(T const& data, ListNode* next): data(data), next_ptr( next ) {}
 ListNode(T&& data, ListNode* next): data(std::move(data), next_ptr( next ) {}

That's great. It now does everything you need. But there is already a constructor that does this that is implemented automatically by the compiler. So why have a constructor. Just use the default implementation and it will do all the work for you.

struct ListNode
{
 T data;
 ListNode *next_ptr;
};

---

What is this used for?

 ListNode<T> node; // Were you planning on using a sentinel?

---

OK. head and tail.

 ListNode<T> *head, *tail;

Why be lazy and squeeze this on one line. Make it easy to read put it on two. All coding standards you find will also specify the same thing. There is no reason to do this and make it hard to read.

---

Is size_t always in the global namespace?

 size_t queue_size;

Nope. You can force that by including certain headers. But do you want to do that with C++ code where all the other types are in the std namespace? Use std::size_t.

---

This doe's not delete the queue.

 ~Queue() 
 {
 delete head, tail;
 }

You are missing all elements that are not head/tail.

---

Don't use inline here.

 inline void push( T x )

All method declarations in a class are already inline by default. And inline does not mean inline the code it tells the linker there may be multiple definitions in object files for this function it they can safely be ignored.

The use of inline for inline-ing code is redundant. The compiler already makes the best choices and does it automatically (better than us puny humans). People may argue that there are other keywords for forcing inlining sure. But don't think humans make the choice of adding those compiler specific commands (unless your an idiot human). These are added once you have proved the compiler is making an non optimal choice you want to force it one way or another (that is hard work).

---

As noted before you should probably pass by const reference or r-value reference for efficiency.

 void push(T x) // The parameter is copied here.
 // use
 void push(T const& x) // pass a reference remvoe one copy. 
 void push(T&& x) // pass by r-value ref allow move.

---

I would simplify your push to:

 void push(T const& x)
 {
 head = new ListNode<T>(x, head);
 if (tail == nullptr) {
 tail = head;
 }
 ++queue_size;
 }
 void push(T&& x)
 {
 head = new ListNode<T>(std::move(x), head);
 if (tail == nullptr) {
 tail = head;
 }
 ++queue_size;
 }

---

Sure you can check the operation is valid.

 inline void pop()
 {
 if( head == nullptr ) throw std::out_of_range( "Queue is empty" );

But the standard libraries don't. They allow you to break the users code here. The logic is there is a a way for them to check externally empty() and they should be using this. Its their fault if they are bad programmers.

In C++ the standard behavior is that code should be optimal in all situations. Consider this situation:

 while(!queue.empty()) {
 queue.pop();
 }

Why are you making me pay the price of a check inside pop() when I have already payed the price externally. Its twice as expensive as it needs to be.

Now we do understand there are beginners out there. So we also provide methods that do check for situations where it would be nice for the interface to perform the check:

Example:

 for(int loop = 0;loop < vec.size(); ++loop)
 std::cout << "Loop: " << loop << " " << vec[loop] << "\n"; // No check on accesses.
 std::cout << "Loop: " << loop << " " << vec.at(15) << "\n"; // Checked accesses.

The std::vector provides two methods to accesses elements. Once is checked you can use this in situations where you have not done the check externally. While the other is not checked and can be used when you know the input is always in range.

 T& operator[](int index);
 T& at(int index);

---

---

Same argument on checking here:

 inline T& front()
 {
 if( head != nullptr ) return head->data;
 else throw std::out_of_range( "Queue is empty" );
 }
 inline T& back()
 {
 if( tail != nullptr ) return tail->data;
 else throw std::out_of_range( "Queue is empty" );
 }

---

Functions that do not change the state of an object should be marked const. Thus when you pass the Queue by const reference to a function you can still accesses functions that don't mutate the object.

The obvious functions here are:

 std::size_t size() const { return queue_size;} // No change in state.
 bool empty() const; // This never mutates the object.
 //
 // Should be able to tell if a Queue is empty and 
 // its size even when you only have a const reference
 // to the obejct

Less obvious are the front() and back() methods. Here you can have two modes. There can be a mutating version that allows you to mutate the members in the queue (if you want that functionality (not sure you do in a queue)).

 // Mutatable accesses
 T& front() {return head->data;}
 T& back() {return tail->data;}
 // Non Mutatable accesses
 T const& front() const {return head->data;}
 T const& back() const {return tail->data;}

---

This is an anti pattern:

 if (test) {
 return true;
 }
 else {
 return false;
 }

You can simplify it to:

 return test;

So lets look at empty():

 bool empty()
 {
 if( head == nullptr ) return true;
 return false;
 }
 // Simplify to:
 bool empty() const
 {
 return head == nullptr;
 }

HowTo

Queue.h

#ifndef THORSANVIL_QUEUE_H
#define THORSANVIL_QUEUE_H
 
#include <iostream>
#include <initializer_list>
namespace ThorsAnvilExamples
{
template<typename T>
class Queue
{
 struct ListNode
 {
 T data;
 ListNode *next_ptr;
 };
 template<typename E>
 class iteratorBase
 {
 ListNode* data;
 public:
 iteratorBase(ListNode* d): data(d) {}
 E& operator*() {return data->data;}
 E* operator->() {return &data->data;}
 iteratorBase& operator++() {data = data->next_ptr;return *this;}
 iteratorBase operator++(int) {iterator tmp(*this);++(*this);return tmp;}
 bool operator==(iteratorBase const& rhs) {return data == rhs.data;}
 bool operator!=(iteratorBase const& rhs) {return data != rhs.data;}
 };
 private:
 ListNode* head = nullptr;
 ListNode* tail = nullptr;
 std::size_t qsize = 0;
 public:
 Queue()
 {}
 Queue(std::initializer_list<T> list)
 {
 for(T const& item: list) {
 push(item);
 }
 }
 Queue(Queue const& copy)
 {
 for(T const& item: copy) { // Add begin() and end()
 push(item);
 }
 }
 Queue& operator=(Queue const& copy)
 {
 Queue tmp(copy);
 swap(tmp);
 return *this;
 }
 Queue(Queue&& move) noexcept
 {
 swap(move);
 }
 Queue& operator=(Queue&& copy) noexcept
 {
 swap(copy);
 return *this;
 }
 void swap(Queue& other) noexcept
 {
 using std::swap;
 swap(head, other.head);
 swap(tail, other.tail);
 swap(qsize, other.qsize);
 }
 ~Queue() 
 {
 ListNode* old;
 while(head != nullptr) {
 old = head;
 head = head->next_ptr;
 delete old;
 }
 }
 friend void swap(Queue& lhs, Queue& rhs)
 {
 lhs.swap(rhs);
 }
 using iterator = iteratorBase<T>;
 using const_iterator = iteratorBase<T const>;
 iterator begin() {return iterator{head};}
 const_iterator begin() const {return const_iterator{head};}
 const_iterator cbegin()const {return const_iterator{head};}
 iterator end() {return iterator{nullptr};}
 const_iterator end() const {return const_iterator{nullptr};}
 const_iterator cend() const {return const_iterator{nullptr};}
 void push(T const& x) {add(new ListNode{x, head});}
 void push(T&& x) {add(new ListNode{std::move(x), head});}
 template<typename... Args>
 void push(Args&&... args) {add(new ListNode{T(std::move(args)...), head});}
 void pop()
 {
 ListNode* old = head;
 head = head->next_ptr;
 delete old;
 --qsize;
 }
 T const& front() const {return head->data;}
 T const& back() const {return tail->data;}
 bool empty() const {return head == nullptr;}
 std::size_t size() const {return qsize;}
 void print(std::ostream& str = std::cout) const
 {
 if (head) {
 str << head->data;
 for(ListNode* temp = head->next_ptr; temp != nullptr; temp = temp->next_ptr) {
 str << " " << temp->data;
 }
 }
 }
 friend std::ostream &operator<<(std::ostream &str, const Queue &q)
 {
 q.print(str);
 return str;
 }
 private:
 void add(ListNode* newhead)
 {
 head = newhead;
 if( tail == nullptr ) {
 tail = head;
 }
 ++qsize;
 }
};
}
#endif