// Write a function to reverse the first two elements in a // double linked list
ID: 674800 • Letter: #
Question
// Write a function to reverse the first two elements in a
// double linked list
// The function should change pointers
// NO CREDIT will be given for changing the data, i.e. the int data field inside the node
// You MUST match the output given below
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
using std::ostream;
struct node {
int data;
node * p; // FORWARD LINK
node * rp; // REVERSE LINK
};
ostream & operator<<( ostream &, const node *); // Written
void addFront( node * & start, int); // Written
void cleanUp( node *); // Written
void reverse(node * &); // WRITTEN BY STUDENT
void main()
{
node * a = NULL;
cout << "EMPTY LIST CASE: ";
cout << "BEFORE a is " << a << endl;
reverse(a);
cout << "AFTER a is " << a << endl;
cleanUp(a);
a = NULL;
addFront(a,10);
cout << " ONE ELEMENT LIST CASE: ";
cout << "BEFORE a is " << a << endl;
reverse(a);
cout << "AFTER a is " << a << endl;
cleanUp(a);
a = NULL;
addFront(a,30);
addFront(a,20);
cout << " TWO ELEMENT LIST CASE: ";
cout << "BEFORE a is " << a << endl;
reverse(a);
cout << "AFTER a is " << a << endl;
cleanUp(a);
a = NULL;
addFront(a,60);
addFront(a,50);
addFront(a,40);
cout << " THREE ELEMENT LIST CASE: ";
cout << "BEFORE a is " << a << endl;
reverse(a);
cout << "AFTER a is " << a << endl;
cleanUp(a);
a = NULL;
addFront(a,400);
addFront(a,300);
addFront(a,200);
addFront(a,100);
cout << " FOUR ELEMENT LIST CASE: ";
cout << "BEFORE a is " << a << endl;
reverse(a);
cout << "AFTER a is " << a << endl;
cleanUp(a);
}
void reverse(node * & s) // Student Writes this Function
{
}
void addFront( node * & start, int x)
{
node * t = new node;
t->data = x;
if( start != NULL )
{
t->p = start;
t->rp = NULL;
start->rp = t;
}
else
{
t->p = NULL;
t->rp = NULL;
}
start = t;
}
void cleanUp( node * s)
{
node * walker, * prev;
walker = s;
while ( walker != NULL )
{
prev = walker;
walker = walker->p;
delete prev;
}
}
ostream & operator<<(ostream & w, const node * s)
{
const node * walker = s;
const node * trailer = walker;
w << "Forward Print " << endl;
if ( s==NULL)
{
w << "EMPTY LIST";
}
else
{
while ( walker != NULL )
{
w << walker->data << ' ';
trailer = walker;
walker = walker->p;
}
}
w << endl << "Reverse Print " << endl;
if ( trailer == NULL )
{
w << "EMPTY LIST";
return w;
}
while ( trailer != NULL)
{
w << trailer->data << ' ';
trailer = trailer->rp;
}
return w;
}
/*
EMPTY LIST CASE:
BEFORE a is
Forward Print
EMPTY LIST
Reverse Print
EMPTY LIST
AFTER a is
Forward Print
EMPTY LIST
Reverse Print
EMPTY LIST
ONE ELEMENT LIST CASE:
BEFORE a is
Forward Print
10
Reverse Print
10
AFTER a is
Forward Print
10
Reverse Print
10
TWO ELEMENT LIST CASE:
BEFORE a is
Forward Print
20 30
Reverse Print
30 20
AFTER a is
Forward Print
30 20
Reverse Print
20 30
THREE ELEMENT LIST CASE:
BEFORE a is
Forward Print
40 50 60
Reverse Print
60 50 40
AFTER a is
Forward Print
50 40 60
Reverse Print
60 40 50
FOUR ELEMENT LIST CASE:
BEFORE a is
Forward Print
100 200 300 400
Reverse Print
400 300 200 100
AFTER a is
Forward Print
200 100 300 400
Reverse Print
400 300 100 200
*/
Explanation / Answer
/* Program to reverse a doubly linked list */
#include <stdio.h>
#include <stdlib.h>
/* a node of the doubly linked list */
struct node
{
int data;
struct node *next;
struct node *prev;
};
/* Function to reverse a Doubly Linked List */
void reverse(struct node **head_ref)
{
struct node *temp = NULL;
struct node *current = *head_ref;
/* swap next and prev for all nodes of
doubly linked list */
while (current != NULL)
{
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
/* Before changing head, check for the cases like empty
list and list with only one node */
if(temp != NULL )
*head_ref = temp->prev;
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginging of the Doubly Linked List */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* since we are adding at the begining,
prev is always NULL */
new_node->prev = NULL;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* change prev of head node to new node */
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked lsit */
void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;
/* Let us create a sorted linked list to test the functions
Created linked list will be 10->8->4->2 */
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);
printf(" Original Linked list ");
printList(head);
/* Reverse doubly linked list */
reverse(&head);
printf(" Reversed Linked list ");
printList(head);
getchar();
}
/* Program to reverse a doubly linked list */
#include <stdio.h>
#include <stdlib.h>
/* a node of the doubly linked list */
struct node
{
int data;
struct node *next;
struct node *prev;
};
/* Function to reverse a Doubly Linked List */
void reverse(struct node **head_ref)
{
struct node *temp = NULL;
struct node *current = *head_ref;
/* swap next and prev for all nodes of
doubly linked list */
while (current != NULL)
{
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
/* Before changing head, check for the cases like empty
list and list with only one node */
if(temp != NULL )
*head_ref = temp->prev;
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginging of the Doubly Linked List */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* since we are adding at the begining,
prev is always NULL */
new_node->prev = NULL;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* change prev of head node to new node */
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked lsit */
void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;
/* Let us create a sorted linked list to test the functions
Created linked list will be 10->8->4->2 */
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);
printf(" Original Linked list ");
printList(head);
/* Reverse doubly linked list */
reverse(&head);
printf(" Reversed Linked list ");
printList(head);
getchar();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.