We help IT Professionals succeed at work.

# Have to write a program using doubly linked list

on
Medium Priority
698 Views
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?
DeleteElemnt
PrintForward
PrintBackward

This program is pretty tough and due in a couple days
Comment
Watch Question

## View Solutions Only

Commented:
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

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
CERTIFIED EXPERT
Top Expert 2012

Commented:
>>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.

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

Commented:
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
Commented:
Hi Rmbndr23,

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

Paul

Not the solution you were looking for? Getting a personalized solution is easy.

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 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) {

currentPtr->value = key;

printForward(currentPtr);

}

else if (currentPtr->value > key) {

}

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;

}

}

}

Commented:
>>>> 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

Commented:
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

Commented:
yea this is a  C i guess we havnt got to C++ yet

Commented:
Could you move this to C for my PaulCaswell   Thanks

Commented:
does anyone see any problem with my delete function? for some reason i can't get it to work properly
Commented:
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.
//*** The question says you should use 'AddAfter'! Usually, global functions (like these) have the first letter uppercase.
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) {

//*** 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) {

}

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
##### Thanks for using Experts Exchange.

• View three pieces of content (articles, solutions, posts, and videos)
• Ask the experts questions (counted toward content limit)
• Customize your dashboard and profile