Doubly Linked List Issues?

Question

I've created, what I think to be a doubly linked list. The idea is to reverse output of words entered each on a new line, so:

Hello\nAll\n.
.\nAll\nHello

The idea is to traverse my list until '\n' is found, then go in the opposite direction and print that off, go back to where I left, continue traversing until another new line, then go forward again and print etc.

However, my current implementation I can't seem to get to work and I've hit a brick wall, and hints or tips are appreciated!

typedef struct L { 
char val;
struct L *next;
struct L *prev;
}List;

List *insertList(char val, List *t1 );
List *createList(void);

int main(void) {
  List *z = createList();
  List *pos = z;
  while (pos != NULL) {
    while ( z->val != '\n' ) {
        if (z == NULL)
            break;
            z = z->next;
            pos = z;
}
    while (z != NULL) {
        printf("%c", z->val);
        z = z->prev;
    }
}
return 0;
}
List *createList(void) {
  List *h = NULL;
  char c;
  do { 
    c =(char)getchar();
    h = insertList(c, h);
  }while(c != '.');
  return h;
 }
List *insertList( char val, List *t1) {
  List *t = calloc(1, sizeof( List ));
  t->prev = NULL;
  t->val = val;
  t->next = t1;
    if (t1 != NULL) {
     t1->prev = t;
  }
return t;
}

Answer 1

#include<stdio.h>
#include<conio.h>
#include<malloc.c>
struct dnode{
int data;
struct dnode *prev,*next;
};
typedef struct dnode DNODE;
DNODE *first;
DNODE *last;

DNODE* createDnode(int ele){
DNODE *nnode;
nnode=(DNODE *)malloc(sizeof(DNODE));
nnode->data=ele;
nnode->next=NULL;
nnode->prev=NULL;
return nnode;    

}

//Insert First

DNODE *insertFirst(int ele){
DNODE *nnode;
nnode=createDnode(ele);
if(first==NULL){ //if node is creating first time
    first=last=nnode;
    return;    
}
nnode->prev=NULL;
nnode->next=first;
first=nnode;
return first;
} 

//Insert Last

DNODE *insertLast(int ele){
DNODE *nnode;
nnode=createDnode(ele);
if(first==NULL){ //if node is creating first time
    first=last=nnode;
    return;    
}
last->next=nnode;
nnode->prev=last;
last=nnode;
return last;    
}

 //Insert Before an Element

DNODE *insertBefore(int ele,int key){
DNODE *nnode,*curr,*pre;
nnode=createDnode(ele);
if(first==NULL){ //if node is creating first time
    first=last=nnode;
    return;    
}
if(first->data==key){  // if key is found at first node
    nnode->next=first;
    first=nnode; 
    return first;   
}
curr=first;
while(curr && curr->data!=key){
    pre=curr;
    curr=curr->next;   
}   
if(!curr){   //if search not found then curr will be NULL, it's means the node is added at last
    last->next=nnode;
    nnode->prev=last;
    last=nnode;
    return last;
}
    curr->prev->next=nnode;
    nnode->prev=curr->prev;
    nnode->next=curr;
    curr->prev=nnode;
    return;
  }

 // Insert After an Element

  DNODE *insertAfter(int ele,int key){
  DNODE *nnode,*curr,*pre;
  nnode=createDnode(ele);
  if(first==NULL){ //if node is creating first time
    first=last=nnode;
    return;    
}
curr=first;
while(curr && curr->data!=key){
    //pre=curr;
    curr=curr->next;   
}   
if(!curr){   //if search not found then curr will be NULL, it's means the node        is added at last
    last->next=nnode;
    nnode->prev=last;
    last=nnode;
    return last;
}
nnode->next=curr->next;
curr->next->prev=nnode;
nnode->prev=curr;
curr->next=nnode;
return;    

}

// Remove Function

int removeNode(int key){
DNODE *curr;
if(first==NULL){ //if node is creating first time
    printf("\n\nList is Empty");
    return -1;    
}
curr=first;
if(first->data==key){  //if first node has key
   first=first->next;
   first->prev=NULL;
   curr->next = NULL;
   free(curr);
   return;
}

while(curr && curr->data!=key){
    curr=curr->next;   
} 
if(!curr){   //if search not found then curr will be NULL, 
    return -1;
}

curr->prev->next=curr->next;
curr->next->prev=curr->prev;
curr->next = curr->prev = NULL;
printf("\n\n%d is Successfully Deleted: ",curr->data);
free(curr);
return;
}

