help! Placement of nodes in a Linked List

hey everyone I am creating a program that creates a linked list and the program has to have a menu to let the user 1.add to the beginning of the list. 2. add to the end of the list. 3. delete a particular character from the list 4. prints the list and 5. exits. I have the whole structure of the program done but I cannot get the adding to the beginning or the end of the list part down. No matter what you do if there is already an "A" or a "C" in the list, if you add "B" it will put the character right in between the "A" and the "C". Please help!

Code:

---

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

/* self-referential structure */
struct listNode {
        char data; /* each listnode contains a character */
        struct listNode *nextPtr;
};
       
typedef struct listNode ListNode ;
typedef ListNode *ListNodePtr;
       
/* prototypes */
void insertbegin( ListNodePtr *sPtr, char value );
void insertend( ListNodePtr *sPtr, char value );
char delete( ListNodePtr *sPtr, char value );
int isEmpty (ListNodePtr sPtr );
void printList( ListNodePtr currentPtr );
void instructions( void );
/***************************************************************************/       
int main( void )
{
        ListNodePtr startPtr = NULL; /* init no nodes */
        int choice;                                                  /* user's choice */
        char item;                                                  /* char entered by user */
       
        instructions(); /* display menu */
        printf("? ");
        scanf( "%d", &choice );
       
        /* loop while user doesn't choose 5 (quit) */
        while ( choice != 5){
       
                switch ( choice ) {
               
                        case 1:
                                printf( "Enter a character: ");
                                scanf( "\n%c", &item );
                                insertbegin( &startPtr, item ); /* add item to beginning of list */
                                break;

                        case 2:
                                printf( "Enter a character: ");
                                scanf( "\n%c", &item );
                                insertend( &startPtr, item ); /* add item  to end of list */
                                break;
                               
                        case 3:
                                /* if list is not empty */
                                if ( !isEmpty( startPtr ) ) {
                                        printf( "Enter character to be deleted: ");
                                        scanf( "\n%c", &item );
                                        /*if character is found, remove it*/
                                        if ( delete( &startPtr, item ) ) {/* delete item from list */
                                                printf( "%c deleted.\n", item );
                                        }
                                        else {
                                                printf("%c not found.\n\n", item );
                                                }
                                        }
                                        else {
                                                printf("List is empty.\n\n" );
                                        }
                               
                                break;
                       
                        case 4:
                                printList( startPtr); /* print list */
                                break;
                       
                        default:
                                printf( "Invalid Choice.\n\n");
                                instructions();
                                break;
                               
                        } /* end switch */
                       
                        printf("? ");
                        scanf( "%d", &choice );
                } /* end while */
               
                printf( "End of run.\n" );

return 0;

}

/* display program instructions to user */
void instructions( void )
{
        printf( "Enter your choice:\n"
                "  1 to insert an element into the beginning of the list.\n"
                "  2 to insert an element into the end of the list.\n"
                "  3 to delete an element from the list.\n"
                "  4 to print the list.\n"
                "  5 to quit.\n");
}
/***************************************************************************/
void insertbegin( ListNodePtr *sPtr, char value )        /* Insert a new value into the list in sorted order */
{
        ListNodePtr newPtr;                        /*pointer to new node*/
        ListNodePtr previousPtr;        /*pointer to previous node in list*/
        ListNodePtr currentPtr;                /*pointer to current node in list*/
       
        newPtr = malloc( sizeof( ListNode ) ); /* create node */
       
        if ( newPtr != NULL ) { /* is space available */
                newPtr->data = value; /*place value in node*/
                newPtr->nextPtr = NULL; /* node does not link to another node*/
               
                previousPtr = NULL;
                currentPtr = *sPtr;
               
                /* loop to find the correct location in the list */
                while ( currentPtr != NULL && value > currentPtr->data ) {
                        previousPtr = currentPtr;
                        currentPtr = currentPtr->nextPtr;
                } /* end while */
               
                /* insert new node at beginning of list */
                if ( previousPtr == NULL ) {
                        newPtr->nextPtr = *sPtr;
                        *sPtr = newPtr;
                } /* end if */
                else { /* insert new node between previousPtr and currentPtr */
                        previousPtr->nextPtr = newPtr;
                        newPtr->nextPtr = currentPtr;
                } /* end else */
       
        } /* end if */
        else {
                printf( "%c not inserted. No memory available.\n", value );
        } /* end else */
}
/***************************************************************************/
void insertend( ListNodePtr *sPtr, char value )        /* Insert a new value into the list in sorted order */
{
        ListNodePtr newPtr;                        /*pointer to new node*/
        ListNodePtr previousPtr;        /*pointer to previous node in list*/
        ListNodePtr currentPtr;                /*pointer to current node in list*/
       
        newPtr = malloc( sizeof( ListNode ) ); /* create node */
       
        if ( newPtr != NULL ) { /* is space available */
                newPtr->data = value; /*place value in node*/
                newPtr->nextPtr = NULL; /* node does not link to another node*/
               
                previousPtr = NULL;
                currentPtr = *sPtr;
               
                /* loop to find the correct location in the list */
                while ( currentPtr != NULL && value > currentPtr->data ) {
                        previousPtr = currentPtr;
                        currentPtr = currentPtr->nextPtr;
                } /* end while */
               
                /* insert new node at beginning of list */
                if ( previousPtr == NULL ) {
                        newPtr->nextPtr = *sPtr;
                        *sPtr = newPtr;
                } /* end if */
                else { /* insert new node between previousPtr and currentPtr */
                        previousPtr->nextPtr = newPtr;
                        newPtr->nextPtr = currentPtr;
                } /* end else */
       
        } /* end if */
        else {
                printf( "%c not inserted. No memory available.\n", value );
        } /* end else */
}

