• C

Have to write a program using doubly linked list

Write a program to create, manipulate, and print a doubly linked list of numbers.

    * A doubly linked list is build from elements that have a pointer to the next element of the list and another pointer to the previous element of the list. The next pointer of the last element of the list is defined to be the NULL pointer. The previous pointer of the first element of the list is defined to be the NULL pointer. A doubly linked list can be traversed forward or backward using a single pointer to keep track of the current position in the list.
    * Write a function called "AddAfter" that adds a number to a doubly linked list after the current list element. Input to this function should be a pointer to the current element of the doubly linked list and the number to be added to the list. The funtion should return a pointer to the new element.
    * Write a function called "AddBefore" that adds a number to a doubly linked list before the current list element. Input to this function should be a pointer to the current element of the doubly linked list and the number to be added to the list. The funtion should return a pointer to the new element.
    * Write a function called "DeleteElement" that deletes the number from a doubly linked list at the current element position. Input to this function should be a pointer to the current element of the doubly linked list. The funtion should return the NULL pointer if the list is empty. The funtion should return a pointer to the list element before the deleted element if there is one. Otherwise, the funtion should return a pointer the list element after the deleted element. Make sure to free up the memory allocated for the deleted element.
    * Write a function called "PrintForward" that will print the numerical values stored in a doubly linked list from start value to the last. The input to this function should be a pointer to one of the elements of the list and not necessarily the first element of the list.
    * Write a function called "PrintBackward" that will print the numerical values stored in a doubly linked list from the last element to the first. The input to this function should be a pointer to one of the elements of the list and not necessarily the last element of the list.

Your program should read in a sequence of positive numbers from the command prompt until the user enters a -1. Use the AddAfter and AddBefore functions to add each number to the doubly linked list in decending order (i.e., largest to smallest). Use a single pointer called current_p to point to the current element of the doubly linked list to navigate through the list.

The program should print out the list in ascending order and then in descending order. Next, the program should prompt the user to delete one of the numbers from the list and delete that element from the list. The program should print out the new list in ascending order and then terminate.


Not really sure how to get this program accomplished... anyone have any input on these functions that need to be written?
AddBefore
AddAfter
DeleteElemnt
PrintForward
PrintBackward

This program is pretty tough and due in a couple days
Rmbndr23Asked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

PaulCaswellCommented:
Hi Rmbndr23,

Your best option is to post what you've done so far. That way we can help you change it so it stays all your work. I we post solutions to homework questions, not only do we get into trouble as it's against the rules but you dont learn much from it.

Paul
Rmbndr23Author Commented:
#include <stdio.h>

#include <stdlib.h>



typedef struct listnode {

      char data;

      struct node *nextPtr;

      struct node *prevPtr;

} List;



