1,105,334 Community Members

Removing an item from head of linked list

Member Avatar
ml2662
Newbie Poster
2 posts since Aug 2004
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

I am having trouble with the following program. I am trying to create a linked list that behaves like a FIFO queue. I need to be able to add new items to the end of the queue and remove them from the front. My confusion is with trying to use the pointers to point to the right place. I am also having trouble getting the node_number to increment correctly.

#include <iostream>
using namespace std;

class QueueItem{
    private:
        char *item;
        int node_number;
        static int node_counter;
        QueueItem *next;

    public:
        QueueItem()
        {
            item=0;
            node_number=0;
            next=0;
        };

        QueueItem(char *input)
        {
          item=new char[strlen(input)+1];
          strcpy(item,input);
          next=0;
          node_counter++;
          node_number++;

        };

        void set_next(QueueItem *next_item)
        { 
          if(next!=0)
          { 
              QueueItem *t_ptr=next; 
              next=next_item; 
              next_item->next=t_ptr;

          }
          else 
          {
              next=next_item;

          }


        };

        QueueItem * get_next()
        {   
          return next;
        };

        int get_birth_number()
        {
            return node_counter;
        };

        int get_node()
        {
            return node_number;
        };


        void get_item()
        {
            cout<<node_number<<""<<item<<endl;

        };



};

int QueueItem::node_counter=0;


class Queue{
    private:
         QueueItem *head_ptr,*current;

    public:
        Queue()
        {
            head_ptr=new QueueItem;
        };

         void AddItem(char *str)
        {   
             QueueItem *iter=head_ptr;
             while (iter->get_next()!=0)
             {
                 iter=iter->get_next();
             }
             iter->set_next(new QueueItem(str));

         };

         void RemoveItem()
        {
             QueueItem *iter=head_ptr;
             delete iter;
             iter=iter->get_next;

        };

        void print()
        {
            QueueItem *iter=head_ptr;
            while (iter->get_next()!=0)
            {
                iter=iter->get_next();
                iter->get_item();
            }

        };

    /*  void Erase()
        {

            QueueItem *next_item,*temp_item;

            next_item=head_ptr;
            while(next_item !=0)
            {
                temp_item=head_ptr->next_item();
                item=next_info->get_item();
                delete item;
                delete next_item;

                next_item=temp_item;
            }
            head_ptr=0;

        };*/


};




void main()
{

    Queue names;

    names.AddItem ("Michele");
    names.AddItem ("Jimmy");
    names.AddItem ("Sarah");
    names.AddItem ("Joshua");

    names.print();

    names.RemoveItem();

    names.print();


}
Member Avatar
Chainsaw
Posting Pro in Training
434 posts since Jun 2004
Reputation Points: 12 [?]
Q&As Helped to Solve: 13 [?]
Skill Endorsements: 1 [?]
 
0
 

node_number is not initialized to anything, only ++'d in the constructor with the string. Maybe just say "node_number = node_counter"?

I'd also initialize node_counter where you declare it rather in the default constructor for the QueueItem.

RemoveItem() deletes the item and then refers to it! You should have another var holding the next item, like "pnext = item->getnext(); delete item; item = pnext;" Note that when you call getnext(), be sure and include the '()'! RemoveItem() also needs to update head_item. Maybe use that instead of item.

Erase() is ALL messed up; Maybe just call RemoveItem() over and over until the head is empty.

Member Avatar
ml2662
Newbie Poster
2 posts since Aug 2004
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

:cry:
Well that helped so now my node_number works and increments properly. But I am still stuck with the AddItem and RemoveItem functions. I think most of my problem is in the AddItem function because I can successfully remove an item from the list but is being removed from the wrong end. I think the AddItem function is assigning the head_ptr to the wrong end of the queue but I can't seem to fix it. The revised code is below.

#include <iostream>
using namespace std;



class QueueItem{
    private:
        char *item;
        int node_number;
        static int node_counter;
        QueueItem *next;

    public:
        QueueItem()
        {
            item=0;
        //  node_number=0;
            next=0;
        };

        QueueItem(char *input)
        {
          item=new char[strlen(input)+1];
          strcpy(item,input);
          next=0;
          node_counter++;
          node_number=node_counter;
        };

        QueueItem * get_next()
        { 
         // ++node_number;
          return next;
        };


        void set_next(QueueItem *next_item)
        { 
          if(next!=0)
          { 
              QueueItem *t_ptr=next; 
              next=next_item; 
              next_item->next=t_ptr;

          }
          else 
          {
              next=next_item;

          }

        };


        void get_item()
        {
            cout<<item<<endl;
        };

        int get_nodecount()
        {
            return node_counter;
        };

        void get_nodenum()
        {
            cout<< node_number;
        };



};