/***************************************************************************/
/* Delete a list element */
char delete( ListNodePtr *sPtr, char value )
{
        ListNodePtr previousPtr;
        ListNodePtr currentPtr;
        ListNodePtr tempPtr;
       
        /* delete first node */
        if ( value == ( *sPtr )->data ) {
                tempPtr = *sPtr;
                *sPtr =( *sPtr )->nextPtr;
                free( tempPtr );
                return value;
        } /* end if */
        else {
                previousPtr - *sPtr;
                currentPtr = ( *sPtr )->nextPtr;
               
                /* loop to find the correct location in the list */
                while ( currentPtr != NULL && currentPtr->data != value ) {
                        previousPtr = currentPtr;
                        currentPtr = currentPtr->nextPtr;
                } /* end while */
               
                /*delete node at currentPtr */
                if ( currentPtr != NULL )  {
                        tempPtr = currentPtr;
                        previousPtr->nextPtr = currentPtr->nextPtr;
                        return value;
                } /* end if */
               
        } /* end else */
       
        return '\0';
       
} /* end function delete */
/***************************************************************************/
/* Return 1 if the list is empty, 0 otherwise */
int isEmpty( ListNodePtr sPtr )
{
        return sPtr == NULL;
}
/***************************************************************************/
/* Print the list */
void printList( ListNodePtr currentPtr )
{

        /* if list is empty */
        if ( currentPtr == NULL ) {
                printf("List is empty.\n\n");
        }
        else {
                printf( "The list is:\n" );
               
                /* while not the end of the list */
                while ( currentPtr != NULL ) {
                        printf( "%c ", currentPtr->data );
                        currentPtr = currentPtr->nextPtr;
                }
               
                printf( "\n\n");
        }
       
} /* end function printList */

---

thank you!

Wow. You're not quite getting the idea of a linked list, though.
The idea is that you have pointers to every node. Not some "normal" node placed on the stack they you're reassigning.
I don't get the idea with insertbegin and insertend if you're just going to sort the list anyway.

First error:

Code:

---

                previousPtr - *sPtr;

---

In delete.
Illegal since you're dereferencing sPtr. Even so, you're not reassigning it, so it's useless. Even if not illegal, it will probably not do what you intend.
previousPtr is not even a pointer, so that's even more weirdness. Perhaps you intended to do =?

Code:

