Instead of actually reversing the link between nodes, I have traversed the list till the very end and set the last node address as head. I prepared a separate function for printing it in specific order which works well except that its returning garbage value for the last node. Here's the code -
void reverselist(Node * &head){
Node *temp =head;
Node *prevtemp = NULL;
while(temp !=NULL){
prevtemp = temp;
temp = temp->next;
}
head = prevtemp;
}
void printreverse(Node * &head){
Node *temp = head;
while(temp!=NULL){
cout << temp->data << " ";
temp = temp->prev;
}
}
int main() {
Node * node1= new Node(54);
Node *head = node1;
Node *tail =node1;
insertathead(head, tail, 10);
printlist(head);
insertattail(tail, 23);
printlist(head);
insertatanyposition(head, tail,43,2);
printlist(head);
reverselist(head);
printreverse(head);
return 0;
}
CodePudding user response：
The answer is no. This does not work.
I also do not see a double linked list. Looks more like you wanted to implement a singly linked list.
Additionally, I do not see a linked list somewhere in the code. Maybe you mix up "Node" and "Linked List". The "Node" is usually a part of the linked list. So it is contained in the Linked List class. And the whole functionality of the "Node" is usually not exposed to the outside world.
Example with Singly Linked list and reverse iterator in the function main at the bottome:
#include <iostream>
#include <iterator>
#include <initializer_list>
#include <algorithm>
// Very simple implementation of a forward list
template <class T>
class SinglyLinkedList {
// The node
struct Node {
T data{}; // Data. Would normally be a templated argument
Node* next{}; // And the pointer to the next node
Node(const T& i, Node* n = nullptr) : data(i), next(n) {}; // Simple constructor to set a value and next pointer
};
Node* head{}; // This is the start of the list
// It would be advisable to have a tail pointer. We use the more inefficient approach here
Node* getLast() const { Node* n{ head }; while (n and n->next) n = n->next; return n; }
public:
// Constructor / Destructor --------------------------------------------------------------------------------------------------------
~SinglyLinkedList() { clear(); }
// Default constuctor
SinglyLinkedList() {} // Default
// From an initialization list
SinglyLinkedList(const std::initializer_list<T>& il) { clear(); for (const T& i : il) push_back(i); } // From initializer list
// Copy constructor
SinglyLinkedList(const SinglyLinkedList& other) { clear(); for (const T& i : other) push_back(i); }
// Move constructor. Will steal the elements from the other
SinglyLinkedList(SinglyLinkedList&& other) noexcept { head = other.head; other.head = nullptr; }
// Assignment operator
SinglyLinkedList& operator = (const SinglyLinkedList& other) { clear(); for (const T& i : other) push_back(i); }
// Move assignment operator
SinglyLinkedList& operator = (SinglyLinkedList&& other) { head = other.head; other.head = nullptr; }
// Housekeeping --------------------------------------------------------------------------------------------------------------
void clear() { Node* tmp{ head }; while (tmp) { Node* toDelete{ tmp }; tmp = tmp->next; delete toDelete; } head = nullptr; }
int empty() const { return head == nullptr; }
int size() const { int k{}; Node* n{ head }; while (n) { k; n = n->next; } return k; }
// Modify content --------------------------------------------------------------------------------------------------------------
void push_front(const T& i) { Node* n = new Node(i); n->next = head; head = n; };
void push_back(const T& i) { Node* n = new Node(i); Node* l = getLast(); if (l) l->next = n; else head = n; }
void pop_front() { if (head) { Node* tmp = head->next; delete head; head = tmp; } }
void pop_back() { // This is a little bit more difficult in a singly linked list
if (head) {
Node* n{ head }, * previous{};
while (n and n->next) {
previous = n;
n = n->next;
}
delete n;
if (previous)
previous->next = nullptr;
else
head->next = nullptr;
}
}
// Access elements --------------------------------------------------------------------------------
T& front() const { return head ? head->data : 0; };
T back() const { Node* n = getLast(); return n ? n->data : 0; }
// Add iterator properties to class ---------------------------------------------------------------
struct iterator { // Local class for iterator
Node* iter{}; // Iterator is basically a pointer to the node
Node* head{};
// Define alias names necessary for the iterator functionality
using iterator_category = std::bidirectional_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = T;
using pointer = T*;
using reference = T&;
// Constructor
iterator() {}
iterator(Node* n, Node* h) : iter(n), head(h) {}
// Dereferencing
reference operator *() const { return iter->data; }
pointer operator ->() const { return &iter->data; }
// Aithmetic operations
iterator& operator () { if (iter) iter = iter->next; return *this; }
iterator operator (int) { iterator temp{ *this }; * this; return temp; }
iterator operator (const difference_type& n) const { iterator temp{ *this }; difference_type k{ n }; while (k--) temp; return temp; }
iterator& operator =(const difference_type& n) { difference_type k{ n }; while (k--) * this; return *this; };
// Clumsy subtratcion
iterator& operator --() { Node* tmp = head; while (tmp and tmp->next != this->iter) tmp = tmp->next; iter = tmp; return *this; }
// Comparison
bool operator != (const iterator& other) const { return iter != other.iter; }
bool operator == (const iterator& other) const { return iter == other.iter; }
bool operator < (const iterator& other) const { return iter < other.iter; }
bool operator > (const iterator& other) const { return iter > other.iter; }
bool operator <= (const iterator& other) const { return iter <= other.iter; }
bool operator >= (const iterator& other) const { return iter >= other.iter; }
// Difference. Also complicated, because no random access
difference_type operator-(const iterator& other) const {
difference_type result{};
Node* n{ iter };
while (n and n != other.iter) {
result;
n = n->next;
}
return result;
}
};
// Begin and end function to initialize an iterator
iterator begin() const { return iterator(head, head); }
iterator end() const { return iterator(nullptr, head); }
// Functions typcical for forward lists ----------------------------------------------------------------------
// Easy, becuase we can operate form the current iterator and do not need the "previous" element
iterator insertAfter(iterator& pos, const T& i) {
iterator result(nullptr, head);
if (pos.iter and pos.iter->next) {
Node* n = new Node(i, pos.iter->next);
pos.iter->next = n;
result.iter = n;
}
return result;
}
iterator eraseAfter(iterator& pos) {
iterator result(nullptr, head);
if (pos.iter and pos.iter->next) {
Node* tmp = pos.iter->next->next;
delete pos.iter->next;
pos.iter->next = tmp;
result.iter = pos.iter->next;
}
return result;
}
};
// Test/Driver Code
int main() {
// Example for initilizer list
SinglyLinkedList<int> sllbase{ 5,6,7,8,9,10,11,12,13,14,15 };
// Show move constructor
SinglyLinkedList<int> sll(std::move(sllbase));
// Add some values in the front
sll.push_front(4);
sll.push_front(3);
sll.push_front(2);
sll.push_front(1);
// Delete 1st element (Number 1)
sll.pop_front();
// Delete last element
sll.pop_back();
// Use a std::algorithm on our custom linked list. Works because we have an interator
SinglyLinkedList<int>::iterator iter = std::find(sll.begin(), sll.end(), 8);
iter;
--iter;
// Now add an element after 8
iter = sll.insertAfter(iter, 88);
// And delete the 9
iter = sll.eraseAfter(iter);
// Use range based for loop. Works because, we have iterators
for (int i : sll)
std::cout << i << ' ';
// Reverse Output
std::cout << "\n\n";
std::reverse_iterator<SinglyLinkedList<int>::iterator> riter = std::make_reverse_iterator(sll.end());
std::reverse_iterator<SinglyLinkedList<int>::iterator> riterEnd = std::make_reverse_iterator(sll.begin());
for (; riter != riterEnd; riter)
std::cout << *riter << ' ';
std::cout << "\n\n";
return 0;
}
Then, you would add iterator functionality to the linked list class.
And last but not least, there is a wrapper class for reverse iterators. And with that, you can easily implement what you want. Please read here
But for that you need to create a --operator for your iterator. This is difficult for singly linked list and simple for double linked list.
C has already what you need. You can simply use it.
But, if we want to practice a little bit, then check some list implementations in the net and try to implement step by step.
And: Read book. This thing which consists of real paper :-)
CodePudding user response：
If you take the case of a Doubly Linked List, Its answer is Yes you can reverse this list by just making head pointer as the last node.
But, Note that now all the previous pointers are next pointers and all next pointers will be the previous pointers.
See below:
NULL<-1<-->2<-->3<-->4->NULL
↑
Head
Now If you make head to 4, the list will be like this:
NULL<-1<-->2<-->3<-->4->NULL
↑
Head
As seen the list is reversed but, the next pointers become previous and vice versa.
Coming To your Query that You have got a Garbage Value for printreverse function, I did the same code of yours but it works fine!
U can have a look at it below:
#include <bits/stdc .h>
using namespace std;
struct Node
{
struct Node *prev;
int data;
struct Node *next;
Node(int x)
{
data = x;
next = prev = nullptr;
}
Node(int x, Node*p,Node *q)
{
data = x;
next = q;
prev = p;
}
};
void reverselist(Node * &head){
Node *temp =head;
Node *prevtemp = NULL;
while(temp !=NULL){
prevtemp = temp;
temp = temp->next;
}
head = prevtemp;
}
void printlist(Node * &head){
Node *temp = head;
while(temp!=NULL){
cout << temp->data << " ";
temp = temp->next;
}
}
void printreverse(Node * &head){
Node *temp = head;
while(temp!=NULL){
cout << temp->data << " ";
temp = temp->prev;
}
}
int main()
{
Node *node1 = new Node(0);
Node *head = node1;
Node *tail = node1;
Node *temp=node1;
int i=1;
while(i<6){
temp->next= new Node(i ,temp,nullptr);
temp=temp->next;
}
cout<<"List Before Reversal"<<endl;
printlist(head);
reverselist(head);
cout<<endl<<"List After Reversal"<<endl;
printreverse(head);
return 0;
}
Output of above code is:
List Before Reversal 0 1 2 3 4 5
List After Reversal 5 4 3 2 1 0