inserting a node in middle of doubly linked list

[red999]

I am trying to insert a node before another node in a doubly linked list and I have been trying to do for awhile, but I still can't get it =/. I keep getting error whenever I try to display the list after I insert in a new node. Please help.

#include <stdio.h>
#include <stdlib.h>
#define SENT -1
#define MAX 100

typedef struct nodes {
        int element;
        struct nodes *fp;
        struct nodes *bp;
} node_t;

node_t *head, *tail, *current;

void insert_end(node_t *list){
       if (head == NULL){
          head = list;
          list->bp = NULL;}
       else {
            tail->fp = list;
            list->bp = tail;
            }
       tail = list;
       list->fp =NULL;
}

void insert_start(node_t *list, int num){
     node_t *newp, *temp = head;
     list = head;
     newp = (node_t *)malloc(sizeof(node_t));
     newp->element = num;
     newp->fp = temp;
     newp->bp = NULL;
     list->bp = newp;
     head = newp;
}  


//insert a node in front of a selected node
void insert_front(node_t *list, int insert, int node){
     int i;
     node_t *newp, *temp;
     list = head;
     i = list->element;
     while (list->fp != NULL){
          if (i == node) break;
          list = list->fp;
          i = list->element;
    }
     newp = (node_t *)malloc(sizeof (node_t));
     newp->element = insert;
     temp = list;
     newp->fp = temp->fp;
     temp->fp->fp = newp;
     temp->fp = newp;
     newp->bp = temp;
     list = temp;
} 
void prompt(){
     printf("\n\n0 Quit\n");
     printf("1 Insert node at the beginning of the list\n2 Insert node at the end of the list\n3 Insert node in front of a node\n");
     printf("4 Delete node\n");
     printf("5 Display-to-rear\n6 Display-to-front\n");
     printf("\nYour choice(0-5): ");
     }

void display(node_t *list){
     printf("Current list: ");
     for(list = head; list != NULL; list = list->fp) {
          printf("%d ", list->element);}   
     }

int ask_num(){
    int num;
    printf("Enter a positive integer: ");
    scanf("%d", &num);
    return num;
}

int find_num(node_t *list, int num){
    int i;
    list = head;
    i = list->element;
    while (list->fp != NULL){
          if (i == num) return 1;
          list = list->fp;
          i = list->element;
          }
    return 0;
}
    
                       
int main(int argc, char **argv){
    int num, key, node, i, find, num_in_file[MAX];
    node_t *my_list;
    FILE *inp;

    inp = fopen(argv[1], "r");
    for (fscanf(inp, "%d", &num), i = 0; num != SENT; ++i, fscanf(inp, "%d", &num)){
        num_in_file[i] = num;
        }
    for (--i, num = num_in_file[i]; i >= 0; --i, num = num_in_file[i]){
        my_list = (node_t *)malloc(sizeof(node_t));
        my_list->element = num;
        insert_end(my_list);
        }
    fclose(inp);
    display(my_list);
    do {
        prompt();
        scanf("%d", &key);
        switch (key){
               case 0:
                    break;
               case 1:
                    num = ask_num();
                    insert_start(my_list, num);
                    printf("\n");
                    display(my_list);
                    break;
               case 2:
                    num = ask_num();
                    my_list = (node_t *)malloc(sizeof(node_t));
                    my_list->element = num;
                    insert_end(my_list);    
                    printf("\n");
                    display(my_list);   
                    break;   
               case 3:
                    num = ask_num();
                    printf("Insert %d in front of which node? ", num);
                    scanf("%d", &node);
                    find = find_num(my_list, node);
                    if (find == 1){
                       insert_front(my_list, num, node);}
                       printf("\n");
                       display(my_list);
                             
               }
        } 
    while (key != 0);            
    return 0;
}

[s_sridhar]

