FAQ lists and searches (C)

could someone give me some pointers on lists. i understand the concept of them i just cant get the syntax down. i am also stuck on sequential searches. any advice would be appreciated. thanks.

[quzah]

A list. You kno what that is, right? Like a grocery list? It's a number of items "listed" one after the other. That's why it's called a "list".[/smart ass]

Here's a thought:

You tell us what you understand, we'll help with what you don't. A list entry (commonly called a "node") contains at a minimum, two things:

1) data
2) a pointer to the next node

To access the list, you need a place holder, or an anchor (same thing, different termonology):

struct mystruct *anchor;

This now is the placeholder for your node. This is what you add to, remove from, etc.

For example, this anchor can be envisioned as a table. Your list, consisting of nodes, is a stack of paper. Each piece of paper has some data, and a pointer to the next item in the list (in this case, the "pointer" is the fact that there's another sheet of paper under it).

Simple example. Very easy concept.

Quzah.

[ActionMan]

Hey,
well sequential searcher are slow.. but they are a simple concept.. heres some pseudo code:

while (not at end of list AND not found)
{

if (this node is what searching for)
found!!!
else
increment to next node
}

this is sorta what you would use for a linked list. Modifying it to any data structure isnt hard.

hope this helps,

[QuestionC]

Linked list searches are all about loops really.

Start with the first element.
Break if you're pointing at the element you need.
Repeat to the next element.

Usually the only error condition is if you reach the end of the list, which is taken care of easily enough by breaking if your pointer is NULL.

Assuming that list is a node * which points at the first element, and p is just a temporary node *, every search is gonna look something like this...

for (p = list; p != NULL; p = p -> next)
{
 if (p -> info == searchVal) break;
}

After this bit of code, p will either have escaped the loop because it reached the end of the list (p == NULL), in which case you know searchVal is not in the list, or it will have escaped the loop because p points at a node, the content of which is searchval (p -> info == searchVal). So, the contents of p are very useful.

p = p -> next
is the code that steps from one node to the next. With a normal linked list however, you must understand that whatever node you are pointing at, you don't have any way of accessing information for the previous node. This becomes an issue when inserting nodes, circumvented by the use of two node pointers, the use of a node pointer pointer, or code that looks like this...

if (p -> next -> info == searchVal)