Need urgent help with this - linked list

[mo13]

Write a C++ program that implements a linked list as an abstract data type.
The program must:
 Be type flexible, that is, could be a list of integers, string, or any type.
 allow the user to add members into the list
 delete members from the list
 make sure the list is still sorted after all the deletion and addition
Show all the function implementation.

[keskiverto]

Please note that this is not a homework site. We won't do your homework for you. The purpose of homework is that you learn by doing. However we are always willing to help solve problems you encountered, correct mistakes you made in your code and answer your questions.

We didn't see your attempts to solve this problem yourself and so we cannot correct mistakes you didn't made and answer questions you didn't ask. To get help you should do something yourself and get real problems with something. If your problem is "I don't understand a thing", then you should go back to basics and study again.

[mo13]

i know how to do it using a normal linked list eg: just inserting one kind of data type but im not sure how to make it a abstract data type list

[mo13]

will i have to use a separate class file ?

[keskiverto]

Look at std::vector. Is it "type flexible"? If yes, how does it do it?

[mo13]

OK this is what i got so far:

#include <iostream>

using namespace std;

struct node
{
    string member;
    node *next;
};

bool isEmpty(node *head);
char menu();
void insertAsFirstElement(node *&head, node *&last, string member);
void insert(node *&head, node *&last, string name);
void remove(node *&head, node *&last);
void display(node *&current);

bool isEmpty(node *head){
if(head == NULL)
    return true;
else
    return false;
}
char menu(){
char choice;
cout << "MENU.\n";
cout << "1. Add\n";
cout << "2. remove\n";
cout << "3. display list\n";
cout << "4. Exit\n";
cin >> choice;
return choice;
}
void insertAsFirstElement(node *&head, node *&last, string member){
node *temp = new node;
temp-> member = member;
temp->next =NULL;
head = temp;
last = temp;

}
void insert(node *&head, node *&last, string member){
if(isEmpty(head))
    insertAsFirstElement(head , last , member);
else{
node *temp = new node;
temp-> member = member;
temp->next = NULL;
last->next = temp;
last=temp;
}
}
void remove(node *&head, node *&last){
if(isEmpty(head))
    cout << "The list is empty.\n";
else if (head == last){
    delete head;
    head==NULL;
    last==NULL;
    }
    else{
        node *temp=head;
        head = head->next;
        delete temp;
    }
}
void display(node *&current){
if(isEmpty(current))
    cout << "the list is empty.\n";
else{

     while(current != NULL)
     {
         cout << current ->member <<endl;
         current=current->next;
     }
     }
}

int main()
{
    node *head = NULL;
    node *last = NULL;
    char choice;
    string member;
    do{
        choice= menu();

        switch(choice){
        case '1' : cout <<"enter a member:";
        cin >> member;
        insert(head , last ,member);
        break;

        case '2': remove(head, last);
        break;
        case '3' : display(head);
        break;
        default : cout << "System exit\n";
        }
    }while(choice !='4');
    return 0;
}

[Thomas1965]

I think as an abstract data type it should use templates and should be a class.
A very rough first draft.

template <class T>
class LinkedList
{
public:
  void Add(T value)
  {}
  void Delete(T value)
  {}
  // all public stuff here
private:
  struct Node
  {
    T member;
    Node *next;
  };
  // all other private stuff here
};

// You can use it like this
  LinkedList<int> intList;

  intList.Add(10);

[linuxjca]

I think the STL is the best way to do this, it's template construction,
so you can change the type (int string, etc ...), have sort function,
you can add or delete items.

This is an example :

#include <iostream>
#include <list>

using namespace std;

int main(int argc, char** argv) {
    // Create a list of integer
    list<int> ListInt;
    // fill list in reverse order
    for(int i = 10; i>0; i--)
        ListInt.push_back(i*2);
    // display list content
    for (list<int>::iterator it = ListInt.begin(); it != ListInt.end(); it++)
        cout << *it << ' ';
    cout << endl;
    // sort the list
    ListInt.sort();
    // display list content
    for (list<int>::iterator it = ListInt.begin(); it != ListInt.end(); it++)
        cout << *it << ' ';
    
    return 0;
}

[dhayden]

make sure the list is still sorted after all the deletion and addition

Does this mean the list has to be maintained in sorted order? I think it does.

Read the assignment sentence by sentence and see if you can create a header file for what's needed. When you're done, read the assignment again to be sure you didn't miss anything. Repeat until you're sure that the code described in your header will solve the problem.

The program must:

Be type flexible, that is, could be a list of integers, string, or any type.

So you need a template like Thomas1965 said.

allow the user to add members into the list

And an Add() method. Hey, Thomas has that too!

delete members from the list

So you need a delete method. Damn! Thomas for President!

make sure the list is still sorted after all the deletion and addition

Ah, he missed this one:
bool Validate(); // returns true if the list is sorted.

[mo13]

thanks for the help guys:)

[jonnin]

make sure the list is still sorted after all the deletion and addition

I am unaware of anything linear (like lists) that lose sorting via a delete. 12345 remove 3 1245 is still sorted...

insert is where you must do something.