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...

The code doesn't set the next pointers. add_vrtx() needs to set prior_vrtx->next = *new_vrtx.

Argh, and I missed that? Thanks for pointing it out!

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.

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.

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 Elysia

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.

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..?

Ok I got that sorted. Now it turns out I'm having trouble deleting nodes in the list...

Show us some code :)

Quote:

---

Originally Posted by Ewiv

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. ;-)

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;
}

---

You need a pointer to point to that node so you can delete it after changing the links.

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.