Need help understanding List class

[Arslan7041]

So my professor has given us the code for a List class (complete with an iterator class inside and everything). Our task is to modify it to make it a doubly linked list as well as add a back pointer.

Right now, all im trying to do is understand this code she has given us. There are a few things that are confusing me, and im hoping you guys can help me out.

#ifndef LLIST_H
#define LLIST_H

#include <iterator>
template <class T>
class List
{
	struct Node
	{
		Node(const T& x,Node* y = 0):m_data(x),m_next(y){}
		T m_data;
		Node* m_next;
	};

	Node* m_head;
public:

	class iterator
	{
		Node* m_rep;
	public:
		friend class List;

		inline iterator(Node* x=0):m_rep(x){}
		inline iterator(const iterator& x):m_rep(x.m_rep) {}
		inline iterator& operator=(const iterator& x)
		{
			m_rep=x.m_rep; return *this;
		}
		inline iterator& operator++()
		{
			m_rep = m_rep->m_next; return *this;
		}
		inline iterator operator++(int)
		{
			iterator tmp(*this); m_rep = m_rep->m_next; return tmp;
		}
		inline T& operator*() const { return m_rep->m_data; }
		inline Node* operator->() const { return m_rep; }
		inline bool operator==(const iterator& x) const
		{
			return m_rep == x.m_rep;
		}
		inline bool operator!=(const iterator& x) const
		{
			return m_rep != x.m_rep;
		}

	};


	List() : m_head(0) {}
	~List() { clear(); }
	void clear() { while (!empty()) pop_front(); }

	inline void push_front(const T&x)
	{
		Node* tmp = new Node(x);
		tmp->m_next = m_head;
		m_head = tmp;
	}
	inline void pop_front()
	{
		if (m_head)
		{
			Node* newhead = m_head->m_next;
			delete m_head;
			m_head = newhead;
		}
	}
	inline bool empty() { return m_head; } // Why are we returning m_head here? List is empty when m_head is = 0, 
//so wont this return a FALSE when list is  empty? 
//And this is opposite of what the empty function is supposed to do?

	inline T& front() { return *begin(); }
	inline const T& front() const { return *begin(); }

	inline iterator begin() { return iterator(m_head); }
	inline iterator end() { return iterator(); } // what is this even returning?? 
//There is no iterator constructor that takes void, so what is this?

	// insert y before x. Intended to parallel vector operation
	void insert (iterator& x, const T& y) {
		Node *tmp = new Node(y, x.m_rep); // Whats even going on here?
//  I've stared at this line for a long time, and am still confused as to what is happening. 

		if (x==m_head) m_head = tmp;
		else {
			Node *p = m_head;
			while (p && p->m_next != x.m_rep) p = p->m_next;
			if (!p) throw std::exception();
			p->m_next = tmp;
		}
	}

	// push back. Intended to parallel vector operation
	void push_back (const T& y) {
		Node *nd = new Node(y, NULL);
		if (!m_head) m_head = nd;
		else {
			Node *p = m_head;
			while (p->m_next) p = p->m_next;
			p->m_next = nd;
		}
	}

};

#endif 

I've stated my questions as comments in the code above. As you can see, there are only 3 specific lines I am having trouble with. Can anyone explain these?

[Peter87]

inline bool empty() { return m_head; } Why are we returning m_head here? List is empty when m_head is = 0, so wont this return a FALSE when list is empty? And this is opposite of what the empty function is supposed to do?

You are correct. It returns the opposite of what you want.

inline iterator end() { return iterator(); } what is this even returning?? There is no iterator constructor that takes void, so what is this?

The constructor has a default argument so if you don't pass an argument it will set the node pointer to null.

Node *tmp = new Node(y, x.m_rep); Whats even going on here? I've stared at this line for a long time, and am still confused as to what is happening.

This line of code creates a new Node object with the value y (the value to be inserted) and the next node pointer equal to x.m_rep (the node pointer of the iterator).

[Arslan7041]

Thank you very much. That cleared up a lot of things.

Now a quick follow up question:

I need to make a push_front function for a DOUBLY linked list. I made it but im not sure if its correct. My questions, once again is in the form of a comment in the code below:

	inline void push_front(const T&x)
	{
		Node* tmp = new Node(x);

		tmp->prev = m_head; // this will point the prev pointer to the m_head variable and not the first node, correct?
		tmp->m_next = m_head->m-next; // this points next to the first node? is this line correct?
		tmp->m_next->m_prev = tmp;
		tmp->m_prev->m_next = tmp;
	}

Please let me know of any errors in the above code as well.

[Arslan7041]

Now that I think about it, do I need to add in my code above:

m_head = tmp; ?

[Peter87]

You probably want to add that line but it's not all that's needed to change. Note that the old head node should be after the newly inserted node which becomes the new head node.

[dhayden]

To figure out what mus be added, you may find it helpful to grab two pens with different colors. Draw the nodes and pointers before you insert with one color. Then draw the new node and the new links in another color. This highlights what changes.

Don't forget the case where you insert into an empty list.

And don't forget to update the back pointer (tail pointer?). Pretty much anywhere that you update the m_head pointer, you must also update the tail pointer.

And for what it's worth, the prof's original iterator class isn't optimal. It's possible to write the class such that insert() always runs in constant time.

[Arslan7041]

Pretty much anywhere that you update the m_head pointer, you must also update the tail pointer.

Really? I thought tail pointer does NOT need to be updated for the push_front, pop_front and insert functions as they dont affect the tail of the list at all. Even the insert function given here is done in such a way that a new node inserted will never be at the end (i.e. there will always be a node after it).

I did however update tail (back pointer) for the push_back function.

[Peter87]

You only need to update the tail pointer if the inserted element is also the last element in the list.

[dhayden]

You also need to update the tail pointer when popping the last item in the list. That means that push_front, op_front and insert all need update the tail pointer (although only in special circumstances).