Thread: link list

Hello,
Was wodering if someone could give me some insight on templates.
The code that is between the **** ****. If I swap the two lines , will it change anything? I think the list is not empty here. This is inserting a node at the front of the list. The new node points to what use to be the first nodeof the list,and copies newPtr to firstPtr so that first firstPtr now points to the new first node of the list. Are they not enterchangable? Or is this a big problem?
What if this was inserting at the back of the list?
''''''''lastPtr->nextPtr = newPtr;''''''''
'''''''lastPtr = newPtr;'''''''
Same differencece, except lastPtr now points to the new last node of the list?

Next question refers to the line ^^^^^delete tempPtrt^^^^.
If I remove it, will the program not be able to reallocate the memory. Or Am I off base, And what would this cause?

If I delete the line:##### value = tempPtr->data;######
This is just removing a noded frrom the front of the list. Is this a memory issue also?

+++++currentPtr->nextPtr = 0;++++++++++. If I remove this line what would happen? I know this sets the nextPtr to 0 in the last node of the list. Will this cause a printing problem?ie, print past the end of the list.

If I swap these 2 lines of code, I haven't the foggiest.
~~~ cout << currentPtr->data << ' ';~~~
~~~currentPtr = currentPtr->nextPtr;~~~

Thanks for your troubles.
Sam T.


#ifndef LIST_H
#define LIST_H

#include <iostream>
#include <cassert>
#include "listnd.h"

using std::cout;

template< class NODETYPE >
class List {
public:
List();
~List();
void insertAtFront( const NODETYPE & );
void insertAtBack( const NODETYPE & );
bool removeFromFront( NODETYPE & );
bool removeFromBack( NODETYPE & );
bool isEmpty() const;
void print() const;
private:
ListNode< NODETYPE > *firstPtr;
ListNode< NODETYPE > *lastPtr;

ListNode< NODETYPE > *getNewNode( const NODETYPE & );
};

template< class NODETYPE >
List< NODETYPE >::List() : firstPtr( 0 ), lastPtr( 0 ) { }

template< class NODETYPE >
List< NODETYPE >::~List()
{
if ( !isEmpty() ) {
cout << "Destroying nodes ...\n";

ListNode< NODETYPE > *currentPtr = firstPtr, *tempPtr;

while ( currentPtr != 0 ) {
tempPtr = currentPtr;
cout << tempPtr->data << '\n';
currentPtr = currentPtr->nextPtr;
^^^^^ delete tempPtr;^^^^^^^
}
}

cout << "All nodes destroyed\n\n";
}

template< class NODETYPE >
void List< NODETYPE >::insertAtFront( const NODETYPE &value )
{
ListNode< NODETYPE > *newPtr = getNewNode( value );

if ( isEmpty() )
firstPtr = lastPtr = newPtr;
else {
**** newPtr->nextPtr = firstPtr;****
****firstPtr = newPtr;****
}
}

template< class NODETYPE >
void List< NODETYPE >::insertAtBack( const NODETYPE &value )
{
ListNode< NODETYPE > *newPtr = getNewNode( value );

if ( isEmpty() )
firstPtr = lastPtr = newPtr;
else {
''''''''lastPtr->nextPtr = newPtr;''''''''
'''''''lastPtr = newPtr;'''''''
}
}

template< class NODETYPE >
bool List< NODETYPE >::removeFromFront( NODETYPE &value )
{
if ( isEmpty() )
return false;
else {
ListNode< NODETYPE > *tempPtr = firstPtr;

if ( firstPtr == lastPtr )
firstPtr = lastPtr = 0;
else
firstPtr = firstPtr->nextPtr;

##### value = tempPtr->data;######
delete tempPtr;
return true;
}
}

template< class NODETYPE >
bool List< NODETYPE >::removeFromBack( NODETYPE &value )
{
if ( isEmpty() )
return false;
else {
ListNode< NODETYPE > *tempPtr = lastPtr;

if ( firstPtr == lastPtr )
firstPtr = lastPtr = 0;
else {
ListNode< NODETYPE > *currentPtr = firstPtr;

while ( currentPtr->nextPtr != lastPtr )
currentPtr = currentPtr->nextPtr;

lastPtr = currentPtr;
+++++currentPtr->nextPtr = 0;++++++++++
}

value = tempPtr->data;
delete tempPtr;
return true;
}
}

template< class NODETYPE >
bool List< NODETYPE >::isEmpty() const
{ return firstPtr == 0; }

