Introduction:
This C++ code demonstrates the implementation of various operations on a doubly linked list. A doubly linked list is a data structure where each node contains a data element and two pointers, one pointing to the previous node and another pointing to the next node. This allows for efficient traversal in both directions.
#include
using namespace std;
struct node2
{
int data2;
struct node2 *previous;
struct node2 *next2;
};
int main()
{
node2 *head2;
node2 *last2;
node2 *temp2;
last2=0;
int choice;
do
{
cout<<"Enter data in Doubly node:"<<endl; temp2=new node2(); cin>>temp2->data2;
if(last2==0)
{
temp2->next2=0;
temp2->previous=0;
last2=head2=temp2;
}
else
{
temp2->next2=0;
temp2->previous=last2;
last2->next2=temp2;
last2=temp2;
}
cout<<"\nDo you want to create a new node (1=yes,0=NO): "; cin>>choice;
}while(choice==1);
cout<<"Printing from start"<<endl;
temp2=head2;
while(temp2!=0)
{
cout<data2<<" "; temp2=temp2->next2;
}
cout<<"\n Printing from end"<<endl;
temp2=last2;
while(temp2!=0)
{
cout<data2<<" "; temp2=temp2->previous;
}
/******************************************/
do
{
cout<<"Enter data"<<endl; temp2=new node2(); cin>>temp2->data2;
if(last2==0)
{
temp2->next2=0;
temp2->previous=0;
last2=head2=temp2;
}
else
{
temp2->next2=head2;
temp2->previous=0;
head2->previous=temp2;
head2=temp2;
}
cout<<"\nDo you want to create a new node (1=yes,0=NO): "; cin>>choice;
}while(choice==1);
cout<<"\n Printing from start"<<endl;
temp2=head2;
while(temp2!=0)
{
cout<data2<<" "; temp2=temp2->next2;
}
return 0;
}
Steps:
Structure Definition:
The code begins with defining a structure named node2 that represents each node in the doubly linked list. It contains an integer data2, a pointer previous to the previous node, and a pointer next2 to the next node.
Main Function:
The main function is where the operations on the doubly linked list are implemented.
Initialization:
Three pointers head2, last2, and temp2 are initialized. head2 points to the first node, last2 points to the last node, and temp2 is used to create new nodes.
Input and Creation of Nodes:
The code enters a loop to create nodes based on user input. Inside the loop:
A new node is dynamically allocated and user input is taken for its data2.
If it’s the first node (i.e., last2 is 0), the node’s pointers are set to 0 (null), and both head2 and last2 point to this node.
For subsequent nodes:
The node’s next 2 points to 0.
The node’s previous points to the last 2.
The next2 pointer of the last2 node is updated to point to the new node.
last2 is updated to the new node.
Continue Creation:
The user is prompted whether they want to create another node. If the choice is 1 (yes), the loop continues; otherwise, it exits.
Printing Nodes (Forward):
After creating nodes, the code prints the data of nodes starting from head2 and moving forward using the next2 pointers.
Printing Nodes (Reverse):
Then, the code prints the data of nodes starting from last2 and moving backward using the previous pointers.
Second Operation (Insert at Beginning):
The code performs a similar operation again, but new nodes are inserted at the beginning of the doubly linked list this time.
Printing Nodes Again:
Finally, the code prints the data of nodes again, this time starting from the updated head2 after performing the insertions at the beginning.
Conclusion:
This code demonstrates the creation and manipulation of a doubly linked list using two different methods of insertion: at the end and the beginning. It showcases the traversal of the list in both forward and reverse directions.
FAQs:
What is a doubly linked list?
A doubly linked list is a data structure where each node contains a data element and two pointers, one pointing to the previous node and another pointing to the next node. This allows efficient traversal in both directions.
What is the purpose of the previous pointer in the node2 structure?
The previous pointer in the node2 structure points to the previous node in the linked list, enabling bidirectional traversal.
How are nodes inserted at the end and the beginning of the linked list?
Nodes are inserted at the end by updating the next2 pointer of the last node, and at the beginning by updating the previous pointer of the head node and reassigning the head2 pointer.
What are the benefits of a doubly linked list over a singly linked list?
Unlike singly linked lists, doubly linked lists allow traversal in both directions (forward and backward) with the help of the previous pointers. This can be useful in certain applications, such as implementing undo/redo functionality.
Why is dynamic memory allocation used for creating nodes?
Dynamic memory allocation (using new or malloc) is used to allocate memory for nodes at runtime, allowing the creation of a flexible number of nodes without knowing the exact size in advance.