int QueueItem::node_counter=0;


class Queue{
    private:
         QueueItem *head_ptr,*current;


    public:
        Queue()
        {
            head_ptr=new QueueItem;
        };

         void AddItem(char *str)
        {   
             QueueItem *iter=head_ptr;
             while(iter->get_next()!=0)
             {
                 iter=iter->get_next();
             }
             iter->set_next(new QueueItem(str));


         };


     void RemoveItem()
        {
             QueueItem *head_ptr;
              head_ptr==current;
              delete head_ptr;


        };

        void print()
        {
            QueueItem *iter=head_ptr;
            while (iter->get_next()!=0)
            {
                iter=iter->get_next();
                iter->get_nodenum();
                iter->get_item();
            }

            cout<<"The number of items in the queue is:"<<iter->get_nodecount()<<endl;

        };

    /*  void Erase()
        {
            QueueItem *iter=head_ptr;
            while (iter->get_next()!=0)
            {
                iter=iter->get_next();
                iter->RemoveItem(); 
        };*/


};




void main()
{

    Queue names;

    names.AddItem ("Michele");
    names.AddItem ("Jimmy");
    names.AddItem ("Sarah");
    names.AddItem ("Joshua");

    names.print();

    names.RemoveItem();
//  names.RemoveItem();



    names.print();




}
Member Avatar
meabed
Junior Poster
139 posts since May 2004
Reputation Points: 37 [?]
Q&As Helped to Solve: 3 [?]
Skill Endorsements: 0 [?]
Team Colleague
 
0
 

Linked Lists

really i amnot ready to read all of these lines of code but i will try to give you good explanation about it . A linked list is an algorithm for storing a list of items. It is made of any number of pieces of memory (nodes) and each node contains whatever data you are storing along with a pointer (a link) to another node. By locating the node referenced by that pointer and then doing the same with the pointer in that new node and so on, you can traverse the entire list.
Because a linked list stores a list of items, it has some similarities to an array. But the two are implemented quite differently. An array is a single piece of memory while a linked list contains as many pieces of memory as there are items in the list. Obviously, if your links get messed up, you not only lose part of the list, but you will lose any reference to those items no longer included in the list (unless you store another pointer to those items somewhere).

Some advantages that a linked list has over an array are that you can quickly insert and delete items in a linked list. Inserting and deleting items in an array requires you to either make room for new items or fill the "hole" left by deleting an item. With a linked list, you simply rearrange those pointers that are affected by the change. Linked lists also allow you to have different-sized nodes in the list. Some disadvantages to linked lists include that they are quite difficult to sort. Also, you cannot immediately locate, say, the hundredth element in a linked list the way you can in an array. Instead, you must traverse the list until you've found the hundredth element.

A linked list like I've described above, where each item has a pointer to the next item in the list, is called a singly linked list. To implement this list, you would also want to store a pointer to the first item in the list (the head), which you would use to access the other items. However, some operations are awkward with a singly linked list. For example, to remove an item, you may need to traverse the entire list to locate the item that came before the item you are removing in order to modify its NEXT pointer. For this reason, many linked lists are implemented as a doubly linked list. In a doubly linked list, each item contains a pointer to both the next and the previous item in the list. Because you may want to traverse the list in reverse order, you would probably want to store the last item in the list (the tail) in addition to the first item.

The code below shows some key routines to implement a doubly linked list. The NODE structure represents each node in the list. It includes an int for storing information and a pointer to the next and previous nodes in the list. Obviously, you can modify the NODE structure to store other types of data and this code is ideally suited for conversion to a template that can be compiled to work with any other type of data. In addition, all the list-related routines are ideally suited to be implemented as a class. I kept the code as straight C here just to keep things as simple as possible and to fit the code into the space I had available. Perhaps you can modify it to meet your own needs.

#include 

struct NODE {
   NODE *pNext;
   NODE *pPrev;
   int nData;
};

NODE *pHead, *pTail;

// Appends a node to the end of the list
void AppendNode(NODE *pNode)
{
   if (pHead == NULL) {
      pHead = pNode;
      pNode->pPrev = NULL;
   }
   else {
      pTail->pNext = pNode;
      pNode->pPrev = pTail;
   }
   pTail = pNode;
   pNode->pNext = NULL;
}

// Inserts a node into the list after pAfter
void InsertNode(NODE *pNode, NODE *pAfter)
{
   pNode->pNext = pAfter->pNext;
   pNode->pPrev = pAfter;
   if (pAfter->pNext != NULL)
      pAfter->pNext->pPrev = pNode;
   else
      pTail = pNode;
   pAfter->pNext = pNode;
}

