Thread: Problem with linked list

Hello,

I am currently writing a program that reads in an index of words and searches through a large text file for every instance of that word. I have the tokenize and input working correctly, but I am currently having problems getting my linked list which will consist of the pages it is on to work correctly. I think what its doing is only showing me the last node.
Here are my structures:

Code:

typedef struct stag 
{	
	int pgno ; //page numbers 
	struct stag *next ; //  pointer to next page No

}NODE;
  
typedef struct 
{ 
	string word; 
	NODE *link ;// pointer to linked list of pgno
}

Here is my portion of code for the linked list:

Code:

if(bin >= 0)//bin is the result of my binsearch
{
        p = new(NODE);
	p->next = NULL;
	p->pgno = pages;//pgno is page number
	index.awn[bin].link = p;
}

Any advice would be appreciated.

Thanks.

You need to add p to the list pointed to by link. I'm assuming link is meant to be the head of the list of nodes. You need to either walk down the list and add p to the point where you reach NULL, or point p->next to link and then make p the new value for link.

Alright, I will try that.

Thanks for the help, my list works now.

Just one last question, id like to make it so that it doesnt add duplicates to the linked list, but have ran into a roadblock. This is what I was trying:

Code:

if(index.awn[bin].link->pgno != p->next->pgno)
		p->pgno = pages;

If your list is sorted then you can check the item you are about the add against the last item in the list before adding it, otherwise you'll need to search the entire list before adding each item.

To not have a duplicate you have to search the whole list (a list is probably not the most efficient choice for this, but at this point I wouldn't worry about it until your code is working).

I would have a variable set to false for whether a match was found. Then I'd loop through the list and if I got to the end without finding a match, I'd add the node to the list, otherwise I'd delete the node and not add it to the list. A slightly better algorithm would be to keep the list in sorted order. If you did that, you would walk down the list until you reached the end or until you reached a node with a higher page number, and then insert the node there. That way you don't have to go through the whole list, plus it will be sorted for you when you output it later.

Thank you very much for your help. Ive got it all working now and am happy with the results.

Once again, I appreciate the help.