?
Solved

Have to write a program using doubly linked list

Posted on 2006-03-22
15
Medium Priority
?
664 Views
Last Modified: 2010-05-18
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
0
Comment
Question by:Rmbndr23
13 Comments
 
LVL 16

Expert Comment

by:PaulCaswell
ID: 16260863
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
 

Author Comment

by:Rmbndr23
ID: 16260961
#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
 
LVL 86

Expert Comment

by:jkr
ID: 16260998
>>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
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 

Author Comment

by:Rmbndr23
ID: 16261020
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
 
LVL 16

Expert Comment

by:PaulCaswell
ID: 16261471
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
 
LVL 16

Accepted Solution

by:
PaulCaswell earned 1000 total points
ID: 16261598
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
 

Author Comment

by:Rmbndr23
ID: 16263315
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
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 16266427
>>>> 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
 
LVL 16

Expert Comment

by:PaulCaswell
ID: 16267336
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
 

Author Comment

by:Rmbndr23
ID: 16271483
yea this is a  C i guess we havnt got to C++ yet
0
 

Author Comment

by:Rmbndr23
ID: 16272068
Could you move this to C for my PaulCaswell   Thanks
0
 

Author Comment

by:Rmbndr23
ID: 16273847
does anyone see any problem with my delete function? for some reason i can't get it to work properly
0
 
LVL 16

Assisted Solution

by:PaulCaswell
PaulCaswell earned 1000 total points
ID: 16273901
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

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
Suggested Courses

840 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question