C++

Forum

 
reverse a doubly linked list

Jul 20, 2020 at 7:01am
gongong (80)
Hello,

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
  #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:

1
2
3
4
5
6
7
8
9
10
 
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
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;
}
Last edited on Jul 20, 2020 at 7:46am
Jul 20, 2020 at 7:25am
TomCPP (32)
It is hard to find out the problem having only part of your code, especially without implementation of append .
Jul 20, 2020 at 7:34am
gongong (80)
@TomCPP thanks for your reply.

please find the entirety of the code here: https://repl.it/@bondat/hw14
Jul 20, 2020 at 7:51am
zapshe (1858)
1
2
3
4
5
6
7
8
9
10
 
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.
Jul 20, 2020 at 8:04am
TomCPP (32)
This code ( lack of delete node )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
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.
Jul 20, 2020 at 11:55am
dhayden (5798)
1
2
3
4
5
6
 
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.


Jul 20, 2020 at 5:22pm
jonnin (11383)
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.
Last edited on Jul 20, 2020 at 5:25pm
Jul 20, 2020 at 7:22pm
salem c (3689)
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.
Jul 20, 2020 at 9:50pm
jonnin (11383)
sure, but roughly 5% or less of posted homework problems make any kind of sense.
Last edited on Jul 20, 2020 at 9:50pm
Topic archived. No new replies allowed.