ClassTemplate With LinkedList??

[JoBe]

Good evening everyone,

This next exercise, I have to do the following:

Write a ClassTemplate for a linked list. Demonstrate it by using two linked lists. The datafield of the first type is int, the second one is double.

What Ive got sofar is this:

#include <iostream>
#include <vector>

using namespace std;

template <class T>

class vec
{
	public:
		vec(T xx = 0, T yy = 0, T zz = 0): x(xx), y(yy), z(zz){}	// Constructor.

		void linklist(T &x, T &y, T &z);
		
		void print() const;

	private:
		T x, y, z;
};

template <class T>
void vec<T>::print() const
{
	cout<< x << " " << y << " " << z <<endl;
}

template <class T>
void vec<T>::linklist(T &x, T &y, T &z)
{
            ??????????	
}

int main()
{
	vec <int> a(1), b(4), c(9), ilist;
	vec <double> d(4.5), e(9.7), f(0.3), dlist;

	linklist(a, b, c);
	linklist(d, e, f);

	return 0;
}

I don't think it really is good, that's why I wanted to ask if someone could point me in the correct direction.

I think I have to use the template <vector>, but, how do I combine that with the template class?????

[Narue]

>Write a ClassTemplate for a linked list.
I think it means write a linked list class that uses templates for the type, not whatever you were trying to do with a vector.

Infusing myself with the power of concentrated ugly, I wrote this for you. Maybe you can glean something out of it for your own project. Yes, I know it's probably way more than you're expected to do:

#include <iostream>

using namespace std;

template <typename T>
class linked_list {
  class Node {
    friend class Iterator;
    friend class linked_list;
  public:
    Node ( T init, Node *link ): data ( init ), next ( link ) {}
  private:
    T data;
    Node *next;
  };

  class Iterator {
    friend class linked_list;
  public:
    Iterator(): node ( 0 ) {}
    Iterator ( Node *link ): node ( link ) {}
    Iterator ( const Iterator& it )
      : node ( new Node ( it.node->data, it.node->next ) ) {}
    Iterator *operator++() { node = node->next; return this; }
    T& operator*() { return node->data; }
    friend bool operator!= ( const Iterator& a, const Iterator& b )
    {
      return a.node != b.node;
    }
  private:
    Node *node;
  };
public:
  typedef Iterator iterator;

  linked_list(): n ( 0 ) {}
  template <typename Iter>
  linked_list ( Iter first, Iter last ): n ( 0 )
  {
    while ( first != last ) {
      push_back ( *first++ );
      ++n;
    }
  }

  void push_front ( const T& item )
  {
    list.node = new Node ( item, list.node );
    ++n;
  }

  void push_back ( const T& item )
  {
    if ( list.node == 0 )
      list.node = new Node ( item, 0 );
    else {
      Node *it = list.node;

      while ( it->next != 0 )
        it = it->next;

      it->next = new Node ( item, it->next );
    }
  }

  iterator begin() { return list; }
  iterator end() { return Iterator(); }
  int size() { return n; }
private:
  iterator list;
  int n;
};

template <typename T, int N>
char (&array(T(&)[N]))[N];

int main()
{
  int a[] = {1,2,3,4,5,6,7,8,9,0};
  double b[] = {1.2,2.3,3.4,4.5,5.6,6.7};

  linked_list<int> list1 ( a, a + sizeof array ( a ) );
  linked_list<double> list2 ( b, b + sizeof array ( b ) );

  linked_list<int>::iterator it1 = list1.begin();

  while ( it1 != list1.end() ) {
    cout<< *it1 <<"->";
    ++it1;
  }
  cout<<endl;

  linked_list<double>::iterator it2 = list2.begin();

  while ( it2 != list2.end() ) {
    cout<< *it2 <<"->";
    ++it2;
  }
  cout<<endl;
}

It's ugly and far from good. I put less than 30 minutes work into it, sue me.

[JoBe]

>> I put less than 30 minutes work into it, sue me.

Nah, I'll let you of the hook, ... this time :cheesy:

Thanks Narue ;)

