470,647 Members | 1,428 Online

# Amazon Interview Question on Doubly Linked List, Plz help

Hi Coders,

I was asked to write a program to interchange numbers using doubly

Here is the details with Code that i wrote.

i/p: 1 2 3 4 5 6 7 8 .....n,n-1.
o/p: 2 1 4 3 6 5 8 7.....n,n-1.

I wanted this code to make as small and it should be algorithmically
fit. The following is just plain without any logic. plz help me to
solve this algorithmically i.e big oh etc. and it should run fast for
millions of numbers.

Thanks a lot.

Code:
--------------------------------------------------------------------------------------------
#define TravelNode 8
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

/*
* Doubly linked Node with Data
*/

struct node {

int data;
struct node *prev;
struct node *next;
};

typedef struct node NODE;

int main(void) {

*tail,
*temp;

int i=1;

/*
* Memory Allocation for head node
*/

/*
* Save First Node
*/

/*
* Fill data in very first node
*/

printf("\n Begin.... \n");

/*
* Fill Data in the Nodes
*/

while(i < TravelNode ){

}

First Node Now.
tail = head->next; // tail pointing to
Second Node.

/*
* First Two Node Exchange
*/

temp = (NODE*)malloc(sizeof(NODE));

tail->next = tail->prev;
tail->prev = temp;

mainHead = temp; // This will be used
for final printing of Data
from resulted db list

/*
* Node interchange Kernel
*/

tail->next = tail->prev;
tail->prev = temp;
}

else {

if(!(tail->next))
else
>next;
tail->next = tail->prev;
tail->prev = temp;
}
}

printf("\n");

i = TravelNode;
while(i-- 0){

printf(" R = %d ", mainHead->data);
}

printf("\n End.... \n");
----------------------------------------------------------------------------------------------------------------
Mar 19 '08 #1
1 2101 Mahesh wrote:
Hi Coders,

I was asked to write a program to interchange numbers using doubly

Here is the details with Code that i wrote.

i/p: 1 2 3 4 5 6 7 8 .....n,n-1.
o/p: 2 1 4 3 6 5 8 7.....n,n-1.

I wanted this code to make as small and it should be algorithmically
fit. The following is just plain without any logic. plz help me to
solve this algorithmically i.e big oh etc. and it should run fast for
millions of numbers.

/* BEGIN bubble_llist.c */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 8

typedef struct list_node {
struct list_node *next;
void *data;
struct list_node *prev;
} llist_type;

llist_type *llist_append
(llist_type **head, llist_type *tail, void *data, size_t size);
int u_fprintf(const llist_type *head, FILE *stream);
void llist_free(llist_type *node, void (*free_data)(void *));

int main(void)
{
unsigned count;

puts("/* BEGIN bubble_llist.c output */\n");
for (count = 1; count != N + 1u; ++count) {
tail = llist_append(&head, tail, &count, sizeof count);
if (tail == NULL) {
puts("malloc trouble!");
break;
}
}
putchar('\n');
puts("\n/* END bubble_llist.c output */");
return 0;
}

{
llist_type *ret;

for (;;) {
const llist_type second = *first.next;

second.prev -prev = first.next;
second.prev -next = second.next;
first.next -prev = first.prev;
first.next -next = second.prev;
if (head -next != NULL) {
} else {
break;
}
} else {
break;
}
}
} else {
}
return ret;
}

llist_type *llist_append
(llist_type **head, llist_type *tail, void *data, size_t size)
{
llist_type *node;

node = malloc(sizeof *node);
if (node != NULL) {
node -prev = tail;
node -next = NULL;
node -data = malloc(size);
if (node -data != NULL) {
memcpy(node -data, data, size);
tail -next = node;
} else {
}
} else {
free(node);
node = NULL;
}
}
return node;
}

int u_fprintf(const llist_type *head, FILE *stream)
{
int rc = 0;

const unsigned *const u_ptr = head -data;

if (0 (rc = fprintf(stream, "%u\n", *u_ptr))) {
break;
}
}
return rc;
}

void llist_free(llist_type *node, void (*free_data)(void *))
{
llist_type *next_node;

while (node != NULL) {
next_node = node -next;
free_data(node -data);
free(node);
node = next_node;
}
}

/* END bubble_llist.c */
--
pete
Jun 27 '08 #2

### This discussion thread is closed

Replies have been disabled for this discussion.