Major problem:
You are breaking the rule of three (or five).
Your class contains a RAW pointer. This means you need to override Copy Constructor/Assignment operator/Destructor. You missed the assignment operator.
{
List<int> x;
List<int> y;
x = y; // This is going to cause problems.
}
// At this point when it is destroyed.
// As both x and y point at the same begin object.
Since you have a valid copy constructor you can just use the copy-and-swap idiom to build the assignment operator:
List& operator=(List rhs) // pass by value to get copy
{
std::swap(begin, rhs.begin); // Now swap all data members.
// You could write your own swap member
return *this;
}
Sentinels
You create your list with an initial 'Sentinel' value. This is a common technique to remove the need to check for NULL pointers in your code and can make the other functions easier to write (as you don't need to check for NULL). BUT to use it usefully, the list needs to be circular (last element points at first) and you must always have this unused 'Sentinel' node.
When you use this technique you should never use the sentinel as a value holding node. You should always skip over it. Your loop then is always from begin->next (as the first node) until begin (when you reach begin again you have gone one past the last node (hence the need for a circle).
Unfortunately your code is a mix of using sentinel and using NULL terminated list. You need to pick one and stick with it. Using a sentinel makes the code much easier to write (as you don't need to check for NULL and special case the empty list).
Need a tail pointer
You currently only have a head pointer.
This means when you insert into the list you always chain all the way to the end before inserting. This makes an operation that could be O(1) be O(n). Most list implementations use head/tail pointer or use a doubly linked list (one chain for each direction). This makes finding the tail trivial and maintaining the extra pointer has practically no cost.
Other comments:
The rest of the code assumes you were trying to use a sentinel value to make the use of the list more efficient. If you want to use NULL to indicate the end of a list rather than a sentinel, the comments will change slightly (but using sentinels is the better solution so I will move ahead from there).
Not all types have a default value (or are default constructable). So you need two versions of your node class. One to use as the sentinel and one to use that holds the data payload. Let us assume that Node is the version that holds the payload and inherits from the base class that just contains pointer information:
When constructing Nodes:
// Remove the default constructor.
// When creating a payload node it should be initialized with a value.
Node() : next(0) { }
// The constructor should take a value by const reference
// This will make sure that expensive to copy objects are not over copied.
// You should also pass a pointers to link it into the list.
// At the point it is constructed you should have that information by putting
// this code in the constructor you will make creation and use easier.
Node(T value) : val(value), next(0) { }
// Since Node is a publicly available class and not designed to be copied
// You should (and have) disable the copy constructor and assignment operator.
//
// Alternatively if you make Node a private Type inside the List class then
// this is not needed.
private:
Node(const Node& nd) { }
Node& operator=(const Node& nd) { }
Construct list and insert sentinel as expected.
List() {
begin = new BaseNode(); // Note I changed the type BaseNode
// Note: BaseNode constructor will make next point
// back at itself.
}
When you use this constructor, you should also insert a sentinel. So the list always has a sentinel value no matter how it is created. Then you can just add the value as normal.
List(T initval) {
begin = new BaseNode();
addVal(initval);
}
Adding a node is a common task with its own specific method addVal() of doing this. Use this common method to do the actual work of adding a node. This prevents duplicating of code and makes sure that adding a node is consistently done (Note your current addVal() is not very efficient but I will address that separately.
List(const List& inp) {
begin = new Node<T>(inp.begin->val);
Node<T> *tempInitial = inp.begin->next;
Node<T> *tempFinal = begin;
while(tempInitial->next) {
tempFinal->next = new Node<T>();
tempFinal = tempFinal->next;
tempFinal->val = tempInitial->val;
tempInitial = tempInitial->next;
}
}
// Could look like this:
List(List const& rhs)
{
begin = new BaseNode<T>(); // sentinel.
Node<T>* begin = inp.begin;
for(Node<T>* loop = begin->next; loop != begin; loop = loop->next);
{
addVal(loop->val);
}
}
In your version here you seem to overwrite the sentinel.
This is wrong as if you add 0 multiple times it will only be added once. Leave the sentinel alone and just concentrate on adding a new node each time.
void addVal(const T& val) {
if(!begin->next && begin->val == 0) {
begin->val = val;
}
Here you assume that last node is NULL-terminated.
But in the copy constructor you assume that the list is circular.
else {
Node<T> *temp = begin;
while(temp->next) {
temp = temp->next;
I would go with the circular list (using sentinels). Also each time you add a value you must traverse the whole list to find the end. It would be easier to keep track of the last value using two pointers in List object; begin (points at the sentinel) and end (points at the last inserted node (or at the sentinel if empty list)).
Using a sentinel the insert becomes.
void addVal(const T& val)
{
Node<T>* last = findlast(begin); // not needed if you have a last member.
Node<T>* newNode = new Node(val, last, begin);
// ^^^^ node before the new node
// ^^^^^ node after the new node.
}
Deleting items from a singly linked list is a pain (as you need the proceeding item). Doubly linked lists are a lot easier (in my opinion) to use because of this. But again you are potentially deleting the sentinel here.
You also search the list twice: the first time you search to find the value, then you search the list to find the node preceding the one you want to delete.
bool deleteVal(const T& val) {
Node<T>* pos = isPresentN(val);
if( pos == 0) return 0;
if(pos == begin) { begin = pos->next; delete pos; return 1; }
Node<T>* temp = begin;
while(temp->next != pos) {
temp = temp->next;
}
You can simplify this and just look for the value by checking the value of the next node. Note: The same code works for a NULL-terminated list (just change begin into NULL).
Node<T>* loop = begin;
while(loop->next != begin && loop->next.val != val)
{
loop = loop->next;
}
// Now loop->next is either begin or points at the node we are looking for.
if (loop->next != begin)
{
Node<T> old = loop->next;
loop->next = old->next;
delete old;
}
