www.digitalmars.com         C & C++   DMDScript  

c++ - linked list ADT

reply "Andrew Edwards" <edwardsac spamfreeusa.com> writes:
Gentlemen,
I'm quite confused about the proper implementation for the following
classes. I've provide an implementation as I understand it, however my
understand is paltry at best. The intent is to create a linked list
implementation of the list ADT. Please guide me in the right direction.

template < class T >
class node
{
  private:
    node ( const T& something, node* nextPtr );
    T info;
    node* next;

  friend class list<T>;
};

template < class T >
class list
{
  public:
    list ( int i = 0 );
    ~list ();

  private:
    ListNode<T>* beginning;  // Pointer to beginning of list
    ListNode<T>* location;   // Location pointer
};

// implementation
template < class T >
node<T>::node ( const T& something, node* nextPtr )
{
  info = something;
  next = nextPtr;
}

template < class T >
list<T>::list(int i);
{
  beginning = new node<T>;
  location = NULL;
}

As always,
Thanks in advance,
Andrew
Jul 05 2003
next sibling parent reply Jan Knepper <jan smartsoft.us> writes:
Who not used STL?



Andrew Edwards wrote:

 Gentlemen,
 I'm quite confused about the proper implementation for the following
 classes. I've provide an implementation as I understand it, however my
 understand is paltry at best. The intent is to create a linked list
 implementation of the list ADT. Please guide me in the right direction.

 template < class T >
 class node
 {
   private:
     node ( const T& something, node* nextPtr );
     T info;
     node* next;

   friend class list<T>;
 };

 template < class T >
 class list
 {
   public:
     list ( int i = 0 );
     ~list ();

   private:
     ListNode<T>* beginning;  // Pointer to beginning of list
     ListNode<T>* location;   // Location pointer
 };

 // implementation
 template < class T >
 node<T>::node ( const T& something, node* nextPtr )
 {
   info = something;
   next = nextPtr;
 }

 template < class T >
 list<T>::list(int i);
 {
   beginning = new node<T>;
   location = NULL;
 }

 As always,
 Thanks in advance,
 Andrew
-- ManiaC++ Jan Knepper
Jul 05 2003
parent reply "Andrew Edwards" <edwardsac spamfreeusa.com> writes:
"Jan Knepper" <jan smartsoft.us> wrote...
 Who not used STL?
I'm assuming you are asking why I do not use STL. In short, I'm taking a C++ Data Structures class which requires that I implement my own. If I've made the wrong assumption about your question, please clarify! Andrew
Jul 05 2003
parent Jan Knepper <jan smartsoft.us> writes:
Andrew Edwards wrote:

 "Jan Knepper" <jan smartsoft.us> wrote...
 Who not used STL?
I'm assuming you are asking why I do not use STL. In short, I'm taking a C++ Data Structures class which requires that I implement my own. If I've made the wrong assumption about your question, please clarify!
No, that was the question... I often wonder why people implement existing code, it's kinda like re-inventing the wheel. Of course in your case the reason is obvious. -- ManiaC++ Jan Knepper
Jul 07 2003
prev sibling parent reply "Wichetael" <wichetael gmx.net> writes:
As yet you've only implemented a partial linked list implementation. You're
still lacking functions which would allow you to insert, add, remove, get,
find node's to/in/from the list. These functions are the most essential
functions as these will enforce the actual data structure. Also in the list
constructor you create a new node for beginning, I'm assuming you want that
to be a dummy node indicating the beginning of the list, in that case you'll
want to make it clear for yourself that that is a dummy node by setting it's
info to 0. You'll have a problem there though as info is a reference, which
can't be uninitialized, thus you can't really make a dummy node. So, you
have two options, one is to use a pointer instead of a reference in the
node, which you could set to 0 just as with the next pointer. Or you need to
forget about a dummy node and just do your accounting in the management
functions. But that will require some extra code in your list management
functions, most specifically, when adding nodes to you list, you first need
to check if it's empty (ie beginning is set to 0) in which case you need to
set beginning, in all other case you need to set one of the next pointers of
one of the nodes in the list.

All in all you still have quite a bit to do, I'd recommend you read over
your text books again and all the important parts, making a linked list
implementation isn't really difficult, you just need to get the right idea
of it first.

Regards,

Remko van der Vossen

"Andrew Edwards" <edwardsac spamfreeusa.com> wrote in message
news:be7aq9$2g2r$1 digitaldaemon.com...
 Gentlemen,
 I'm quite confused about the proper implementation for the following
 classes. I've provide an implementation as I understand it, however my
 understand is paltry at best. The intent is to create a linked list
 implementation of the list ADT. Please guide me in the right direction.

 template < class T >
 class node
 {
   private:
     node ( const T& something, node* nextPtr );
     T info;
     node* next;

   friend class list<T>;
 };

 template < class T >
 class list
 {
   public:
     list ( int i = 0 );
     ~list ();

   private:
     ListNode<T>* beginning;  // Pointer to beginning of list
     ListNode<T>* location;   // Location pointer
 };

 // implementation
 template < class T >
 node<T>::node ( const T& something, node* nextPtr )
 {
   info = something;
   next = nextPtr;
 }

 template < class T >
 list<T>::list(int i);
 {
   beginning = new node<T>;
   location = NULL;
 }

 As always,
 Thanks in advance,
 Andrew
Jul 06 2003
parent "Andrew Edwards" <edwardsac spamfreeusa.com> writes:
Thanks for taking the time to reply to this post.

I am aware of all the parts necessary to fully implement a linked list:
However, I did not provide enough information or explain myself clearly
enough.

Since I am doing my homework I did not want to put too much of my code
forward. I problem was understanding how to implement the constructor of the
two classes. Additionally, I wasn't able to visualize how to access members
of one class through the other.

You are quite right though! Implementing a linked list isn't really
difficult. Once I understood how to implement the constructors and how to
access the members of each class through one object that is!

As always, your assistance was greatly appreciated!

Regards,
Andrew
Jul 06 2003