The next step up from a sinlgy linked list is the double linked list. It is basically the same. It just stores another pointer for the previous node. This makes some operations way easier and some a little harder. But most of the time it is a trade of worth taking.

A common thing people do is to make double linked list(in short dlist) circular. To mark the head and the tail they use a special node called the sentinel. This makes some operations easier, but for now we will concentrate on the basic dlist.

Your task is to change the singly linked list to a double linked list.