Is this a proper DEQUE push function?

[xavier666]

I was making a DEQUE program utilizing two separate lists for forward and backward traversal. But what I think I've done is ended up making two separate lists, having same data but only their order reversed, thus wasting memory :'(.
So what I want to know is this how a DEQUE push function is done(push as in pushing from top as in pushing in stack)? If I'm wrong, just tell me where to change the code :confused:

typedef struct list
{
	int data;
	struct list *forward;
	struct list *backward;
}node;

void push_top( node *head, node *tail, int n )
{
	node *temp1;    // CONTROL VARIABLE FOR ALL FORWARD TRAVERSAL RELATED TASK
	node *temp2;    // CONTROL VARIABLE FOR ALL BACKWARD TRAVERSAL RELATED TASK
	node *temp3;    // STORES NEWLY GENERATED ADDRESS FOR FORWARD LIST
	node *temp4;    // STORES NEWLY GENERATED ADDRESS FOR BACKWARD LIST	

	temp1 = head;
	temp2 = tail;

	if(temp1 == NULL)   // EMPTY LIST
	{
		// 1ST TIME CREATING HEAD
		temp3 = (node *)malloc(sizeof(node));
		temp3 -> data = n;
		temp3 -> forward = NULL;
		head = temp3;

        // 1ST TIME CREATING TAIL
		temp4 = (node *)malloc(sizeof(node));
		temp4 -> data = n;
		temp4 -> backward = NULL;
		tail = temp4;
	}
	else
	{
        // ADDING NEW ELEMENT & MAKING IT THE NEW HEAD
        temp3 = (node *)malloc(sizeof(node));
        temp3 -> data = n;
        temp3 -> forward = head;
        head = temp3;

		// GOING TO 2ND LAST ELEMENT OF BACKWARD LIST
        while(temp2 -> backward != NULL)
            temp2 = temp2 -> backward;

        // ADDING NEW ELEMENT & MAKING IT POINT TO NULL
        temp4 = (node *)malloc(sizeof(node));
        temp4 -> data = n;
        temp4 -> backward = NULL;

		// POINTING THE 2ND LAST ELEMENT TO THE NEW LAST ELEMENT
        temp2 -> backward = temp4;
	}
}

[Salem]

http://www.sgi.com/tech/stl/Deque.html
You need two "push" functions, one for each end of the deque.

> temp3 = (node *)malloc(sizeof(node));
Why are you casting the result of malloc - there is no need to do so in a correct C program.
http://faq.cprogramming.com/cgi-bin/smartfaq.cgi?answer=1047673478&id=1043284351

[xavier666]

You need two "push" functions, one for each end of the deque.

I did that but i didn't show it. All the DEQUE functions follow this similar type of logic. I thought if this was OK, the rest of the functions should be fine

Why are you casting the result of malloc - there is no need to do so in a correct C program.

Point noted, i guess my book is a bit outdated. It specifically says to type-cast malloc 'coz of null pointer

I'll assume that logically the function is correct. Waiting for your confirmation ...

[Salem]

I can't tell anything without seeing both push functions.

The one you posted seems bloated to me to begin with.

If you had a separate deque struct containing the head and tail, then it would be a lot simpler for both functions.

[xavier666]

Okay, got it. Now it seem that i made a mistake. I accidentally gave the wrong snippet. That one was experimental and not fully functioning as both the head and tails need to be returned. This snippet is fully functioning but i made the head and tail variables global. But I guess that's where the 2nd structure containing the head and tail comes.
But i'm absolutely clueless about how to return both of them using structure.
Here are both the push functions

typedef struct list
{
	int data;
	struct list *forward;
	struct list *backward;
}node;

node *head;     // STORES ADRESS OF STARTING ELEMENT
node *tail;     // STORES ADRESS OF ENDING ELEMENT
node *temp1;    // CONTROL VARIABLE FOR ALL FORWARD TRAVERSAL RELATED TASK
node *temp2;    // CONTROL VARIABLE FOR ALL BACKWARD TRAVERSAL RELATED TASK
node *temp3;    // STORES NEWLY GENERATED ADDRESS FOR FORWARD LIST
node *temp4;    // STORES NEWLY GENERATED ADDRESS FOR BACKWARD LIST

void push_top( int n )
{
	temp1 = head;
	temp2 = tail;
	
    temp3 = malloc(sizeof(node));
    temp3 -> data = n;
    temp4 = malloc(sizeof(node));
    temp4 -> data = n;

	if(temp1 == NULL)   // EMPTY LIST
	{
		// 1ST TIME CREATING HEAD
		temp3 -> forward = NULL;
		head = temp3;

        // 1ST TIME CREATING TAIL
		temp4 -> backward = NULL;
		tail = temp4;
	}
	else
	{
        // ADDING NEW ELEMENT & MAKING IT THE NEW HEAD
        temp3 -> forward = head;
        head = temp3;

		// GOING TO LAST ELEMENT OF BACKWARD LIST
        while(temp2 -> backward != NULL)
            temp2 = temp2 -> backward;

        // ADDING NEW ELEMENT & MAKING IT POINT TO NULL
        temp4 -> backward = NULL;

		// POINTING THE LAST ELEMENT TO THE NEW LAST ELEMENT
        temp2 -> backward = temp4;
	}
}

void push_end( int n )
{
	temp1 = head;
	temp2 = tail;
	
    temp3 = malloc(sizeof(node));
    temp3 -> data = n;
    temp4 = malloc(sizeof(node));
    temp4 -> data = n;

	if(temp2 == NULL)   // EMPTY LIST
	{
		// 1ST TIME CREATING TAIL
		temp4 -> backward = NULL;
		tail = temp4;

        // 1ST TIME CREATING HEAD
		temp3 -> forward = NULL;
		head = temp3;
	}
	else
	{
        // ADDING NEW ELEMENT & MAKING IT TAIL
        temp4 -> backward = tail;
        tail = temp4;

        // GOING TO LAST ELEMENT OF FORWARD LIST
		while(temp1 -> forward != NULL)
            temp1 = temp1 -> forward;

        // ADDING NEW ELEMENT & MAKING IT POINT TO NULL
        temp3 -> forward = NULL;

        // POINTING THE LAST ELEMENT TO THE NEW LAST ELEMENT
        temp1 -> forward = temp3;
	}
}

[xavier666]

> temp3 = (node *)malloc(sizeof(node));
Why are you casting the result of malloc - there is no need to do so in a correct C program.

Now this is becoming weird. After I removed type casting, I'm getting an error. Here's the premise:

Editor   - Code::Blocks 8.02
Compiler - GNU GCC Compiler

And here's what I did:

• When I removed (node *) from temp3 = (node *)malloc(sizeof(node));
• The error that I got is

  error: invalid conversion from `void*' to `node*'

• I became desperate and made it temp3 = (node *)malloc(sizeof(*node)); according to the link you gave me but still it yielded no results. So i'm back where I started.

Is it possible my compiler is non ISO C standard?

[Narue]

>Is it possible my compiler is non ISO C standard?
Seeing as how you're compiling as C++ rather than C, I'd say that's a fair assumption.

[Salem]

1. Create a separate struct for the deque itself.
2. Remove all those global temps - eww!!!
3. Separate the 'create a node' from the 'add it to the deque' functionality. Two simpler functions are much easier to deal with than some do-it-all bloater.

The essence of all this should be something like

struct deque {
  struct node *head;
  struct node *tail;
};

void push_front ( struct deque *q, struct node *n ) {
  if ( q->head == NULL ) {
    q->head = n;
    q->tail = n;
  } else {
    n->next = q->head;
    q->head = n;
  }
}

void push_back ( struct deque *q, struct node *n ) {
  if ( q->head == NULL ) {
    q->head = n;
    q->tail = n;
  } else {
    q->tail->next = n;
    q->tail = n;
  }
}

[xavier666]

>Is it possible my compiler is non ISO C standard?
Seeing as how you're compiling as C++ rather than C, I'd say that's a fair assumption.

How am I doing that (sounds silly, I know)? I mean the extension is .c but compiling as C++. My compiler automatically detects my code to be C code so I thought the compilation would be proper. Please explain where I'm going wrong.
I also saw that there is a list of compilers inside Code::Blocks from where we could choose a compiler of our liking.By default it was set to GCC compiler so i decided to stick with it.

Thanks Salem! when it works, I'll mark this thread as solved

[Narue]

>Please explain where I'm going wrong.
I don't know, but I do know that error, and it only comes from a C++ compiler to the best of my knowledge. C allows implicit conversion to and from void*, but C++ only allows implicit conversion to void*. Perhaps there's a switch that explicitly forces the C++ compiler regardless of file extensions.