Thread: Linked lists - trying to revive...

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    110

    Linked lists - trying to revive...

    I'm trying to set up a simple implementation of a double linked list. I can't make it fly. Here's my code:
    Code:
    #include <iostream>
    #include <string.h>
    #include <stdlib.h>
    #include <stdio.h>
    
    using namespace std;
    #define ValueType int
    
    struct vertex {
        int id;
        struct vertex *prior;
        struct vertex *next;
    };
    
    /*
    
    void delete_vrtx(vertex vrtx_pntr){
        vrtx_pntr->piror->next = vrtx_pntr->next;        NOTE: FIND OUT IF SYNTAX WORKS
        vrtx_pntr->next->prior = vrtx_pntr->prior;
        return;
    }
    */
    /*
     * add_node()
     * params
     * vertex - use current to set prior
     * int    - data.
     **/
    vertex add_vrtx(vertex *prior_vrtx, int data){
        struct vertex *new_vrtx = (struct vertex *) malloc( sizeof( struct vertex) );
        new_vrtx->next = 0;
        new_vrtx->prior = prior_vrtx;
        new_vrtx->id = data;
        return *new_vrtx;
    }
    
    int main() {
        // set up a root.
        struct vertex *root = (struct vertex *) malloc( sizeof( struct vertex) );
        root->id    = 0;  // init all variables to zero.
        root->next  = 0;
        root->prior = 0;
    
        struct vertex *vrtx_pntr = root;            // pointer to first vertex.
    
        for(int i = 0; i < 3; ++i){                    // Trying to connect more nodes into my list.
            *vrtx_pntr = add_vrtx(vrtx_pntr, i);    // the prior vertex.
        }
    
        vrtx_pntr = root;
        if( vrtx_pntr != 0){
            cout << "Test: root exists.\n";
            while( vrtx_pntr->next != 0 ){
                cout << "Test: Nodes exists.\n";        // Won't print out this.
    
                cout << "Sweep: " << vrtx_pntr->id << "\n";
    
            }
        }
    
        return 0;
    }
    I seem to create a root vertex, but I can't establish if I connect sub nodes to my list. Please help me and bear in mind that I haven't really code stuff since I was a student...

  2. #2
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    The code doesn't set the next pointers. add_vrtx() needs to set prior_vrtx->next = *new_vrtx.

  3. #3
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Argh, and I missed that? Thanks for pointing it out!

  4. #4
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Still the same result... Here's the updated code:
    Code:
    #include <iostream>
    #include <string.h>
    #include <stdlib.h>
    #include <stdio.h>
    
    using namespace std;
    #define ValueType int
    
    struct vertex {
        int id;
        struct vertex *prior;
        struct vertex *next;
    };
    
    /*
    void del(vertex vrtx_pntr){
        vrtx_pntr->piror->next = vrtx_pntr->next;
        vrtx_pntr->next->prior = vrtx_pntr->prior;
        return;
    }
    */
    /*
     * add_node()
     * params
     * vertex - use current to set prior
     * int    - data.
     **/
    vertex add_vrtx(vertex *vrtx_current, int data){
        struct vertex *vrtx_new = (struct vertex *) malloc( sizeof( struct vertex) );
        // Setup for new vertex
        vrtx_new->next = 0;
        vrtx_new->prior = vrtx_current;
        vrtx_new->id = data;
        
        // Attatch to old vertex
        vrtx_current->next = vrtx_new;
        
        return *vrtx_new;
    }
    
    int main() {
        // set up a root.
        struct vertex *root = (struct vertex *) malloc( sizeof( struct vertex) );
        root->id    = 0;  // init all variables to zero.
        root->next  = 0;
        root->prior = 0;
    
        struct vertex *vrtx_pntr = root;            // list pointer to first vertex.
    
        for(int i = 1; i < 4; ++i){
            *vrtx_pntr = add_vrtx(vrtx_pntr, i);    // Link a new vertex to list.
        }
    
        vrtx_pntr = root;        // reset pointer to root..
        
    
        if( vrtx_pntr != 0){
            cout << "Test: root exists.\n";
            while( vrtx_pntr->next != 0 ){
                cout << "Test: Nodes exists.\n";
                cout << "Sweep: " << vrtx_pntr->id << "\n";
                        vrtx_pntr = vrtx_pntr->next;
            }
        }
    
        return 0;
    }
    Feel free to point out my mistakes.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Every time you do
    Code:
    *vrtx_pntr = add_vrtx(vrtx_pntr, i);
    you clobber the node that was in the root position. The new node is created, but you're not setting vrtx_pntr to point to it; you're overwriting the node vrtx_pntr points to (ie the root) with the contents of the new node. I don't really know why you're returning a vertex in the first place.

    Also, your add function will only work if the node passed in is the end of the list. If you want to insert into the middle, you should set vrtx_new->next to point to vrtx_current->next.

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Do you intend for this to be C or C++?
    You are using C++ with "cout", but your linked list is all C. Maybe you could clarify?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Quote Originally Posted by Elysia View Post
    Do you intend for this to be C or C++?
    You are using C++ with "cout", but your linked list is all C. Maybe you could clarify?
    Thanks for showing such interest in my code, or whatever you like to call it. ;-) First of all I use C/C++ for the good support of parallelizing libraries. I never really bothered my about the prints since they're solely used while I develop my code snippets. The C:ishness is out of habit, I guess.

  8. #8
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    I started all over again. The thing is, I have a code that works properly. It iterates through nodes, the nodes are stored in an array. In each iteration about 2/3s is handled and 'marked done' according to some premisses in the algorithm I run. I do this linked list stuff to see whether I can get speed up by skipping the iteration through nodes that already been handled in later iterations. Further, I try to implement a double linked list because I believe it's simpler to delete a currently handled node in a double linked list. (The data in a node is the index of an unmarked node.)

    An example of how the iterations might look.
    Iteration 1 - in a for-loop the nodes are inserted into the list and the nodes are handled simultaneously.
    node 1 - marked
    node 2 - unmarked, put in linked list
    node 3 - marked
    node 4 - marked
    node 5- unmarked, put in linked list
    node 6 - marked
    etc..

    Iteration 2 - Linked list is used to point out unmarked nodes sitting in the node-array.
    node 2 - marked
    node 5 - marked

    All nodes have been handled and everything is hunky dory.

    Now in my new attempt I get stuck on an other... thing.
    Code:
    #include <iostream>
    #include <string.h>
    #include <stdlib.h>
    
    using namespace std;
    #define ValueType int
    
    struct vertex {
        int data;
        vertex * next;
        vertex * prev;    
    };
    
    void init_vertex(struct vertex * head, int n){
        head->data = n;
        head->next = NULL;
        head->prev = NULL;
    }
    
    void insert_front(struct vertex ** head, int n) {
        vertex * new_vertex = new vertex;
        // * head->prev = new_vertex; //  Wont compile!!!  
        new_vertex->data = n;
        new_vertex->next = *head;
        *head = new_vertex;
    }
    I get errormessage: request for member 'prev' in '* head', which is of non-class type 'vertex*'. What am I doing wrong, whats the cure..?

  9. #9
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Ok I got that sorted. Now it turns out I'm having trouble deleting nodes in the list...

  10. #10
    Registered User
    Join Date
    Jun 2013
    Posts
    56
    Show us some code

  11. #11
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Quote Originally Posted by Ewiv View Post
    Show us some code
    Thanks for replying. Unfortunately I'm not on my own computer, waiting for a host to fix drinks, beers, snacks and ......... I'll write from memory...

    I tried to set it up like this:
    Code:
    delete(&node); // This is done in the loop iterating through the linked list.
    
    delete_vertex(struct vertex ** node ){
      (*node)->prev->next = (*node)->next;
      (*head)->next->prev = (*node)->prev;
    }
    At the moment I haven't got a clue to what's wrong. I'll get back to it next year. ;-)

  12. #12
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    It should be more like this:
    Code:
    delete_vertex(&node); // This is done in the loop iterating through the linked list.
    
     
    delete_vertex(struct vertex ** node ){
          (*node)->prev->next = (*node)->next;
          (*head)->next->prev = (*node)->prev;
    }

  13. #13
    Registered User
    Join Date
    Jun 2013
    Posts
    56
    You need a pointer to point to that node so you can delete it after changing the links.

  14. #14
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Hi again!

    Ok, this is a version of my code with all other junk deleted.
    Code:
    #include <iostream>
    #include <string.h>
    #include <stdlib.h>
    
    using namespace std;
    #define ValueType int
    
    struct vertex {
        int data;
        vertex * next;
        vertex * prev;
    };
    
    void init_vertex(struct vertex * head, int n){
        head->data = -1;
        head->next = NULL;
        head->prev = NULL;
    }
    
    void insert_front(struct vertex ** head, int n) {
        vertex * new_vertex = new vertex;
        (* head)->prev = new_vertex;
        new_vertex->data = n;
        new_vertex->next = *head;
        *head = new_vertex;
    }
    
    /*
     * delete_this(&head);
     * */
    void delete_this(struct vertex * node){
        node->next->prev = node->next;
        node->prev->next = node->prev;
    //    kill(head);
    }
    
    
    void display(struct vertex * head) {
        vertex * list = head;
        while(list) {
            cout << list->data << " ";
            list = list->next;
        }
        cout << "\nList end\n";
    }
    
    int main(){
        // Init a linked list for uncoloured vertices.
        struct vertex *newHead;
        struct vertex *head = new vertex;
        init_vertex(head,-1);
    
    
        for(int i=1; i<3; ++i){
            insert_front(&head,i);                // store for colouring.
        }
    
        cout << "Test: " ;
        display(head);
    
            while(head) {
                if(head->data > 0){
                    cout << "\nIndex in array: " << head->data << "";
                        // remove from list NOT WORKING
                        delete_this(head);
                }
                head = head->next;
            }
    
    
    }
    Please feel free to shout out if anything is gnarly.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Double Linked Dynamic Lists Vs Unrolled Linked Lists
    By lantzvillian in forum C Programming
    Replies: 6
    Last Post: 02-14-2012, 01:07 PM
  2. Replies: 4
    Last Post: 05-01-2010, 10:19 PM
  3. Question about Linked lists of lists
    By hear_no_evil in forum C Programming
    Replies: 2
    Last Post: 11-08-2004, 02:49 AM
  4. question on linked lists(stack with linked lists)
    By dionys in forum C Programming
    Replies: 1
    Last Post: 06-02-2004, 11:08 AM
  5. Revive a HD?
    By Dual-Catfish in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 05-13-2002, 08:25 AM