Thread: Doubly Linked Lists

Well my guess would be something like this

Code:

// a node
typedef struct _node {
    int     data;
    struct _node *next;
    struct _node *prev;
} node;

// pointers to the end of the list
typedef struct {
    node    *head;
    node    *tail;
} LinkedList;

// lst is a pointer to the linked list (head/tail)
// target is what you're looking for
// node either points to the node (if found)
// or is NULL (if not found)
node* Search(LinkedList* lst, int target);

int main ( ) {
    LinkedList list;
    // blah to create the list
    node *found = Search( &list, 123 );
    return 0;
}

Linked lists are the greatest creation ever. These things absolutely rule, and they're SO simple to use.

1) Make an 'anchor' node, that will store either the first or last node in the list (or, if it's circular, just any given point).
2) Allocate some date.
3) Add it to the list,
4) goto 2:

Salem's idea of creating a structure to track both head and tail is an interesting one, but I've personally never used it. I generally just keep track of one. Though, I can see where if you were inserting in the list, you could find the value of the head and tail, grab the average, and decide if you need to go foreward or backwards to insert it correctly. Generally speaking this could save time.

Still, linked lists are incredibly easy to use. Double linked lists are infinitely easier than single linked lists when it goes for node removal.

Code:

void remove( int data, Node *list )
{
    Node *n;

    //single line of code to find your data
    //purposefully omitted. Yes, you can
    //answer your question in a single line
    //of code.

    //Now that our node is found, set it free!

    if( n->prev ) n->prev->next = n->next;
    if( n->next ) n->next->prev = n->prev;

    //Damn that's slick. It just doesn't get any
    //easier than that!

    free( n );

}

Quzah.

> Salem's idea of creating a structure to track both head and tail is an interesting one
I was trying to make it fit the apparent function prototype (which wasn't a node ptr)

>> Salem's idea of creating a structure to track both head and
>> tail is an interesting one
>
> I was trying to make it fit the apparent function prototype
> (which wasn't a node ptr)

Ah, gotcha. I often wonder, when reading these homework posts, why on earth you'd want to do some of these assignments. I mean, I know it's supposed to teach you the use of the language, but really, creating your own N based numbering system? *chuckle*

Quzah.