[JoBe]

Hi Narue,

I know it's been a short while, but, I tried to run your program and it's given me errors when I debugged it.

Could you help me out please and simplify your program so that I could give it ago and see what you're doing and how :?:

[Dogtree]

If you want to make the class look something like a standard C++ container then Narue's code is about as simple as it gets. You define a data structure that holds items and then define an iterator that controls safe traversal of those items. A simpler, but less safe, linked list class would just dole out node pointers as iterators:

#include <iostream>

template <typename T>
struct Node {
  T _item;
  Node *_next;

  Node(const T& item, Node *next)
    : _item(item), _next(next)
  {}
};

template <typename T>
class LinkedList {
  Node<T> *_head;
public:
  typedef Node<T> *iterator;

  LinkedList(): _head(0) {}

  void add(const T& val)
  {
    _head = new Node<T>(val, _head);
  }

  iterator begin() { return _head; }
  iterator end() { return 0; }
};

int main()
{
  LinkedList<int> list;

  list.add(1);
  list.add(2);
  list.add(3);
  list.add(4);

  LinkedList<int>::iterator it = list.begin();

  while (it != list.end()) {
    std::cout << it->_item << '\n';
    it = it->_next;
  }
}

That's not as useful because it involves knowing about the Node class. A good linked list class should hide all of that away so that users only know, or care, about values and iterators.

[JoBe]

Thanks Dogtree,

It's because of Narue's example has so manny whistles and bells that I couldn't make anything out of it, also, I couldn't debug it and give it a spin, usually I can comprehend it much better when Ive got an example.

Didn't say that it was a bad example ;)

I do wonder wether it's not possible to use the container <vector> in this exercise or is this used only when you have to manually input variables?

[Dogtree]

It's not about bells and whistles. If you want that stuff, take a look at the std::string class. Narue's list is actually very sparse, it just seems complicated because of the nested Node and Iterator helper classes. The only operations that the list class itself supports are:

• Create an empty list
• Create a list from a range
• Add a value to the front of the list
• Add a value to the end of the list
• Get the size of the list
• Define a [first, last) range

It doesn't handle insertion anywhere except the front and back, it doesn't handle deletion of any values, it lacks a copy constructor, assignment operator, destructor, and a good number of fundamental operations for a linked list. The standard std::list class is pretty generic, and it sports 12 types, four constructors, a destructor, 43 member functions, and 7 non-member functions. That isn't including the functionality required of the bidirectional iterators that the std::list class requires. With that in mind, especially after seeing and/or writing the standard std::list, Narue's class is practically trivial. ;)

I don't see how vector would be a part of the exercise. It isn't, and can't be, implemented as a linked list, so unless you want to use a vector for something other than the implementation of your linked list class, it wouldn't fit in the exercise.

[JoBe]

Was wondering wether you could help me out with a few questions Dogtree?

class LinkedList 
{
  Node<T> *_head;
public:
...

1) By writing Node above public, does that mean it's automatically private?

2) Why do you use and underscore before a member? Habit?

3) Isn't it possible to write the definition of iterator on the top of main in combination with list?

Like you can write

int i = 0, j, k = 4;

Why can't I write

LinkedList<int> :: iterator it, list;

:?:

4) When I rewrite the code and come towards 'std::', I get a list with several possibility's.
a) What exactly are those several options.
b) Why isn't cout included in that list but still possible to use?

Thanks for the help.

[Dogtree]

1) Yep, the default access for a class is private, so unless you specify otherwise, it's private. It's the opposite for a struct though, where the default is public.

2) I use it to differentiate between data members and parameters or local variables.

3) Yes, but it's good practice to initialize objects when you create them. Otherwise you would create an empty iterator, then assign it a value as opposed to simply creating an initialized iterator, which can be more efficient.

4) That sounds like an autocomplete feature for your environment. How it works depends on which environment you use, and what version of the environment you're at.

4a) That's a list of the names in the std namespace. Basically every available name in the namespace should be included if the list is complete.

4b) That's up to your implementation. For example, while your autocomplete doesn't show cout, mine does.