Thread: FAQ lists and searches (C)

  1. #1
    Unregistered
    Guest

    lists and searches

    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.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    23

    Searches

    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,
    ActionMan

    "THE DAY IS MYNE!!!!
    I'll take famouse titties for $400"
    -Sean Connery, Saturday Night Live

  4. #4
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    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...
    Code:
    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...
    Code:
    if (p -> next -> info == searchVal)
    Last edited by QuestionC; 10-31-2001 at 08:08 PM.
    Callou collei we'll code the way
    Of prime numbers and pings!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. Singly-linked lists and memory loss (valgrind report)
    By Nazgulled in forum C Programming
    Replies: 5
    Last Post: 03-11-2008, 06:45 AM
  3. Linked Lists in C++
    By cworld in forum C++ Programming
    Replies: 2
    Last Post: 04-16-2002, 07:28 PM
  4. lists and searches
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 10-31-2001, 08:04 PM