Implementation of List in C++, help with push_back()

[failbot]

So, I'm writing an implementation of List in C++ as a programming exercise, so far I have this:

#include <iostream> 
#include <algorithm>

using namespace std;

template <class T> class Link;
template <class T> class List_iterator;

template <class T> 
class List
{
public:
   typedef List_iterator<T> iterator;

   List();
   List(const List<T> & l);
   ~List();

   bool empty() const;
   unsigned int size() const; 
   T & back() const;
   T & front() const;
   void push_front(const T & x);
   void push_back(const T & x);
   void pop_front();
   void pop_back();
   iterator begin() const;
   iterator end() const;
   void insert(iterator pos, const T & x);
   void erase(iterator & pos); 
   List<T> & operator=(const List<T> & l);

protected:
   Link<T> * first_link;
   Link<T> * last_link;
   unsigned int my_size;
};

template <class T>
List<T>::List()
{
        first_link = 0;
        last_link = 0;
        my_size = 0;
}

template <class T>
List<T>::List(const List & l)
{
        first_link = 0;
        last_link = 0;
        my_size = 0;
        for (Link<T> * current = l.first_link; current != 0; current = current -> next_link)
                push_back(current -> value);
}

template <class T>
typename List<T>::iterator List<T>::begin() const
{
        return iterator(first_link);
}

template <class T> 
class Link 
{
private:
   Link(const T & x): value(x), next_link(0), prev_link(0) {}//pg. 204 
                
   T value;     
   Link<T> * next_link;
   Link<T> * prev_link;

   friend class List<T>;
   friend class List_iterator<T>;
};

template <class T> class List_iterator
{
public:
   typedef List_iterator<T> iterator;

   List_iterator(Link<T> * source_link): current_link(source_link) { }
   List_iterator(): current_link(0) { }
   List_iterator(List_iterator<T> * source_iterator): current_link(source_iterator.current_link) { }

   T & operator*();  // dereferencing operator
   iterator & operator=(const iterator & rhs);
   bool operator==(const iterator & rhs) const;
   bool operator!=(const iterator & rhs) const;
   iterator & operator++(); 
   iterator operator++(int);
   iterator & operator--(); 
   iterator operator--(int); 

protected:
   Link<T> * current_link;

   friend class List<T>;
};

template <class T>
T & List_iterator<T>::operator*()
{
        return current_link -> value;
}

template <class T>
List_iterator<T> & List_iterator<T>::operator++()
{
        current_link = current_link -> next_link;
        return *this;
}

template <class T>
void List<T>::push_back(const T & x)
{
    if (empty())
	last_link = first_link;
    else
    {
	last_link->prev_link;
	//prev_link->next_link;
	last_link = first_link;
    }

}

template <class T>
typename List<T>::iterator List<T>::end() const
{
        return iterator(last_link);
}

int main()
{
   List<int> l;

   l.push_back(44);  // list = 44
   l.push_back(33);  // list = 44, 33
   l.push_back(11);  // list = 44, 33, 11
   l.push_back(22);  // list = 44, 33, 11, 22

   List<int> m(l);

   List<int>::iterator itr(m.begin());
   while (itr != m.end()) {
        cout << *itr << endl;
        itr++;
   }
}

But it is not compiling. I am sure that it is my push_back() function that is faulty. Can anyone help me write one that works with the rest of my code?

Thanks in advance guys and girls.

[griswolf]

What happens in push_back when the list is empty? How does what your code says do anything useful? Empty or not, where is T put into the list?

[failbot]

What happens in push_back when the list is empty? How does what your code says do anything useful? Empty or not, where is T put into the list?

I know T has to be put at the end of the list, I'm just not sure how to go about doing it. Can you write a small example or point me towards one that's already been written?

Thanks.

[griswolf]

You need to create a Link<T>, and you need to set its prev_link to point at list's last_link; and the next_link in list's last_link to point at this new Link. That's it.

[failbot]

You need to create a Link<T>, and you need to set its prev_link to point at list's last_link; and the next_link in list's last_link to point at this new Link. That's it.

Thanks,

I've tried doing something like this:

{
link<T> * new_link = new link<T> (x);
prev_link = last_link = new_link;
new_link->next_link = last_link;
}

but when compiled it just tells me that prev_link is undefined in this particular scope. Is there a reason why that would occur? Am I on the right track here?

[griswolf]

Yeah, but you are apparently in that 'too tired to read what's in front of me' state. What object owns prev_link? It isn't the list, so you have to specify. And don't forget your [CODE] button. Or go to the Advanced editor and use the [ICODE] button.

[failbot]

Yeah, but you are apparently in that 'too tired to read what's in front of me' state. What object owns prev_link? It isn't the list, so you have to specify. And don't forget your [C[I][/I]ODE] button. Or go to the Advanced editor and use the [IC[I][/I]ODE] button.[/QUOTE]

I just used this:
Wouldn't it be okay to use list because list and link are friend classes?

template <class T>
void List<T>::push_back(const T & x)
{
    Link<T> * new_link = new Link<T> (x);
    last_link->prev_link = new_link;    
    new_link->next_link = last_link;
}

and now, it's giving me other errors but it doesn't say anything about push_back anymore...

This is what the compiler is throwing back at me:

Undefined symbols:
  "List_iterator<int>::operator++(int)", referenced from:
      _main in ccooykS5.o
  "List_iterator<int>::operator!=(List_iterator<int> const&) const", referenced from:
      _main in ccooykS5.o
  "List<int>::~List()", referenced from:
      _main in ccooykS5.o
      _main in ccooykS5.o
      _main in ccooykS5.o
      _main in ccooykS5.o
ld: symbol(s) not found
collect2: ld returned 1 exit status

Thanks by the way, I know this has gone on much longer than it should.