Double linked list

[liquidfuzz]

I'm trying to set up a simple implementation of a double linked list... But I seem to some mistakes. If anyone could tell me what I'm doing wrong...

#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) );
	// Attatch to old vertex
	vrtx_current->next = vrtx_new;
	
	// Set up for new vertex
	vrtx_new->next = 0;
	vrtx_new->prior = vrtx_current;
	vrtx_new->id = data;
	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 = 0; i < 4; ++i){		// This vrtx_pntr is the prior for new vertex.
		*vrtx_pntr = add_vrtx(vrtx_pntr, i);										// the prior vertex.
	}

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

		}
	}

	return 0;
}

Edit, I get 'Test: root exists' printed out, but not the loop through my linked list.

[naraku9333]

You're not iterating through the list.

while( vrtx_pntr->next != 0 ){
		cout << "Test: Nodes exists.\n";
		cout << "Sweep: " << vrtx_pntr->id << "\n";
                vrtx_pntr = vrtx_pntr->next;
	}

[liquidfuzz]

Thanks for replying!

I see your point, but I still get the same result. I must have missed something else too. :-/

[kulkarnisr]

for(int i = 0; i < 4; ++i){		// This vrtx_pntr is the prior for new vertex.
		//*vrtx_pntr = add_vrtx(vrtx_pntr, i);	
		vrtx_pntr = add_vrtx(vrtx_pntr, i);							
    // the prior vertex.
	}

modify
vertex add_vrtx(vertex *vrtx_current, int data)
to return pointer

vertex* add_vrtx(vertex *vrtx_current, int data)

[Largins7]

Hello,

There is an article that you might want to look at. It constructs a linked list template that I think you will like. I haven't tried it, but you should be able to use it for vectors. The article is located at: http://www.cplusplus.com/articles/Lw6AC542/

Largins

[liquidfuzz]

I vent back to the drawing board. But then I stumbled upon other things I don't feel completely comfortable with.

I have aset of help functions. At the moment I need some help with the insert function:

#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;
	// How do I set the prev member of *head to new_vertex?  
	new_vertex->data = n;
	new_vertex->next = *head;
	*head = new_vertex;
}

On line 22 I need to set ->prev so that it points at new_vertex. How would I do that?

[naraku9333]

*head->prev = new_vertex;

[liquidfuzz]

Thanks! I tried that while I was setting it up. I get this message:

request for member 'prev' in '* head', which is of non-class type 'vertex*'

[naraku9333]

(*head)->prev = new_vertex;

[liquidfuzz]

Ok, thanks!

[liquidfuzz]

Now I'm having trouble deleting nodes in my lists. I don't know how to "reach" nodes to delete them. Here's a code snippet:

#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 * vertex, int n){
	vertex->data = -1;
	vertex->next = NULL;
	vertex->prev = NULL;
}

void insert_vertex(struct vertex ** vertex, int n) {
	struct vertex * new_vertex = (struct vertex *)malloc(sizeof(struct vertex));
//	vertex * new_vertex = new vertex;
	(* vertex)->prev = new_vertex;
	new_vertex->data = n;
	new_vertex->next = *vertex;
	*vertex = new_vertex;
}

/*
 * delete_this(&head); Maybe better actually..?
 * */
void delete_this(struct vertex * vertex){
	cout << "TEST";
	vertex->next->prev = vertex->next;
	vertex->prev->next = vertex->prev;
	delete(vertex);
//	kill(head);
}


void display(struct vertex * head) {
	cout << "List: " ;
	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 = (struct vertex *)malloc(sizeof(struct vertex));

	// create a null head node.
	init_vertex(head,-1);

	//Make a test list by inserting nodes
	for(int i=1; i<3; ++i){
		insert_vertex(&head,i);				// Works
	}


	display(head);

	while(head) {
		if(head->data > 0){
			cout << "\nIndex in array: " << head->data << "";
			// remove the current node from list NOT WORKING
			delete_this(head);
		}
		head = head->next;
	}
	return 0;
}

The program breaks down with a segmentation error in the delete loop. Deleting nodes in a double linked list, how is it done? Please feel free to point out issues.

[MikeyBoy]

If you're deleting the head, then what is the value of vertex->prev ? What will happen when you try to access vertex->prev->next ?