Modify the linked list example in the book so that it is a doubly linked list. P
ID: 3696472 • Letter: M
Question
Modify the linked list example in the book so that it is a doubly linked list. Prove that your program works properly by implementing a print backwards function. The book's code (6th edition) is at the end of the example output. You can just cut and paste it to get started. NOTE: this is a C program – if you compile it as C++ you cannot use delete as that is a reserved keyword. Also, since C++ is strongly typed, you must cast pointer allocations to the correct type.
You must understand the singly linked list code before you can start the doubly linked list code.
Your code must store in order.
If you have problems with improperly assigned pointers
You can redefine Node as:
struct listNode {
char data;
struct listNode *nextPtr;
struct listNode *prevPtr;
};
NOTE: I will be testing your code using the following sequence in this exact order –
Insert b a z k g m
Delete a z k g b m
This tests the 4 basic cases. Insert/delete on an empty list, insert/delete at the beginning, insert/delete at the end, insert/delete at the end.
Example Program Session:
Enter your choice:
1 to insert an element into the list.
2 to delete an element from the list.
3 to end.
? 1
Enter a character: a
The list is:
a --> NULL
The list in reverse is:
a --> NULL
? 1
Enter a character: z
The list is:
a --> z --> NULL
The list in reverse is:
z --> a --> NULL
? 1
Enter a character: n
The list is:
a --> n --> z --> NULL
The list in reverse is:
z --> n --> a --> NULL
? 1
Enter a character: d
The list is:
a --> d --> n --> z --> NULL
The list in reverse is:
z --> n --> d --> a --> NULL
? 2
Enter character to be deleted: x
x not found.
? 2
Enter character to be deleted: n
n deleted.
The list is:
a --> d --> z --> NULL
The list in reverse is:
z --> d --> a --> NULL
? 2
Enter character to be deleted: a
a deleted.
The list is:
d --> z --> NULL
The list in reverse is:
z --> d --> NULL
? 2
Enter character to be deleted: z
z deleted.
The list is:
d --> NULL
The list in reverse is:
d --> NULL
? 2
Enter character to be deleted: d
d deleted.
List is empty.
? 1
Enter a character: s
The list is:
s --> NULL
The list in reverse is:
s --> NULL
? 1
Enter a character: t
The list is:
s --> t --> NULL
The list in reverse is:
t --> s --> NULL
? 3
End of run.
Press any key to continue . . .
Here is the code from the book which you can cut and paste:
/* Fig. 12.3: fig12_03.c
Operating and maintaining a list */
#include <stdio.h>
#include <stdlib.h>
/* self-referential structure */
struct listNode {
char data; /* each listNode contains a character */
struct listNode *nextPtr; /* pointer to next node*/
}; /* end structure listNode */
typedef struct listNode ListNode; /* synonym for struct listNode */
typedef ListNode *ListNodePtr; /* synonym for ListNode* */
/* prototypes */
void insert( 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; /* initially there are no nodes */
int choice; /* user's choice */
char item; /* char entered by user */
instructions(); /* display the menu */
printf( "? " );
scanf( "%d", &choice );
/* loop while user does not choose 3 */
while ( choice != 3 ) {
switch ( choice ) {
case 1:
printf( "Enter a character: " );
scanf( " %c", &item );
insert( &startPtr, item ); /* insert item in list */
printList( startPtr );
break;
case 2:
/* if list is not empty */
if ( !isEmpty( startPtr ) ) {
printf( "Enter character to be deleted: " );
scanf( " %c", &item );
/* if character is found, remove it */
if ( delete( &startPtr, item ) ) { /* remove item */
printf( "%c deleted. ", item );
printList( startPtr );
} /* end if */
else {
printf( "%c not found. ", item );
} /* end else */
} /* end if */
else {
printf( "List is empty. " );
} /* end else */
break;
default:
printf( "Invalid choice. " );
instructions();
break;
} /* end switch */
printf( "? " );
scanf( "%d", &choice );
} /* end while */
printf( "End of run. " );
return 0; /* indicates successful termination */
} /* end main */
/* display program instructions to user */
void instructions( void )
{
printf( "Enter your choice: "
" 1 to insert an element into the list. "
" 2 to delete an element from the list. "
" 3 to end. " );
} /* end function instructions */
/* Insert a new value into the list in sorted order */
void insert( ListNodePtr *sPtr, char value )
{
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; /* walk to ... */
currentPtr = currentPtr->nextPtr; /* ... next node */
} /* 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. ", value );
} /* end else */
} /* end function insert */
/* Delete a list element */
char delete( ListNodePtr *sPtr, char value )
{
ListNodePtr previousPtr; /* pointer to previous node in list */
ListNodePtr currentPtr; /* pointer to current node in list */
ListNodePtr tempPtr; /* temporary node pointer */
/* delete first node */
if ( value == ( *sPtr )->data ) {
tempPtr = *sPtr; /* hold onto node being removed */
*sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
free( tempPtr ); /* free the de-threaded node */
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; /* walk to ... */
currentPtr = currentPtr->nextPtr; /* ... next node */
} /* end while */
/* delete node at currentPtr */
if ( currentPtr != NULL ) {
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
free( tempPtr );
return value;
} /* end if */
} /* end else */
return '';
} /* end function delete */
/* Return 1 if the list is empty, 0 otherwise */
int isEmpty( ListNodePtr sPtr )
{
return sPtr == NULL;
} /* end function isEmpty */
/* Print the list */
void printList( ListNodePtr currentPtr )
{
/* if list is empty */
if ( currentPtr == NULL ) {
printf( "List is empty. " );
} /* end if */
else {
printf( "The list is: " );
/* while not the end of the list */
while ( currentPtr != NULL ) {
printf( "%c --> ", currentPtr->data );
currentPtr = currentPtr->nextPtr;
} /* end while */
printf( "NULL " );
} /* end else */
} /* end function printList */
Explanation / Answer
Solution:
This C-Program impelents the Dobly linked List & its Operations
Program:
// C Program to implement a Doubly Linked List & its Operations
#include <stdio.h>
#include <stdlib.h>
struct node
{
struct node *prev;
int n;
struct node *next;
}*h,*temp,*temp1,*temp2,*temp4;
void insert1();
void insert2();
void insert3();
void traversebeg();
void traverseend(int);
void sort();
void search();
void update();
void delete();
int count = 0;
void main()
{
int ch;
h = NULL;
temp = temp1 = NULL;
printf(" 1 - Insert at beginning");
printf(" 2 - Insert at end");
printf(" 3 - Insert at position i");
printf(" 4 - Delete at i");
printf(" 5 - Display from beginning");
printf(" 6 - Display from end");
printf(" 7 - Search for element");
printf(" 8 - Sort the list");
printf(" 9 - Update an element");
printf(" 10 - Exit");
while (1)
{
printf(" Enter choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
insert1();
break;
case 2:
insert2();
break;
case 3:
insert3();
break;
case 4:
delete();
break;
case 5:
traversebeg();
break;
case 6:
temp2 = h;
if (temp2 == NULL)
printf(" Error : List empty to display ");
else
{
printf(" Reverse order of linked list is : ");
traverseend(temp2->n);
}
break;
case 7:
search();
break;
case 8:
sort();
break;
case 9:
update();
break;
case 10:
exit(0);
default:
printf(" Wrong choice menu");
}
}
}
/* TO create an empty node */
void create()
{
int data;
temp =(struct node *)malloc(1*sizeof(struct node));
temp->prev = NULL;
temp->next = NULL;
printf(" Enter value to node : ");
scanf("%d", &data);
temp->n = data;
count++;
}
/* TO insert at beginning */
void insert1()
{
if (h == NULL)
{
create();
h = temp;
temp1 = h;
}
else
{
create();
temp->next = h;
h->prev = temp;
h = temp;
}
}
/* To insert at end */
void insert2()
{
if (h == NULL)
{
create();
h = temp;
temp1 = h;
}
else
{
create();
temp1->next = temp;
temp->prev = temp1;
temp1 = temp;
}
}
/* To insert at any position */
void insert3()
{
int pos, i = 2;
printf(" Enter position to be inserted : ");
scanf("%d", &pos);
temp2 = h;
if ((pos < 1) || (pos >= count + 1))
{
printf(" Position out of range to insert");
return;
}
if ((h == NULL) && (pos != 1))
{
printf(" Empty list cannot insert other than 1st position");
return;
}
if ((h == NULL) && (pos == 1))
{
create();
h = temp;
temp1 = h;
return;
}
else
{
while (i < pos)
{
temp2 = temp2->next;
i++;
}
create();
temp->prev = temp2;
temp->next = temp2->next;
temp2->next->prev = temp;
temp2->next = temp;
}
}
/* To delete an element */
void delete()
{
int i = 1, pos;
printf(" Enter position to be deleted : ");
scanf("%d", &pos);
temp2 = h;
if ((pos < 1) || (pos >= count + 1))
{
printf(" Error : Position out of range to delete");
return;
}
if (h == NULL)
{
printf(" Error : Empty list no elements to delete");
return;
}
else
{
while (i < pos)
{
temp2 = temp2->next;
i++;
}
if (i == 1)
{
if (temp2->next == NULL)
{
printf("Node deleted from list");
free(temp2);
temp2 = h = NULL;
return;
}
}
if (temp2->next == NULL)
{
temp2->prev->next = NULL;
free(temp2);
printf("Node deleted from list");
return;
}
temp2->next->prev = temp2->prev;
if (i != 1)
temp2->prev->next = temp2->next; /* Might not need this statement if i == 1 check */
if (i == 1)
h = temp2->next;
printf(" Node deleted");
free(temp2);
}
count--;
}
/* Traverse from beginning */
void traversebeg()
{
temp2 = h;
if (temp2 == NULL)
{
printf("List empty to display ");
return;
}
printf(" Linked list elements from begining : ");
while (temp2->next != NULL)
{
printf(" %d ", temp2->n);
temp2 = temp2->next;
}
printf(" %d ", temp2->n);
}
/* To traverse from end recursively */
void traverseend(int i)
{
if (temp2 != NULL)
{
i = temp2->n;
temp2 = temp2->next;
traverseend(i);
printf(" %d ", i);
}
}
/* To search for an element in the list */
void search()
{
int data, count = 0;
temp2 = h;
if (temp2 == NULL)
{
printf(" Error : List empty to search for data");
return;
}
printf(" Enter value to search : ");
scanf("%d", &data);
while (temp2 != NULL)
{
if (temp2->n == data)
{
printf(" Data found in %d position",count + 1);
return;
}
else
temp2 = temp2->next;
count++;
}
printf(" Error : %d not found in list", data);
}
/* To update a node value in the list */
void update()
{
int data, data1;
printf(" Enter node data to be updated : ");
scanf("%d", &data);
printf(" Enter new data : ");
scanf("%d", &data1);
temp2 = h;
if (temp2 == NULL)
{
printf(" Error : List empty no node to update");
return;
}
while (temp2 != NULL)
{
if (temp2->n == data)
{
temp2->n = data1;
traversebeg();
return;
}
else
temp2 = temp2->next;
}
printf(" Error : %d not found in list to update", data);
}
/* To sort the linked list */
void sort()
{
int i, j, x;
temp2 = h;
temp4 = h;
if (temp2 == NULL)
{
printf(" List empty to sort");
return;
}
for (temp2 = h; temp2 != NULL; temp2 = temp2->next)
{
for (temp4 = temp2->next; temp4 != NULL; temp4 = temp4->next)
{
if (temp2->n > temp4->n)
{
x = temp2->n;
temp2->n = temp4->n;
temp4->n = x;
}
}
}
traversebeg();
}
Output:
1 - Insert at beginning
2 - Insert at end
3 - Insert at position i
4 - Delete at i
5 - Display from beginning
6 - Display from end
7 - Search for element
8 - Sort the list
9 - Update an element
10 - Exit
Enter choice : 1
Enter value to node : 10
Enter choice : 2
Enter value to node : 50
Enter choice : 4
Enter position to be deleted : 1
Node deleted
Enter choice : 1
Enter value to node : 34
Enter choice : 3
Enter position to be inserted : 2
Enter value to node : 13
Enter choice : 4
Enter position to be deleted : 4
Error : Position out of range to delete
Enter choice : 1
Enter value to node : 15
Enter choice : 1
Enter value to node : 67
Enter choice : 3
Enter position to be inserted : 2
Enter value to node : 34
Enter choice : 4
Enter position to be deleted : 3
Node deleted
Enter choice : 7
Enter value to search : 15
Error : 15 not found in list
Enter choice : 8
Linked list elements from begining : 13 34 34 50 67
Enter choice : 9
Enter node data to be updated : 45
Enter new data : 89
Error : 45 not found in list to update
Enter choice : 9
Enter node data to be updated : 50
Enter new data : 90
Enter choice : 5
Linked list elements from begining : 13 34 34 90 67
Enter choice : 6
Reverse order of linked list is : 67 90 34 34 13
Enter choice : 7
Enter value to search : 90
Data found in 4 position
Enter choice : 8
Linked list elements from begining : 13 34 34 67 90
Enter choice : 7
Enter value to search : 90
Data found in 5 position
Enter choice : 9
Enter node data to be updated : 34
Enter new data : 56
Linked list elements from begining : 13 56 34 67 90
Enter choice : 10
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.