Linked list probs

**mouse163** · 02-19-2005

Hey all,
I'm including my telephone linked list code.
I am having major problems trying to insert (or add)
my new node in the appropriate alphabetical order.
I tried to overload the > op to compare
the first letters of the names -enterd last,first.
but i keep crashing when the print function calls.
(I know the menu can look better, I am just trying to get func-tionality down first).
I suspect what I am trying to do by inserting alphabetically
will also have something to do with my searchfor function?
any comment on that would be helpful.
thanks very much!
Michele

Code:

#include<iostream>
using namespace std;
 
 
#define MAX  40

struct TeleEntry
{
 
 char EntryName[40];
 char EntryNumber[40];
 bool TeleEntry::operator > (const char* &TeleEntryA) const
 {
     if (strcmp(this->EntryName, TeleEntryA) > 0)
     {return true;}
     else
     {return false;}
 }
 
 TeleEntry* Next;




};
 

class ListofTeles
{
 
public:

 ListofTeles();
 int count();
 TeleEntry* Head;
 

 int Add(TeleEntry* Item);
 TeleEntry *Retrieve(int pos);
 bool Delete();
 bool Delete(int pos);
 void Print();


private:
 
 int size;
};
 
 
 
 
 

//constructor__________________________________
 
ListofTeles::ListofTeles():size(0), Head(NULL)
{
}
 
//initialize count by size_____________________
 
int ListofTeles::count()
{
 return size;
}
 
//ADD_____________________________________________
 
int ListofTeles::Add(TeleEntry *NewItem)
{

 TeleEntry *Sample = new TeleEntry;
 Sample   = NewItem;

 if (Head==NULL)
 {
 Head  = Sample;
 }//if
 else
 {
     while((Sample->EntryName) > (Head->EntryName))
 {
             Head = Sample->Next;
     }//while

              Head  = Sample;
        
            
 }
 return size++;
}//add
 
//ITEM RETRIEVAL__________________________________
 
TeleEntry *ListofTeles::Retrieve(int Position)
{
 
 TeleEntry *Current = Head;
 for (int i=0; i<Position && Current !=NULL; i++)
 {
  Current=Current->Next;
 }
 
 return Current;
 

}
 
//ITEM DELETION______________________________________
 

bool ListofTeles::Delete()
{
 if (Head == NULL)
 {
  std::cout<<"The list is empty\n"<< endl;
  return false;
  
 }
 else
 {
  TeleEntry *Current;
  Current = Head->Next;
  Head->Next=Current->Next;
  size--;
  return true;
 }
  
}
 
//ITEM DELETION WITH ARGUEMENT__________________________
 
bool ListofTeles::Delete(int position)
{
 if (Retrieve(position) == NULL)
  return false;
 else
 {
  Retrieve(position -1)->Next = Retrieve (position +1);
  size--;
  return true;
 }
  
}
//PRINT LIST
void ListofTeles::Print()
{

 cout << "Print Telephone List" << endl;
 
 if (Head == NULL)
 {
  std::cout<<"The list is empty\n"<< endl;
 }
else
{
TeleEntry *Current;

Current = Head;

while (Head!=NULL)
{

  cout<<"\nName:     "<<Current->EntryName << "  " <<"Tele #:   "<< Current->EntryNumber << endl;;

  Current = Current->Next;
  Head = Current;

        }//while
    }//else
}//Print
 
//___________________________________________________
 
int main()
{
 
 ListofTeles *Teles= new ListofTeles();
 
 TeleEntry     *Tele;

 char Name [MAX];
 char Number[MAX];
 bool b;

 cout << "would you like to enter a name/number?"<< endl;
 cout << "enter 1 for yes 0 for no" << endl;
 cin >> b;
 

 while(b==1){
cout << "Enter Name (Last,First) :"<< endl;
cin >> Name;
cout << "Enter Number :"<< endl;
cin >> Number;

 Tele = new TeleEntry;
 strcpy (Tele->EntryNumber, Number);
 strcpy (Tele->EntryName, Name);
 
 Teles->Add(Tele);

 cout << "would you like to enter a name/number?"<< endl;
 cout << "enter 1 for yes 0 for no" << endl;
 cin >> b;

 }

 
cout<<"Qty Telephone Numbers: " << Teles->count() << endl;


Teles->Print();
 
 



 
 


return 0;
 
}

**andyhunter** · 02-19-2005

but i keep crashing when the print function calls.

void ListofTeles::Print()
{

cout << "Print Telephone List" << endl;

if (Head == NULL)
{
std::cout<<"The list is empty\n"<< endl;
}
else
{
TeleEntry *Current;

Current = Head;

while (Head!=NULL)
{

cout<<"\nName: "<<Current->EntryName << " " <<"Tele #: "<< Current->EntryNumber << endl;;

Current = Current->Next;
Head = Current;

}//while
}//else
}//Print

I believe this should be:

Code:

while (Current!=NULL)

**mouse163** · 02-19-2005

Thanks,
I don't think that's the problem-I believe the problem is in my Add function.
If i added straight to the back print() worked fine.
but thanks

**andyhunter** · 02-19-2005

Wow, I didn't even see this:

Code:

Head = Current;

Why do you keep moving the head of your list?

You do it in your add function here:

Code:

    while((Sample->EntryName) > (Head->EntryName))
 {
             Head = Sample->Next;
     }//while

              Head  = Sample;
        
            
 }

The head of your list always points to the element added in your list, not the first element.

Maybe you should take a look at this tutorial or reread the section on linked lists in whatever book you have.

