reverse a doubly linked list

[gongong]

Hello,

I have the following templated class and struct.
I only need to define the reverseList(), and then I'm done with this homework.

  #define nullptr NULL

template <typename T>
struct Node
{
    T data;
    Node<T> *next;
    Node<T> *prev;
    Node(const T &element) : data(element), next(nullptr), prev(nullptr) {}
};
template <typename T>
class DoublyLinkedList
{
private:
    Node<T> *head;
    Node<T> *tail;

public:
    // Constructors
    DoublyLinkedList();
    DoublyLinkedList(const DoublyLinkedList &);
    DoublyLinkedList &operator=(const DoublyLinkedList &); // assignment operator
    ~DoublyLinkedList();                                   // destructor
    // Getters / Setters
    bool empty();

    void append(const T &);
    void insertAfter(Node<T> *, const T &);
    void remove(Node<T> *);
    void reverseList() const;
    void clear();
    void print();
};

Here's my attempt:

template <typename T>
void DoublyLinkedList<T>::reverseList() const{
    Node<T> *current;
    current = tail;
    while(current != nullptr){
        cout << current->data << " ";
        current = current->prev;
    }
    cout << endl;
}

OUTPUT:

list 2: 1 2 3 4 5 
list 2: 0 5 4 3 2 1 0 

i don't get why there's zero going in both ends...
is it bc the while loop nullptr :O?

EDIT:
this one definition is provided by the professor, but i don't know how to use it in main

template <typename T>
void DoublyLinkedList<T>::insertAfter(Node<T> *curNode, const T &newData)
{
    if (curNode == tail)
    {
        // Can't insert after dummy tail
        return;
    }
    // Construct new node
    Node<T> *newNode = new Node<T>(newData);
    Node<T> *sucNode = curNode->next;
    newNode->next = sucNode;
    newNode->prev = curNode;
    curNode->next = newNode;
    sucNode->prev = newNode;
}

[TomCPP]

It is hard to find out the problem having only part of your code, especially without implementation of append .

[gongong]

@TomCPP thanks for your reply.

please find the entirety of the code here: https://repl.it/@bondat/hw14

[zapshe]

template <typename T>
void DoublyLinkedList < T > ::reverseList() const {
	Node < T > * current;
	current = tail->prev;
	while (current->prev != nullptr) {
		cout << current->data << " ";
		current = current->prev;
	}
	cout << endl;
}

This solves the issue. My guess is that your implementation has an off by 1 issue somewhere giving you two extra nodes at the ends.

[TomCPP]

This code ( lack of delete node )

template <typename T>
  void DoublyLinkedList < T > ::remove(Node < T > * curNode) {
    if (empty())
      throw std::length_error("empty list");
    if (curNode == head || curNode == tail) {
      // Dummy nodes cannot be removed
      return;
    }
    Node < T > * sucNode = curNode->next;
    Node < T > * predNode = curNode->prev;
    // Successor node is never null
    sucNode->prev = predNode;
    // Predecessor node is never null
    predNode->next = sucNode;
  }

will inevitably lead to the huge memory leak.

[dhayden]

DoublyLinkedList < T > ::DoublyLinkedList() {
    head = new Node < T > (T()); // create dummy nodes
    tail = new Node < T > (T());
    head->next = tail; // have them point to each other
    tail->prev = head;
  }

Your list has dummy nodes at the head and tail. You need to account for these when reversing the list.

Your reverseList() function doesn't actually reverse the list, it just prints it in reverse order. I suspect that you're supposed to actually reverse the list.

remove() leaks the node removed.

[jonnin]

to truly reverse it you need to iterate the whole list to swap head, tail, and each node's prev/next. alternately you can put a boolean 'reversed' in place and use that in various places to swap the direction in-place. The flag is faster (its just one boolean toggle) but some routines (not all) will have extra clutter to decide which direction to go (mostly, the print for user routine(s) need this, everything else is pretty much ok to treat it from original direction ignoring the flag?). You would need to flip anything else that is exposed to the user, like if you had a gethead / gettail those need to be aware of reverse flag too. Append of course.

[salem c]

I thought the whole point of a double linked list was that you didn't have to physically reverse anything.

If you want reverse, you just start at the tail and follow the prev pointers.

[jonnin]

sure, but roughly 5% or less of posted homework problems make any kind of sense.