int main() {

      List *currPtr;

      int counter = 0;

      currPtr = NULL;





this is all ive got so far... i may try working more on it tonight and post up some more of what ive got
jkrCommented:
>>this is all ive got so far...

If you want a list of numbers, the 'data' member in your node struct should be a numeric type.

>>i may try working more on it tonight and post up some more of what ive got

No, it's not that you 'may try' - you have to.
Simplify Active Directory Administration

Administration of Active Directory does not have to be hard.  Too often what should be a simple task is made more difficult than it needs to be.The solution?  Hyena from SystemTools Software.  With ease-of-use as well as powerful importing and bulk updating capabilities.

Rmbndr23Author Commented:
yeah, i know im not saying that im not going to work on it buddy, "may" refers to if i have time to work on it tonight or tomorrow

thanks ill change that to type int
PaulCaswellCommented:
Hi Rmbndr23,

What you've got is good, apart from using 'int' as jkr correctly points out.

To work out what to do, I normally use models. Nowadays the models are all in my head but you may find doing it with actual objects useful.

Let me think of something you can use ... I've seen several good animations of linked lists but I just cant find one right now. The essence of the problem is breaking each link and making it in its new position without letting go of the whole structure.

I'll have another look for a good demo of the process.

Paul
PaulCaswellCommented:
Hi Rmbndr23,

Finally found a helpful link! Its not animated but it covers what you need:

http://www.cs.usask.ca/resources/tutorials/csconcepts/2000_1/Tutorial/3.2.1insertion.html

Paul

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Rmbndr23Author Commented:
Here is what i've got now... for some reason its not deleting elements after i input -1  and i still need to work on my add after function so that it will take numbers that are less that the largest number


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


typedef struct list {
      int value;
      struct list *nextPtr;
      struct list *prevPtr;
} List;


void addBefore(List *cPtr, int key);
void addAfter();
void deleteElement(List *cPtr, int key);
void printForward();
void printBackward();



int main() {
      int i = 0;
      int key = 0;
      List *currentPtr;
      currentPtr = (List *) malloc(sizeof(List));
      currentPtr->nextPtr = NULL;
      currentPtr->prevPtr = NULL;
      currentPtr->value = 0;


      
      while( key != -1 ) {

            scanf("%d", &key);
            
            if (currentPtr == NULL) {
                  printf("List is empty");

            }

            else if (currentPtr->value < key) {
                  
                  addBefore(currentPtr, key);
                  currentPtr->value = key;
                  
                  printForward(currentPtr);
                  
            }

            else if (currentPtr->value > key) {
            //      addAfter(currentPtr);


            }


            else {
                  printf("Error!");

            }

      }
      printf("choose element to delete");
      scanf("%d", &key);
      deleteElement(currentPtr, key);
      printForward(currentPtr);

      return '\0';

}


void printForward(List *cPtr) {

      
      if (cPtr == NULL) {
            printf("The list is empty!");
      }

      else {
            printf("The list is:\n\n");

            while(cPtr != NULL) {
                  
                  printf("%d --> ", cPtr->value);
                  cPtr = cPtr->prevPtr;
                                    
            }
            
            printf("NULL\n\n");

      }



}

void addBefore(List *cPtr, int key) {

      
      List *newPtr = NULL;

      newPtr = (List *) malloc(sizeof(List));  //create space for newPtr


      if (newPtr != NULL){
            
            newPtr->value = key;  //set value equal to key
            newPtr->nextPtr = cPtr; //nextPtr equals address of struct cPtr
            newPtr->prevPtr = cPtr->prevPtr; //prevPtr of newPtr = prevPtr of cPtr
            
            cPtr->prevPtr = newPtr;
      }


      return;
}


void deleteElement(List *cPtr, int key) {

      List *tempPtr = NULL;

      while ( &cPtr->value != NULL) {


            //Move to right
            if (cPtr->value < key) {
                  cPtr = cPtr->nextPtr;

            }

            //Move to left
            else  {
                  cPtr = cPtr->prevPtr;
                        
            }


      }


}
itsmeandnobodyelseCommented:
>>>> What you've got is good,

I don't know whether the linked list should be written in C or C++. As you posted in the C++ TA I assume it is C++. Then, you might consider to change your C notation to C++ and use new/delete rather than malloc/free and iostreams for output rather than using printf:

#include <iostream>
using namespace std;

struct ListNode
{
     int value;
     ListNode* nextPtr;
     ListNode* prevPtr;
};

...

int main()
{
     ...
     ListNode* currentPtr = new ListNode;
     ...

    while( true )
    {
          cout << "Enter data ==>";
          cin >> key;
          if (key == -1)
               break;
          ...
          if (currentPtr == NULL)
          {
              cout << "List is empty" << endl;
              ...
          }
          ...

}

Regards, Alex
PaulCaswellCommented:
If this is a C project I could move it there for you if you like. Just post here.

There are loads of people there who like helping with homework.

Paul
Rmbndr23Author Commented:
yea this is a  C i guess we havnt got to C++ yet
Rmbndr23Author Commented:
Could you move this to C for my PaulCaswell   Thanks
Rmbndr23Author Commented:
does anyone see any problem with my delete function? for some reason i can't get it to work properly
PaulCaswellCommented:
Hi Rmbndr23,

Here's an 'annotated' version of what you last posted. Absorb my comments (marked //***) and see what you can do. Come back to ask if you need some more pointers.

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


typedef struct list {
     int value;
     //*** I usually use 'next' and 'prev' but stick with this now you've done it.
     struct list *nextPtr;
     struct list *prevPtr;
} List;

//*** Put a one-line comment before each of these to briefly describe the function.
// EG:
// Add a new node before cPtr with.
void addBefore(List *cPtr, int key);
//*** The question says you should use 'AddAfter'! Usually, global functions (like these) have the first letter uppercase.
void addAfter();
void deleteElement(List *cPtr, int key);
void printForward();
void printBackward();



int main() {
     int i = 0;
     int key = 0;
     List *currentPtr;
     //*** This makes the list contain an item at the start! Better to just start it contaning NULL.
     currentPtr = (List *) malloc(sizeof(List));
     currentPtr->nextPtr = NULL;
     currentPtr->prevPtr = NULL;
     currentPtr->value = 0;


     while( key != -1 ) {

          scanf("%d", &key);
         
          if (currentPtr == NULL) {
              //*** Should be able to handle this situation too. Add a new item to an empty list!
              //*** The trick is not to pass a 'List*' to the function but to use a 'List**'! Then you can pass &currentPtr or &currentPtr->next etc.
               printf("List is empty");

          }

          else if (currentPtr->value < key) {
               
               addBefore(currentPtr, key);
               //*** I'd put this into the AddBefore function because its going to create the new one anyway and fill in the pointers, it might as well fill in the value too.
               currentPtr->value = key;
               
               printForward(currentPtr);
               
          }

          else if (currentPtr->value > key) {
          //     addAfter(currentPtr);


          }


          else {
               printf("Error!");

          }

     }
     printf("choose element to delete");
     scanf("%d", &key);
     deleteElement(currentPtr, key);
     printForward(currentPtr);

     return '\0';

}


void printForward(List *cPtr) {

     
     if (cPtr == NULL) {
          printf("The list is empty!");
     }

     else {
          printf("The list is:\n\n");

          while(cPtr != NULL) {
               
               printf("%d --> ", cPtr->value);
               //*** Surely, printing forward should be nextPtr here.
               cPtr = cPtr->prevPtr;
                             
          }
         
          printf("NULL\n\n");

     }



}

void addBefore(List *cPtr, int key) {

     
     List *newPtr = NULL;

     newPtr = (List *) malloc(sizeof(List));  //create space for newPtr


     if (newPtr != NULL){
          //*** Oh! You ARE filling it in!
          newPtr->value = key;  //set value equal to key
          newPtr->nextPtr = cPtr; //nextPtr equals address of struct cPtr
          newPtr->prevPtr = cPtr->prevPtr; //prevPtr of newPtr = prevPtr of cPtr
          //*** Good so-far but not enough! There are two links you must change! The next's 'prev' and the prev's 'next'.
          cPtr->prevPtr = newPtr;
     }


    //*** Not necessary.
     return;
}


void deleteElement(List *cPtr, int key) {

     List *tempPtr = NULL;

     //*** The value is an INT! Dont you mean 'next'? Or cPtr itself?
     while ( &cPtr->value != NULL) {


          //Move to right
          if (cPtr->value < key) {
               cPtr = cPtr->nextPtr;

          }

          //Move to left
          else  {
               cPtr = cPtr->prevPtr;
                   
          }


     }

 //*** OK! Now you've found it (not saying you have :-) got to let you do some of the work), delete it! But get your 'Add' working first'

}


Paul
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.