template< class NODETYPE >
ListNode< NODETYPE > *List< NODETYPE >::getNewNode(
const NODETYPE &value )
{
ListNode< NODETYPE > *ptr =
new ListNode< NODETYPE >( value );
assert( ptr != 0 );
return ptr;
}

template< class NODETYPE >
void List< NODETYPE >:rint() const
{
if ( isEmpty() ) {
cout << "The list is empty\n\n";
return;
}

ListNode< NODETYPE > *currentPtr = firstPtr;

cout << "The list is: ";

while ( currentPtr != 0 ) {
~~~ cout << currentPtr->data << ' ';~~~
~~~currentPtr = currentPtr->nextPtr;~~~
}

cout << "\n\n";
}

#endif

If I remove the destructor,what effect would that have? Since the destructor just ensures that all ListNode objects in a List object are destroyed. If I remove it, would there be memory issues?



~List();

template< class NODETYPE >
List< NODETYPE >::~List()
{
if ( !isEmpty() ) {
cout << "Destroying nodes ...\n";

ListNode< NODETYPE > *currentPtr = firstPtr, *tempPtr;

while ( currentPtr != 0 ) {
tempPtr = currentPtr;
cout << tempPtr->data << '\n';
currentPtr = currentPtr->nextPtr;
^^^^^ delete tempPtr;^^^^^^^
}
}

cout << "All nodes destroyed\n\n";
}

Please, any insight would be appreciated?

The rule is if you declare memory using the new operator then you should delete or risk memory leaks. Since each new node is added to the list via an insert call and each insert call calls getnewnode and in getnewnode you use the new operator to declare the memory you need for a new node, then yes you need to make sure you delete each node someplace, either in the removefrom functions or the destructor functions, your choice. If your entire program is small and memory during the program is not an issue, then the memory will be released when you turn of the computer, but the end user may not want to turn off the computer every time they use your program, and someday, if you are lucky, you will be involved in a large project where strict memory control is an issue, so get used to it now. At least that's my opinion.

Hi

The code that is between the **** ****. If I swap the two lines , will it change anything?

Code:

if ( isEmpty() ) 
firstPtr = lastPtr = newPtr; 
else { 
**** newPtr->nextPtr = firstPtr;**** 
****firstPtr = newPtr;**** 
}

Yes it is a BIG problem!
if you interchange them then the value of the old 'firstPtr' will be lost forever with all the elemnts in the list too along it. Also the newPtr item will point to itself causing endelss loop when you try to traverce the list next time.

''''''''lastPtr->nextPtr = newPtr;''''''''
'''''''lastPtr = newPtr;'''''''
Same differencece, except lastPtr now points to the new last node of the list?

Yes. Agian a BIG problem. Now the reason is that you will broke the list at that point. the old lastPtr->nextPtr element will point to nowhere and when you try to traverce the list again you will not complete it and also the last element will point to itself again and there will not be any reference to it at all.

If I delete the line:##### value = tempPtr->data;######

the reason in it is to return the value that is kept by the NODETYPE when that list node is removed from the list. The user like to get back it's belongings when he remove the item from the list. :-)
there is no other way (as it is implemented) to retrive the elements stored in the list. The variable is passed by reference so the user will get it back at the end.

+++++currentPtr->nextPtr = 0;++++++++++. If I remove this line what would happen? I know this sets the nextPtr to 0 in the last node of the list. Will this cause a printing problem?ie, print past the end of the list.

At this point the currentPtr->nextPtr points to the element that a few lines below, will be destroyed by delete opearot. so if you didn't detach it from the list, next time when you access the element pointed by currentPtr->nextPtr, it will point to a freed memory that do not belogs to any item in the list.
with the 0 assignment you indicate that there are no more elements in the list and the iteration thought the list elements should stop at that point.

If I swap these 2 lines of code, I haven't the foggiest.
~~~ cout << currentPtr->data << ' ';~~~
~~~currentPtr = currentPtr->nextPtr;~~~

Imagine at the moment that you are at the very first element in the list (e.g. currentPtr is equal to firstPtr). then you will ommit the contents of the first element jumping to the next and printing it's contents.
The second reason is when the currentPtr is equal to lastPtr. When this happen, currentPtr will become 0 (since the value of the lastPtr->nextPtr is always 0 indicating the end of list) the following line
cout << currentPtr->data <<' ';
will cause GPF tryng to access memory at addres 0 which is not allowed.

Hope this helps.

damyan