开发者

What is the problem with my LinkedList class?

class LinkedList
{
  private:
    int data;  
    LinkedList *ptr;  
public:
  LinkedList(int i_data)  
  开发者_JAVA百科{ 
    data = i_data;  
    ptr = 0;  
  }  
  ~LinkedList()  
  {  
    delete ptr ;  
  }  
  void insert(LinkedList *node)  
  {  
    while(this->ptr!= 0)  
    this = this->ptr;  

    this->ptr= node;  
  }  
}

I will be creating a head node like head = new LinkedList(4) and then will be calling like head->insert(new LinkedList(5)) and subsequently . Can you please tell me does above class represent a linkedlist . i think yes it has node which contain address of next node . Please correct me if i am wrong


Yes this type certainly represents a singularly linked list structure as it has a data slot and a next pointer.

One thing I would change though is the insert method. IMHO, it's more convenient for this method to take the data type, in this case int, and let the LinkedList class take on the work of allocating the data structure.

For example.

void insert(int data) {
    while(this->next != 0)  
    this = this->next;  

    this->next = new LinkedListNode(data);  
}


You have point the last node's next to NULL as well

void insert(LinkedList *node)
{
while(this->next != 0)
this = this->next;

this->next = node; 
node->next = 0;

}


If you need a linked list use the STL version of it. It is already implemented and tested, and in most cases most people won't manage to implement anything better than that.

From the code point of view, you cannot assign to this, so the insert method will not compile --consider using tail recursion here. At a lightly higher level, you should prefer initialization lists to assignment in the body of constructors. You can consider using smart pointers to alleviate the need to manually manage memory, even if in this simple case it would not be a problem.

You should always think first on the interface and then on how you can provide an implementation for it. In particular the simplest interface you may want would be:

class List {
public:
  List();                   // creates an empty list

  void append( int value ); // adds a new element at the tail of the list
     // push_front( value ) in STL sequence containers

  void insert( int value ); // inserts a new element before the head of the list
     // push_back( value ) in STL sequence containers

  // some way of iterating (I like STL iterators,
  // but Java style iterator --even if worse-- could suffice)
};

In fact I would like more things in the interface, but the set above is a minimal approach (where the destructor is not included, but of course I want the resources to be managed by the implementation!). Now, with your definition of LinkedList (which is in fact closer to the definition of a node) you cannot create empty lists. You can append at the end of the list, but you cannot insert before the first element of the list. You did not offer a facility to extract data from the list (!!)

If you take a couple of minutes to think on the extra features you may want from a linked list (removal of a given element through an iterator so you can search for value X and remove it from the list, insertion at a given position in the list, not just head or tail...) you will come up with other requirements in the interface, and then you only need to fulfill those requirements in code, which is always much simpler :)


  1. Your class is not closed. Add a }; at the very end.
  2. The brace that is supposed to be closing the constructor is an opening one.
  3. This is a linked list alright, but it's simpler to use a separate node and list classes since in your case memory management falls completely to the user, making usage of this class a pain.


Where is member 'next' defined?

Your insert() uses 'this->next', but there are only members 'data' and 'ptr'.


My problem is that you have not deferentiated the list from the nodes of the list.
This causes the problem that you can not have an empty list without having a NULL pointer:

I will be creating a head node like head = new LinkedList(4)

  • So I would have a linked list class (that does not need to be dynamically allocated)
  • I would have a node class (internal) that holds data and pointer to next
  • I would update the interface to take the data object (like Jared Par described).

Code:

class LinkedList
{
    struct Node
    {
         Node(int d): data(d) {next = NULL;}
        ~Node()               {delete next;}
        int                   data;
        Node*                 next;
    };

    std::auto_ptr<Node>   head;

    Insert(int data)
    {
        if (head.get() == NULL)
        {
            head.reset(new Node(data));
        }
        else
        {
            Node* loop;
            for(loop = head.get();loop->next != NULL;loop = loop->next) {};
            loop->next = new Node(data);
        }
    }
};

LinkedList   list;
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