Well your code is confusing, but since this is your first linked list, let me help you in implementation. In future posts, post all your code, since I can not see what a method returns, and it is more guessing, no one can help you then.
# include <stdio.h>
# include <iostream>
using namespace std;
struct LinkedListItem
{
LinkedListItem(int c) : content(c), next(nullptr)
{
}
int content;
LinkedListItem * next;
};
struct LinkedList
{
LinkedList() : Start(nullptr), End(nullptr) //initialize it to null, tgis is faster than in body
{}
~LinkedList()
{
//to delete
LinkedListItem * ptrtodelete;
while(Start)
{//while there is something
//archive the current first element
ptrtodelete = Start;
//we move to next item
Start = Start -> next;
delete ptrtodelete;
//i can afford destroying Start (by moving it) because this is destructor
}
//be paranoid
Start = End = nullptr;
}
void AddItem(int i)
{
if(!Start) //or if Start == nullptr
{
Start = new LinkedListItem(i);
End = Start; //both point to the one element
return;
}
LinkedListItem * newelement = new LinkedListItem(i);
End -> next = newelement; //let last item point to this one
End = newelement; //let end point to the last item
}
LinkedListItem * Start; /**< Pointer to first element */
LinkedListItem * End; /**< Pointer to last element */
};
int main()
{
LinkedList l;
l.AddItem(5);
l.AddItem(980);
return 0;
}
Now this is working, can be helpful.
You might consider later on turning it to a template :]
When I compiled it and put to valgrind, this is output
user@Horse:~/Desktop/tmp/AAA$valgrind ./a.out
==11699== Memcheck, a memory error detector
==11699== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==11699== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==11699== Command: ./a.out
==11699==
==11699==
==11699== HEAP SUMMARY:
==11699== in use at exit: 0 bytes in 0 blocks
==11699== total heap usage: 2 allocs, 2 frees, 16 bytes allocated
==11699==
==11699== All heap blocks were freed -- no leaks are possible
==11699==
==11699== For counts of detected and suppressed errors, rerun with: -v
==11699== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
user@Horse:~/Desktop/tmp/AAA$
Now lets see why...? And how this works...?
Each item in my list has a pointer to another element. Last node has pointer set to null, and, if list is empty,
Start
variable is null.
Now in
void AddItem(int i)
I have to check for one special case. If there are no items in list.
Then, I create new item, and return, as adding is done. (I will explaing
End
later)
If a node is there, already, in theory, I would have to traverse all the nodes up to end, to get to last node, being able to link there new element.
That would take me N steps, assuming we have N items in list. That is called complexity in the worst case, and is called O(n) wich stands for Omikron mathematic function.
It simply tells you: From all situations that can happen, if I choose the worst one, then the metdos will take me N steps, but that is maximum. Pretty bad, right?
Imagine having milion items in there...f. example in a game...
So what I did, it that I created a
End
variable, pointing to last item in a linked list.
Like that, I just link new item to this last node,
End -> next = newelement; //let last item point to this one
And set the End variable to the newly added item, wich is last
End = newelement; //let end point to the last item
Now, the complexity now, is O(1). In theory, it would be +1 for any operation in method, so O(4), but that is called as O(1).
Now I also have to delete the linked list. It can be done in more ways, there is one more way wich is elegant, but I am ok with this cycle.
~LinkedList()
Since we will no longer need a ponter to first element, I can start increasing it. So While the Start element is not null,
while(Start)
we save the pointer - Start.
ptrtodelete = Start;
Let start point to next item, and then delete the item we archived
In theory, End can be used instead ptrtodelete to save one variable (4 or 8 bytes for the pointer)
Now I will ask you...what is complexity of this...? If you answered O(n) where n is number of items, you were correct
Last thing, you can see that in constructor
LinkedList() : Start(nullptr), End(nullptr)
I initialize the variables after double-dot. Why not like this...?
LinkedList()
{
Start = nullptr;
End = nullptr;
}
The reason is, looking at code above: A new Listitem is created, code goes to constructor.
A Start and End variables are set to random values. That just is what happens.
Then, we in body change them to null (4 operations).
But considering the example above this one,
A ListItem is created, and values to Start and End are assigned nullptr.
Those are 2 operations.
It wont save you too much, but having huge project, game maybe, at milion allocations, it can save something.
This is incredible thing we were learnt at my faculty, and I love it, because as I looked around, I did not find this yet anywhere on internet. Now I am sharing it with you guys :]