• 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?
 
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
0
 
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
0
 
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
0
Improve Your Query Performance Tuning

In this FREE six-day email course, you'll learn from Janis Griffin, Database Performance Evangelist. She'll teach 12 steps that you can use to optimize your queries as much as possible and see measurable results in your work. Get started today!

 
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.
0
 
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
0
 
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
0
 
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;
                        
            }


      }


}
0
 
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
0
 
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
0
 
Rmbndr23Author Commented:
yea this is a  C i guess we havnt got to C++ yet
0
 
Rmbndr23Author Commented:
Could you move this to C for my PaulCaswell   Thanks
0
 
Rmbndr23Author Commented:
does anyone see any problem with my delete function? for some reason i can't get it to work properly
0
 
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
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.