if list is the node which you must add, traverse the linked list which you created and if run is the current node(used for traversing,

if(run->fp->element==required element)
list->fp=run->fp;
list->bp=run;
run->fp->bp=list;

[rcollins]

I am going to walk my way through your code for void insert_front(node_t *list, int insert, int node) and just list some issues I see and hopefully that will help you to correct any problems you are having.
1. Check to make sure head isn't null.
2. You can use list->element in a conditional check you don't necessarily need to store that in a new variable just to do the conditional check. (this suggestion just cleans things up a bit)
3. I don't know what you want for your default behavior however right now your code doesn't check if the node was actually found before starting the process of adding the new node.

[IMG]http://img5.imageshack.us/img5/7158/doublelinkedlist.jpg[/IMG]
The code is to hard to describe so I put together this image to hopefully allow you to see what it is your code is doing. I suggest you start over with your code to add the node. Start by drawing out what you want to see happen. Also by drawing it you you will notice things like the line list = temp; doesn't really do anything because those pointers never changed.

[red999]

I noticed that in the picture that after the code temp = list;
temp points to the fp node that points to list.

I always thought that that code means that temp points to the list node and that list = head; will make list points to the head node instead of the bp node before it, which does not exist. Can you explain that a little bit more?

[ArkM]

It seems you don't verify your list interface.
For example:
1. What's a role of the 1st insert_start parameter? You overwrite its value in the 1st statement of the function body then create new node...
2. On the contrary, insert_end uses its parameter if global variable head is not equal to NULL and does not create new nodes...
3. The function display() has parameter but uses it as a loop control variable only (?)
4. The function find_num() has parameter but uses it as a temporary variable...
... and so on ...
I think it's not so easy to implement this untidy interface in clear and error-free code...

Better try to redesign most of your functions signatures. Pass list head ponter as a parameter in all list-oriented functions (avoid using global head and tail variables). Moreover, no need in the tail pointer for double-linked list because head->previous (bp member in your program) refers to the last node!

[rcollins]

I noticed that in the picture that after the code temp = list;
temp points to the fp node that points to list.

I always thought that that code means that temp points to the list node and that list = head; will make list points to the head node instead of the bp node before it, which does not exist. Can you explain that a little bit more?

[IMG]http://img190.imageshack.us/img190/7742/dllnode.jpg[/IMG]
Maybe my picture was a little unclear. The outer squares represent the node the two smaller squares at the bottom of that node represent bp and fp.
After temp=list; temp is pointing to the same node as list.

[red999]

It seems you don't verify your list interface.
For example:
1. What's a role of the 1st insert_start parameter? You overwrite its value in the 1st statement of the function body then create new node...
2. On the contrary, insert_end uses its parameter if global variable head is not equal to NULL and does not create new nodes...
3. The function display() has parameter but uses it as a loop control variable only (?)
4. The function find_num() has parameter but uses it as a temporary variable...
... and so on ...
I think it's not so easy to implement this untidy interface in clear and error-free code...

Better try to redesign most of your functions signatures. Pass list head ponter as a parameter in all list-oriented functions (avoid using global head and tail variables). Moreover, no need in the tail pointer for double-linked list because head->previous (bp member in your program) refers to the last node!

I miss Python's list now lol. I'll do what you suggested tomorrow since it is getting late.

Anyway I noticed I occasionally get errors whenever I run my delete function. Can you guys take a look at my delete function? If I delete the last node all the times, it will work, but if I delete a middle node and then delete another node. I'll get an error.

#include <stdio.h>
#include <stdlib.h>
#define SENT -1
#define MAX 100

typedef struct nodes {
        int element;
        struct nodes *fp;
        struct nodes *bp;
} node_t;

node_t *head, *tail;

void insert_end(node_t *list){
       if (head == NULL){
          head = list;
          list->bp = NULL;}
       else {
            tail->fp = list;
            list->bp = tail;
            }
       tail = list;
       list->fp =NULL;
}

void insert_start(node_t *list, int num){
     node_t *newp, *temp = head;
     list = head;
     newp = (node_t *)malloc(sizeof(node_t));
     newp->element = num;
     newp->fp = temp;
     newp->bp = NULL;
     list->bp = newp;
     head = newp;
}  
    
void insert_front(node_t *list, int insert, int node){
     int i;
     node_t *newp, *temp;
     list = head;
     newp = (node_t *)malloc(sizeof (node_t));
     newp->element = insert;
     newp->fp = NULL;
     newp->bp = NULL;
     if (list->element == node){
        newp->fp = list;
        list->bp = newp;
        head = newp;
        return;
        }
     temp = list;
     while (temp->fp != NULL){
           if (temp->fp->element == node){
              newp->fp = temp->fp;
              temp->fp->bp = newp;
              temp->fp = newp;
              newp->bp = temp;
              return;
              }
           temp = temp->fp;
     }
} 

void delete(node_t *list, int num){
     node_t *deletep, *temp;
     list = head;
     if (list->fp == NULL){
        head = NULL;
        return;}
     else if (list->element == num){
        deletep = list;
        list = list->fp;
        list->bp = NULL;
        free(deletep);
        head = list;
        }
     else {
          temp = list;
          temp = temp->fp;
          while (temp != NULL){
                if (temp->element == num){
                   temp = temp->bp;
                   deletep = temp->fp;
                   temp->fp = deletep->fp;
                   free(deletep);
                   }
                temp = temp->fp;    
             }
          }
     }
                           
void prompt(){
     printf("\n\n0 Quit\n");
     printf("1 Insert node at the beginning of the list\n2 Insert node at the end of the list\n3 Insert node in front of a node\n");
     printf("4 Delete node\n");
     printf("5 Display-to-rear\n6 Display-to-front\n");
     printf("\nYour choice(0-5): ");
     }

void display(node_t *list){
     printf("Current list: ");
     for(list = head; list != NULL; list = list->fp) {
          printf("%d ", list->element);}   
     }

int ask_num(){
    int num;
    printf("Enter a positive integer: ");
    scanf("%d", &num);
    return num;
}

int find_num(node_t *list, int num){
    int i;
    list = head;
    i = list->element;
    while (list != NULL){
          if (i == num) return 1;
          list = list->fp;
          i = list->element;
          }
    return 0;
}
    
                       
int main(int argc, char **argv){
    int num, key, node, i, find, num_in_file[MAX];
    node_t *my_list;
    FILE *inp;

    inp = fopen(argv[1], "r");
    for (fscanf(inp, "%d", &num), i = 0; num != SENT; ++i, fscanf(inp, "%d", &num)){
        num_in_file[i] = num;
        }
    for (--i, num = num_in_file[i]; i >= 0; --i, num = num_in_file[i]){
        my_list = (node_t *)malloc(sizeof(node_t));
        my_list->element = num;
        insert_end(my_list);
        }
    fclose(inp);
    display(my_list);
    do {
        prompt();
        scanf("%d", &key);
        switch (key){
               case 0:
                    break;
               case 1:
                    num = ask_num();
                    insert_start(my_list, num);
                    printf("\n");
                    display(my_list);
                    break;
               case 2:
                    num = ask_num();
                    my_list = (node_t *)malloc(sizeof(node_t));
                    my_list->element = num;
                    insert_end(my_list);    
                    printf("\n");
                    display(my_list);   
                    break;   
               case 3:
                    num = ask_num();
                    printf("Insert %d in front of which node? ", num);
                    scanf("%d", &node);
                    find = find_num(my_list, node);
                    if (find == 1){
                       insert_front(my_list, num, node);
                       printf("\n");
                       display(my_list);}
                    else{
                         printf("\n%d was not found in list.\n", node);
                         display(my_list);}
                    break;
               case 4:
                    num = ask_num();
                    delete(my_list, num);
                    printf("\n");
                    display(my_list);
                    break;

                         
                             
               }
        } 
    while (key != 0);            
    return 0;
}

[rcollins]

void delete(node_t *list, int num){
     node_t *deletep, *temp;
     list = head;
     if (list->fp == NULL){
        head = NULL;
        return;}
     else if (list->element == num){
        deletep = list;
        list = list->fp;
        list->bp = NULL;
        free(deletep);
        head = list;
        }
     else {
          temp = list;
          temp = temp->fp;
          while (temp != NULL){
                if (temp->element == num){
                   temp = temp->bp;
                   deletep = temp->fp;
                   temp->fp = deletep->fp;
                   free(deletep);
                   }
                temp = temp->fp;    
             }
          }
     }

In your very first if statement you are throwing out a node without checking to see if it is the one you want. You are not freeing that memory either. In the second if statement you lose any of the list before the element you are trying to delete. In the final else statement you redo the entire function with two mistakes. 1. You don't need the first temp = temp->fp . With it there you aren't checking to see if the head element is the one you want to delete. 2. you need to set the bp of the node after deletep to point back to the node before deletep . Basically except for the two issues I described the last else block is the code you need for this function.

[red999]

I just fixed up my delete function, but for some reason if I want to delete the first node, my program will keep printing random numbers. Can someone take a look at it? Here is the part that deletes the first node.

node_t * delete(node_t *list, int num){
     node_t *current, *temp;
     current = list;
     if (list->element == num){
        list = list->fp;
        free(current);
        list->bp = NULL;
        return current;
        }

[red999]

Uh.... stupid me, I forgot to make the returned value into a variable for my display function.

[kvprajapati]

I just fixed up my delete function, but for some reason if I want to delete the first node, my program will keep printing random numbers. Can someone take a look at it? Here is the part that deletes the first node.

node_t * delete(node_t *list, int num){
     node_t *current, *temp;
     current = list;
     if (list->element == num){
        list = list->fp;
        free(current);        
        list->bp = NULL;
        return current;
        }

delete() function must return content of list pointer.

node_t * delete(node_t *list, int num){
     node_t *current, *temp;
     current = list;
     if (list->element == num){
          list = list->fp;
          free(current);
          list->bp = NULL;
          return list;
         }
         ....