void display(){
DNODE *curr;
if(first==NULL)
    printf("\n\nNothing to Display\n\n");
curr=first;
printf("\n\n\tElement in List\n\n\t");
while(curr){
    printf("%d ",curr->data);
    curr=curr->next;    
  }
 }
 main(){
int ele,ch,key;
do{
    printf("\nEnter Your Choice: \n");
    printf("1-Insert First\t2-Insert Last\n3-Insert Before\t4-Insert After\n5-Remove  \t6-Display\n");
    scanf("%d",&ch);
    switch(ch){
        case 1:
            printf("Enter Element To Insert: ");
            scanf("%d",&ele);
            insertFirst(ele);
            break;  
        case 2:
            printf("Enter Element To Insert: ");
            scanf("%d",&ele);
            insertLast(ele);
            break;
         case 3:
            printf("Enter Element To Insert: ");
            scanf("%d",&ele);
            printf("\nEnter Key: ");
            scanf("%d",&key);
            insertBefore(ele,key);
            break;  
        case 4:
            printf("Enter Element To Insert: ");
            scanf("%d",&ele);
            printf("\nEnter Key: ");
            scanf("%d",&key);
            insertAfter(ele,key);
            break; 
        case 5:
            printf("Enter Key to Delete: ");
            fflush(stdin);
            scanf("%d",&key);
            removeNode(key);
            break;
        case 6:
            display();
            break;
    }  
}while(ch!=7);
getch();
return 0;    

}

Answer 2

Ok, I've had time to see why my first answer wouldn't work - a few little obvious things if you run the code through a debugger. So here's a fully working version. It could probably be optimised quite a bit, but it follows the same structure as your original code so hopefully you can follow it:

typedef struct L { 
    char val;
    struct L *next;
    struct L *prev;
} List;

List* insertList( char val, List *t1 ) {
    List *t = calloc(1, sizeof( List ));
    t->prev = NULL;
    t->val = val;
    t->next = t1;
    if (t1 != NULL)
        t1->prev = t;
    return t;
}

List* createList( void ) {
    List *h = NULL;
    char c;

    do {
        c =(char)getchar();
        h = insertList( c, h );
    } while (c != '.');

    return h;
}

void freeList( List *list ) {
    // free the linked list
    if (list != NULL) {
        freeList( list->next );
        free( list );
    }
}

int main( void ) {
    // create list
    List *head = createList();
    List *pos = head, *currentChar = NULL, *wordStart = NULL;

    while (pos != NULL)
    {
        // find next word
        wordStart = NULL;
        while (pos != NULL)
        {
            // gone past the beginning of a word yet?
            if ((pos->val == '\n') || (pos->next == NULL)) 
            {
                wordStart = (pos->next == NULL) ? pos : pos->prev; // note where this word starts
                pos = pos->next; // jump over \n, or go to end of list (null), for next time into this loop
                break; // jump out of this loop so we can output the word
            }
            else // not found end of word yet - on to next char
                pos = pos->next;
        }

        // have we found a word? if so, output it!
        if (wordStart != NULL)
        {
            currentChar = wordStart; // start at first char in the word
            while (currentChar != NULL)
            {
                printf( "%c", currentChar->val ); // output this char
                currentChar = currentChar->prev; // on to next char in the word
                if ((currentChar != NULL) && (currentChar->val == '\n')) 
                    break; // stop after last char of the word
            }
            // print the line-feed just before wordStart (if there is one)
            if (wordStart->next != NULL)
                printf( "%c", wordStart->next->val );
        }
        else // we've reached the end - stop
            break; // not really necessary - pos should be NULL at this point anyway
    }

    freeList( head ); // free linked list memory

    return 0;
}

The main change is how I output the linefeed. I realised it's NOT the linefeed after each word you need, but the one just BEFORE it (not logical at all - I wonder if that is what the question originally intended?). But it now outputs exactly what you require. And I've added a function to free the linked list memory at the end too for you. :)

Answer 3

I think your structure needs to be changed and there is no reason to have a double linked list to solve your problem.

your struct should contain

struct node {
char *word;
struct node *next;
};

Then your main loop should be something like:

1) Read character data until delimiter into expandable buffer. Add NULL string terminator.
2) When delimiter is reached create node that points to buffer.
3) Insert NODE at HEAD of list.
4) When '.' is reached print each string starting from head of list.

Answer 4

Try these while loops instead [EDITED to note Chris' comment about checking for end of LL]:

while (pos != NULL) {
    while (z != NULL) {
        // if you've reached the line feed or the end of the linked list
        if ((z->val == '\n') || (z->next == NULL)) {
            pos = z->next; // store list position just after this char for next time through
            break;
        }
        z = z->next;
    }
    while (z != NULL) {
        printf("%c", z->val);
        z = z->prev;
        // don't print more than just this word!:
        if ((z != NULL) && (z->val == '\n'))
            break;
    }
    // reset z for top inner while loop
    z = pos;
}

Basic issue was that z was not reset when the outer while loop wrapped around; second issue was that end of linked list didn't break out of first inner while loop; third issue was second inner while loop didn't check for end of the word it was printing.

You also need to free the linked list at the end or it'll be a memory leak. You should also check the return value of calloc() to be sure it didn't return null.