---

        if ( value == ( *sPtr )->data ) {

---

In delete, you are dereferencing the pointer AND using ->. sPtr is not **, so that's kinda illegal. Stupid C allows this kind of crap

so what does that mean for the code, the delete function works fine its just adding to the beginning and the end im having trouble with

Quote:

---

Code:

---

void insertbegin( ListNodePtr *sPtr, char value )        /* Insert a new value into the list in sorted order */

---

---

<sings> One of these things is not like the others... </sings>
Although I do congratulate you on having code that matches your comments.
If you want to insert at the beginning of the list, why walk the list to find the correct place to put it? Just put it right there.
Same for end; just go until you can't go any more, then put a new entry in the list.

Given that inserting an item into a list in order is always more work than simply placing it at either end, you obviously copied the insertion routine from elsewhere and don't understand it.
Try to understand how the insert routine works. It has everything you need for inserting at either end.

Quote:

---

Originally Posted by lostmyshadow

so what does that mean for the code, the delete function works fine its just adding to the beginning and the end im having trouble with

---

Your code is flawed. Most likely you're just no giving the right scenario to execute that flawed code, but when it does, be sure it will crash!
* and -> both DEREFERENCES the pointer (eg accesses the value stored at the address), so in essence you're doing in twice. And what happens if you try to dereference a value that is not a pointer? Exactly. Crash!

here is the correct solution:

Code:

---

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

typedef struct
{
  char code[25];                // course code
  }course_t;

typedef struct node_s
{
  course_t item;        // data
  struct node_s *next;        // pointer to the next node
} node_t;

// Pointer to a node:
typedef node_t* nodeptr;

/*function prototypes*/
nodeptr getnode(void);
void add_begin(nodeptr *head, course_t item);
void add_end(nodeptr *head, course_t item );
int del_data(nodeptr *head, char course_code[]);
void instructions (void);
void PrintList (nodeptr * ptr);
               
/*************************************************************************************/
void instructions (void)
{
        printf("Enter you choice:\n"
                "        1 - to insert an element into the beginning of the list\n"
                "        1 - to insert an element into the beginning of the list\n"
                "        1 - to delete an element you specify\n"
                "        1 - to print the list\n"
                "        1 - exit\n");
}
//----------------------------------------------------------
// Getting a new node: allocates memory for a new node
//----------------------------------------------------------
nodeptr getnode(void)
{
  nodeptr ptr;

  ptr = (node_t*) malloc(sizeof(node_t));        // Allocate memory
  return(ptr);                        // Return pointer to allocated memory
} // end getnode

//----------------------------------------------------------
// Adding a node to the beginning of a list.
//----------------------------------------------------------
void add_begin(nodeptr *head,        // head of the list
              course_t item)        // data of the list
{
  nodeptr newptr;        // pointer for a new node

  newptr = getnode();        // get a new node
  newptr->item = item;        // store data into new node
  newptr->next = *head;        // newnode will point to whatever head was pointing
  *head = newptr;        // new node will be the head
} // end add_begin

//----------------------------------------------------------
// Adding a node to the end of a list:
//----------------------------------------------------------
void add_end(nodeptr *head,        // head of the list
            course_t item )        // data of the list
{
  nodeptr newptr, ptr;

  newptr = getnode();        // Get a new node
  newptr->item = item;        // Store data into new node
  newptr->next = NULL;        // Set next of new node to NULL

  if (*head == NULL)
  {                        // Linked list was empty
    *head = newptr;        // add to beginning
  }
  else
  {                        // Linked List was not empty. Find last node.
    ptr = *head;                // point to beginning of list
    while(ptr->next != NULL)        // while it is not the last node,
    { ptr = ptr->next; }        // pass to the next node
    ptr->next = newptr;                // old last node is followed by new node
  }

} // end add_end


//----------------------------------------------------------
// Delete a node with a given data
// Returns 1 if a deletion is performed, 0 if no deletion is performed.
//----------------------------------------------------------
int del_data(nodeptr *head,                // head of the list
              char course_code[])        // course code to be deleted
{
  nodeptr ptr,                        // Ptr to current node
          prevptr = NULL;        // Ptr to previous node
  int  ret_val = 0;                // Value to be returned.

  if(*head != NULL)                // If list is not empty, then:
  {
    ptr = *head;                        // point to beginning of list
    // Traverse list while data not found and not end of list
    while(strcmp(course_code, ptr->item.code) != 0 &&
          ptr->next != NULL)       
    {
      prevptr = ptr;                // Store pointer to previous node
      ptr = ptr->next;                // Pass to the next node
    }

    // Check if data is found:
    if(strcmp(course_code, ptr->item.code) == 0)
    {
      ret_val = 1;
      if(ptr == *head)
      { // If found node is the first node, then:
        del_begin(head);                // Delete the first node
      }
      else
      { // Now, prevptr points to prev. node, and ptr points to found node
        prevptr->next = ptr->next;        // Set next of previous node
        free(ptr);                        // Free the deleted node
      }
    }
  }
  return (ret_val);
} // end del_data
/*************************************************************************************/                       
void PrintList (nodeptr * ptr) {

        if (ptr == NULL) {
                printf("List is empty!\n");
                }
        else {
                while (ptr != NULL) {
                        printf("%d\t", ptr -> item);
                        ptr = ptr -> *next;
                }        /* end while */
        printf("\n");
        } /* end else */
}
/*************************************************************************************/
int main(void) {

        nodeptr startPtr = NULL;
        int choice;
        char item;
       
        instructions (); /*display menu*/
        printf("? ");
        scanf("%d" , &choice );
       
        /* loop while user does not choose 5 */
        while ( choice != 5 ) {
       
                switch ( choice ) {
                       
                        case 1:
                                printf( "Enter a character: ");
                                scanf( "\n%c", &item );
                                add_begin( &startPtr, item ); /* insert item into list */
                                break;

                        case 2:
                                printf( "Enter a character: ");
                                scanf( "\n%c", &item );
                                add_end( &startPtr, item ); /* insert item into list */
                                break;
                               
                        case 3:
                                printf( "Enter a character: ");
                                scanf( "\n%c", &item );
                                add_begin( &startPtr, item ); /* insert item into list */
                                break;
                       
                        case 4:
                                printf( "Enter a character: ");
                                scanf( "\n%c", &item );
                                add_begin( &startPtr, item ); /* insert item into list */
                                break;
                       
                        case 5:
                                printf( "Enter a character: ");
                                scanf( "\n%c", &item );
                                add_begin( &startPtr, item ); /* insert item into list */
                                break;

return 0;
                                                                }/*end switch*/
                                        }/* end while */
} /* end main */

---