c++ - linked list ADT
- Andrew Edwards (40/40) Jul 05 2003 Gentlemen,
- Jan Knepper (5/45) Jul 05 2003 --
- Andrew Edwards (5/6) Jul 05 2003 I'm assuming you are asking why I do not use STL. In short, I'm taking a...
- Jan Knepper (7/12) Jul 07 2003 No, that was the question...
- Wichetael (25/65) Jul 06 2003 As yet you've only implemented a partial linked list implementation. You...
- Andrew Edwards (14/14) Jul 06 2003 Thanks for taking the time to reply to this post.
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
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
"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
Jan Knepper <jan smartsoft.us> Andrew Edwards wrote:"Jan Knepper" <jan smartsoft.us> wrote...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 KnepperWho 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!
Jul 07 2003
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
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