// Removes the specified node from the list
void RemoveNode(NODE *pNode)
{
   if (pNode->pPrev == NULL)
      pHead = pNode->pNext;
   else
      pNode->pPrev->pNext = pNode->pNext;
   if (pNode->pNext == NULL)
      pTail = pNode->pPrev;
   else
      pNode->pNext->pPrev = pNode->pPrev;
}

// Deletes the entire list
void DeleteAllNodes()
{
   while (pHead != NULL)
      RemoveNode(pHead);
}

void main()
{
   NODE *pNode;

   // Add items to linked list
   for (int i = 0; i < 100; i++) {
      pNode = new NODE;
      pNode->nData = i;
      AppendNode(pNode);
   }
   // Now display each item in list
   for (pNode = pHead; pNode != NULL; pNode = pNode->pNext) {
      printf("%d\n", pNode->nData);
   }
   //
   DeleteAllNodes();
}
Member Avatar
Chainsaw
Posting Pro in Training
434 posts since Jun 2004
Reputation Points: 12 [?]
Q&As Helped to Solve: 13 [?]
Skill Endorsements: 1 [?]
 
0
 

AddItem iterates through the list and when it ends up with a NULL it then dereferences that null pointer and adds the new entry to it. The other issue is that the head node doesn't get set if you are adding the FIRST entry to the list.

meabed describes a doubly-linked list, that may be more what you need. I tend to prefer a CIRCULAR list, that way you can add to the end without looking for the end (it is the head node's prior node), and many of the add/delete issues solve themselves because you don't have special case maintenance of the head node. (meabed's version does have some if stuff for the head node, it sorta depends on what you are after)...

So, the head node is "just a node" but doesn't have any data in it. To iterate you can say "node = head->next; while (node != head) {blah blah blah; node=node->next; }"

Here's a non-compiler-proven basis for a circular doubly linked list....

class ANode
{
public:

    ANode* pNext;
    ANode* pPrior;
    int        yourData;

    ANode()
    {
        yourData = 0;
        pNext = this;
        pPrior = this;    // initially, the node points to itself in both direction.  A circle of one!
    }
    virtual ~ANode()
    {
        Remove();  // on deletion, remove this node from the list it is on.
    }

    void Remove() // remove this node from whatever list its on, even if it isn't on a list!
    {
        pNext->pPrior = pPrior;  // next guy's prior is my prior
        pPrior->pNext = pNext; // prior guy's next is my next
        pNext = this;    // now I point to myself forward
        pPrior = this;    // and backwards
    }

    void AddMeBefore( ANode* her )  add 'this' before 'her' in her list
    {
        Remove();   // take me off any list I may be on
        pPrior = her->pPrior;  // my prior is her old prior
        her->pPrior = this;  // she now points back to me
        pPrior->pNext = this; // her old prior's next is now me
        pNext = her;  // my next is her
    }
};

class BlahBlah
{
. . . .

    ANode    head;

    void AddNodeToTheEndOfTheList( ANode* node )
    {
        node->AddMeBefore( &head );  // Adds node BEFORE the head node, which is the END of the list
    }

    void IterateList()
    {
        ANode* n = head.pNext;  // n is now either the head again or the first 'real' node.
        while (n != &head)
        {
            blah blah blah
            n = n->pNext;  // go to next node, maybe back to the head.
        }
    }
    void DeleteNodeFromList( ANode* n )
    {
        delete n;  // automatically deletes itself from the list, remember?
    }
    void DeleteEntireList()
    {
        ANode* n = head.pNext;
        while (n != &head)
        {
            ANode* next = n->pNext;
            delete n;
            n = next; // see how we saved this across the delete?
        }
    }
};

I hope this helps rather than just adds to the confusion....

Member Avatar
findsyntax
Newbie Poster
14 posts since Aug 2008
Reputation Points: -6 [?]
Q&As Helped to Solve: 2 [?]
Skill Endorsements: 0 [?]
 
0
 

Hi,
I am Rammohan from Bangalore and working as a Technical lead in big IT firm .
Solution for your answer is follows:

struct node *delet ( struct node *p, int node_no )
{
	struct node *prev, *curr ;
	int i;
	if (p == NULL )
	{
		printf("There is no node to be deleted \n");
	}
	else
	{
		if ( node_no > length (p))
		{
			printf("Error\n");
		}
		else
		{
			prev = NULL;
			curr = p;
			i = 1 ;
			while ( i < node_no )
			{
				prev = curr;
				curr = curr-> link;
				i = i+1;
			}
			if ( prev == NULL )
			{
				p = curr -> link;
				free ( curr );
			}
			else
			{
				prev -> link = curr -> link ;
				free ( curr );
			}
		}
	}
	return(p);
}

Regards,
Rammohan Alampally,
<snip false signature>

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article