CODEWITHSUNDEEP
c++templatesdata-structurescontainers
Holly
Holly

Reputation: 1976

About my Templated Linked List

Bit of an odd one, I successfully implemented my own templated linked list as an educational exercise a while back. Now I know it works, I've been using it to create a list of nodes that hold "Sprite" objects, and at the time I understood it but I went and looked back at it today and I'm really confused.

If you'd be kind enough to look at my implementation and help me figure out.

How does the program KNOW that _data (in Node) should be assigned an object of NodeType?? (if you'll excuse the poor phrasing) I mean I have that function SetData but I never even use it. And when I PushBack on the list for example, I just create a new Node of ListType, but I never set that node's data. The node constructor doesn't say _data = new NodeType or anything.

And yet I can call GetData() on any node in my list and get a Sprite object back. I mean I know it works, but I've forgotten how! Could someone take a look and remind me? It'd be much appreciated!

Node.hpp:

#if !defined NODE_HPP
#define NODE_HPP


template<typename NodeType>
class Node{

   public:
      Node( Node* prev = 0, Node* next = 0);
      void SetData(NodeType newData);
      NodeType* GetData();
      Node* GetPrev();
      Node* GetNext();

   private:
      template<typename ListType>
      friend class List;

      NodeType _data;
      Node* _prev;
      Node* _next;

};


///implement Node

template <typename NodeType>
Node<NodeType>::Node(Node* prev, Node* next) : _prev(prev), _next(next)
{}
template <typename NodeType>
void Node<NodeType>::SetData(NodeType newData)
{
   _data = newData;
}
template <typename NodeType>
NodeType* Node<NodeType>::GetData()
{
   return &_data;
}
template <typename NodeType>
Node<NodeType>* Node<NodeType>::GetPrev()
{
   return _prev;
}
template <typename NodeType>
Node<NodeType>* Node<NodeType>::GetNext()
{
   return _next;
}
#endif //define

List.hpp

#if !defined LIST_HPP
#define LIST_HPP

#include "Node.hpp"

///since we're creating a template everything must be defined in the hpp

template <typename ListType>
class List
{
   public:
      List();
      bool Empty();
      void PushFront();
      void PushBack();
      void PopBack();
      void ClearList();
      Node<ListType>* GetHead();
      Node<ListType>* GetTail();
      int NumberOfNodes();

   private:
      Node<ListType>* _head;
      Node<ListType>* _tail;
      int _size;

};


///implement List class here
template <typename ListType>
List<ListType>::List() : _head(0), _tail(0), _size(0)
{
}
template <typename ListType>
bool List<ListType>::Empty()
{
   return _size == 0;
}
template <typename ListType>
void List<ListType>::PushFront()
{
   _head = new Node<ListType>( _head , 0 );
   if(Empty()) //this is the start of a new list, need to set _tail as well
      _tail = _head;
   else
      _head->_prev->_next = _head; //set previous nodes _next to new _head


   ++_size;
}
template <typename ListType>
void List<ListType>::PushBack()
{
   _tail = new Node<ListType>( 0 , _tail);
   if(Empty()) //this is the start of a new list, need to set _head as well
      _head = _tail;
   else
      _tail->_next->_prev = _tail; // set old tails _prev to new tail

   ++_size;
}
template <typename ListType>
void List<ListType>::PopBack()
{
   if(!Empty()){
      if(_tail != _head)
      {
         _tail = _tail->_next;
         delete _tail->_prev; //delete memory at old tail
         _tail->_prev = 0; //reassign new tails _prev pointer to null
      }
      else  // We are deleting the last node so treatment is a little different.
      {
         delete _tail;
         _tail = 0; _head = 0;
      }

      --_size;
   }
}
template <typename ListType>
void List<ListType>::ClearList()
{
   while(!Empty())
      PopBack();


}

template <typename ListType>
Node<ListType>* List<ListType>::GetHead()
{
   return _head;
}
template <typename ListType>
Node<ListType>* List<ListType>::GetTail()
{
   return _tail;
}
template <typename ListType>
int List<ListType>::NumberOfNodes()
{
   return _size;
}
#endif //define

Upvotes: 0

Views: 250

Answers (1)

juanchopanza
juanchopanza

Reputation: 227468

The constructor doesn't explicitly do anything about _data, so it default initializes it*. In other words, after construction, _data is a default constructed NodeType. It NodeType were not default constructible, the template specialization wouldn't compile. The program "knows" to do this initialization because hopefully your compiler follows the rules set out in the C++ standard.

As for knowing the type, the compiler essentially replaces NodeType for which ever type you instantiate the template with and creates a new type using this replacement. So Node<std::string> would result in a type where_datais of typestd::string`.

  • if NodeType were a promitive type, then there would be no initialzation, and _data would hold any old garbage value.

Upvotes: 1

Related Questions