Please help me get started with my linked list

Here's my problem, I'm not sure how to write this whole linked list:

The linked list should be relatively object-oriented, using two classes at least: one for list itself and one for each element of the list. Suggested names are List and ListElement.

Remember that each ListElement should have a pointer to the next ListElement(probably called next).

Remember also that you must find some way to end the list: either by having the last ListElement's next pointer point to null or itself.

The list should hold integers and support three basic operations: adding integers, removing integers, and finding integers.

Please remember that linked lists require the use of new, and that every use of new should have a corresponding use of delete.

Assuming your class is called list, you may use the following sample main:

Code:

int main()
{
     List list;
     
     cout << list.Count(9) << endl;  // should print 0
 
     list.Add(7);
     list.Add(12);

     if(list.Contains(12))
         cout << "found 12" << endl; // this should print
     else
         cout << "error" << endl; // shouldn't print

     if(!list.Contains(15))
         cout << "Did not find 15" << endl; // this should print
     else
         cout << "error" << endl;

     for(int x = 0; x < 10; x++)
         list.Add(x);
     cout << list.Count(7) << endl; // this should pring 2, since 
                                                     // there's (2) 7's in the list
     list.RemoveAll(7);
     cout << list.Count(7) << endl; // should print 0

     return 0;
}

A few questions, would I need to use some sort of array or vector to store the nodes.

how would I write the node, such as:

Code:

struct Node
{
     int x;
     Node *next;
}

class List
{
public:
     List() : head(NULL){}
     
     void Add(int y)
     {
         if(head == NULL)
     {
         head = new Node;
         head->x = y;
         head->next = (what would I put here- NULL, new Node?)
     }

     else 
         arrow->Add(x)


private:
     Node *head;
     List *Arrow;
};

and for the RemoveAll function, would I write:

[code]RemoveAll(int y)
{
if(Arrow != NULL)
delete Arrow;
}[code]

And for list.Count(int), would I need to use an array or vector to count the number of times that a number was inserted int list.Add, or is there some other better way to do this?

thanks

Not exactly what you want, but you should have no problem using it to get yourself going.

Code:

#include <iostream>

template <typename T>
struct node
{
  T data;
  node *next;

  node ( T d, node *n )
    : data ( d ), next ( n )
  {}
};

template <typename T>
class list
{
public:
  typedef node<T> *iterator;
public:
  list();
  ~list();
public:
  void insert ( T );
  void remove ( T );

  void walk ( std::ostream& );

  void clear();
private:
  iterator head;
};

template <typename T>
list<T>::list()
{
  head = new node<T> ( T(), 0 ); // Dummy node
}

template <typename T>
list<T>::~list()
{
  clear();
  delete head;
}

template <typename T>
void list<T>::insert ( T data )
{
  iterator it = head;

  while ( it->next != 0 && it->next->data < data )
    it = it->next;

  it->next = new node<T> ( data, it->next );
}

template <typename T>
void list<T>::remove ( T data )
{
  iterator it = head;

  while ( it->next != 0 && it->next->data < data )
    it = it->next;

  if ( it->next != 0 ) {
    iterator hold = it->next;

    it->next = hold->next;

    delete hold;
  }
}

template <typename T>
void list<T>::walk ( std::ostream& out )
{
  if ( head->next != 0 ) {
    iterator it = head->next;

    while ( it != 0 ) {
      out<< it->data <<"->";

      it = it->next;
    }
  }
}

template <typename T>
void list<T>::clear()
{
  iterator it = head->next;

  if ( it != 0 ) {
    for ( iterator next = it->next; it != 0; it = next ) {
      next = it->next;

      delete it;
    }
  }

  head->next = 0;
}

int main()
{
  list<int> l;

  // Try to clear an empty list
  l.clear();

  // Try to walk an empty list
  l.walk ( std::cout );

  // Insert and remove nodes to check that the logic is okay
  l.remove ( 1 );

  l.insert ( 1 );
  l.insert ( 5 );
  l.insert ( 2 );
  l.insert ( 7 );
  l.walk ( std::cout );
  std::cout<<std::endl;

  l.remove ( 1 );
  l.walk ( std::cout );
  std::cout<<std::endl;

  l.insert ( 3 );
  l.insert ( 9 );
  l.walk ( std::cout );
  std::cout<<std::endl;

  l.remove ( 9 );
  l.remove ( 2 );
  l.walk ( std::cout );
  std::cout<<std::endl;

  // Clear the list
  l.clear();

  // Try to walk a cleared list
  l.walk ( std::cout );

  std::cin.get();
  return 0;
}

-Prelude

You should consider the definition of a linked list. You don't need an array for the list, nor should you need to have an array of elements added (both of these make the list itself worthless).

Think about the structure of the linked list and how you traverse it and how you know when you've hit the end of it. It's helpful to make a drawing of what a linked list conceptually looks like. When writing the code, try doing the link changing on paper first to see how it works and ensure you don't end up letting a node float off into the sunset.