Doubly Linked Lists

This is a discussion on Doubly Linked Lists within the C Programming forums, part of the General Programming Boards category; I'm trying to write a programme using doubly linked lists for a list of nodes with specified data.. I think ...

  1. #1
    Registered User
    Join Date
    Nov 2001
    Posts
    4

    Unhappy Doubly Linked Lists

    I'm trying to write a programme using doubly linked lists for a list of nodes with specified data.. I think I can do that bit, problem is, how do I write a function to Search this list, try and find specified data and print if found? Have node* Search(LinkedList* lst, int target); , but not sure how to use it.

    From a very confused IT student...

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    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;
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    > 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)
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    >> 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.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    Nov 2001
    Posts
    4

    Smile Re:Doubly Linked Lists

    Thanks for all yer help - it was much needed! Look forward to getting more help from ye in the future,

    Thanks again..

  7. #7
    Sayeh
    Guest
    The reason such assignments are given is because the are hoping that atleast -some- of the students are able to grasp the concept from the example--

    The problem actually lies not with the students, but with the instructor or even the institution-- they barely understand the stuff themselves, and truthfully it is very hard to teach someone programming if you don't teach them the true basics.

    Programming Fundamentals 101 should not start out teach 'loops', 'whiles', and 'functions' ,etc. It should start out with assembly language. Give people the overall concept, and then show them the fundamentals of how their language executes on the processor-- with EXAMPLES.

    Contrary to most institutions, assembly language is NOT an advanced topic-- it's where people should be beginning.

    Here is an analogy-- if I taught you English, but never taught you what letters were, or how they go together or how they are broken into vowels and consonants, you would be relegated to learning a language by wrote, and association-- not by conceptual understanding.

    Hence, the _majority_ of you out there trying to learn C/C++ are forced to learn with know understanding. And because of that, every developer has to start at square one, without the benefit of "experienced" people provided a structure set of lessons and answers the culminates in programming using a higher level language.

    This is the flaw of education today (great GOD, it's been going downhill since 1978.... Institutional Morons with little letters after their names...)

    Stepping down from soapbox...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Doubly linked lists
    By mohanlon in forum C Programming
    Replies: 8
    Last Post: 12-08-2010, 12:01 AM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  4. doubly linked lists
    By cworld in forum C++ Programming
    Replies: 2
    Last Post: 04-21-2002, 09:33 AM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21