Please help me get started with my linked list

This is a discussion on Please help me get started with my linked list within the C++ Programming forums, part of the General Programming Boards category; Here's my problem, I'm not sure how to write this whole linked list: The linked list should be relatively object-oriented, ...

  1. #1
    LinkedListQues
    Guest

    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

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    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
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Jan 2003
    Posts
    42
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 08:53 PM
  2. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 11:03 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 11:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21