**andyhunter** · 02-19-2005

Now this is in C, but it should help you see what is going on.

A linked list is simply a group of structures (containers to be exact, you can have a series of class objects) that have at least one member that is a pointer to the next object in the list. Now this isn’t as complicated as it may sound, lets take a look at it piece by piece.

1. A linked list is a group of structures; thus one element in the linked list(often referred to as a node) would be a structure. So an example of this node would be similar to:

Code:

struct myNode {
    char name[10];
    char phoneNumber[13];
};

2. These nodes must contain at least one member that is a pointer to the next structure. Now we say at least one member because often it is more convenient to have 2 pointers; one pointing to the next node and one pointing to the previous node. So we know we need a pointer that is of type of our structure, thus something like this:

Code:

struct myNode* nextNode;

So putting this together we get the definition of our node:

Code:

struct myNode {
    char name[10];
    char phoneNumber[12];
    struct myNode* nextNode;
};

Now that we understand the concept of what a node is lets move onto the implementation of the linked list. As stated previously a linked list is a group or chain of nodes. As with all chains we need to define an anchor or starting point. This starting point is simply a pointer that is of type of our structure. So our implementation of this anchor would be like:

Code:

struct myNode* firstNode;

You define the end of a linked list by having the last node’s next pointer set to NULL. Now in the beginning of our program to signify an initially empty list we will set firstNode to NULL. Thus you will usually see something along the lines of:

Code:

firstNode = NULL;

Alright the remaining concept to grasp the fundamentals of linked lists lies in successfully adding and removing nodes from our list. These topics revolve around dynamic memory allocation, using malloc() and free().This topic is as easy to understand as the previous topics however it seems to be the hardest for new programmers to grasp so we’ll spend some time here. The prototype for malloc() is:

Code:

void* malloc(size_t size);

All malloc() does is allocate size bytes and returns a pointer of type void to that memory, or NULL if an error occured. So you are probably asking, well that’s great but how do I use it? Well the standard convention for using malloc is:

Code:

pointer = malloc(n * sizeof(*pointer));

where n is the number of elements you need and *pointer (the dereferenced pointer) is used to determine the size of the individual element. So if I wanted to create 1 new node (our node we have been using) I would do it like so:

Code:

//allocate space for our node
newNode = malloc(1 * sizeof(*newNode));
//check for error
if(newNode == NULL){
     printf("Error allocating memory");
     return;
}

*Note, the ISO standard dictates there is no need to cast the return from malloc(), however some compilers may complain about being unable to convert the types. If this happens you can still use malloc, simply cast the return*

Now that we understand how to allocate the memory, lets take a look at how we add the node to our list. Remember that we signify the end of our list by having the last node’s next node pointer be NULL. Thus to add a new node we simply “walk through” our linked list until we find the last node. Once we are there we set the last node’s next node pointer to our newly created node. Thus the implementation would look like:

Code:

//first check if the linked list is empty
//if it is make the new node the first node
if(firstNode == NULL) {
     firstNode = newNode;
     return;
}
//if not find the last node
walker = firstNode;
while(walker->nextNode != NULL){
     walker = walker->nextNode;
}
//set last node's next node to our new node
walker->nextNode = newNode;

To delete a node is just as easy as adding a node but before we dive into that lets take a look at how we free the memory we allocated with malloc(). The function is conveniently called free() and its prototype is:

Code:

void free(void* mem);

where mem is a pointer to the block of memory allocated dynamically. Note that there is no return value and free does not ask for nor want a size to free. It simply releases the amount of memory pointed to by mem. Pretty easy, right?

So now you are probably asking, well that’s great but how do I delete my node from the list? Remember that these lists are chained together simply by the pointers that each element has. So to remove an element from the list all you need to do is:
1. Find the node to delete and the previous node
2. Make the previous node’s next node pointer point to the node following the node to delete (aka set the previous node’s next node member equal to the node to delete’s next node member).
3. free the memory allocated for the node to delete.

So lets look at this 1 step at a time:
1. Find the node to delete and the previous node

Code:

//if deleting the first node
if(nodeNumber == 1){
     nodeToDelete = firstNode;
     firstNode = firstNode->nextNode;
}else{
     //start at the begginning
     nodeToDelete = firstNode;
     prevNode = NULL;
     //find the previous node and node to delete
     for(int i = 0; i < nodeNumber - 1; i++){
          prevNode = nodeToDelete;
          nodeToDelete = nodeToDelete->nextNode;
     }

2. Make the previous node’s next node pointer point to the node

Code:

prevNode->nextNode = nodeToDelete->nextNode;

3. free the memory allocated for the node to delete.

Code:

free(nodeToDelete);

And that is all there is to removing a node from a linked list and about all the basics for a linked list. Normally you would sort your linked list but that is a matter for another lesson, or the interested individual to figure out. Hopefully this will help you hit the ground running. Attached below is a full sample program that displays the principles explained above. Additionally I have included another prog that does this whole phone list thing. Again this is in C so I am not giving you the answer, just trying to point you in the right direction.

**mouse163** · 02-19-2005

thank you so much for taking the time to go thru all that for me-
I am going to punch through your tips and the tutorial
(believe me i have done a few!)

I'm very grateful for your time-
Michele

Thread: Linked list probs

Thread Tools

Search Thread

Display

Linked list probs

Understanding Linked Lists

Similar Threads

C++ Linked list program need help !!!

seg fault for linked list in another linked list--help!!

Reverse function for linked list

Template Class for Linked List

singly linked list