Description
Doubly linked list is a more complicated singly linked list. In doubly linked list we store two addresses for our next node and previous node (shown in figure below).
Implement the doubly linked list data structure by completing two existed classes Node and DoublyLinkedList.
Node
Public Variables:
- data(string) string data store in a node.
- next(Node*) pointer points to the next node.
- prev(Node*) pointer points to the previos node.
Constructors:
- Node(string str) – Should initalize the data (data) store in a node to str, and initialize next and prev pointer to nullptr.
DoublyLinkedList:
Public Variables:
- head(Node*) should point to the first element of the doubly linked list.
- tail(Node*) should point to the last element of the doubly linked list.
Constructors:
- The default constructor – Should initialize head and tail to nullptr.
Public Methods:
- void Insert(string str) – Should create a Node(str), and insert it into the doubly linked list, in ascending order of the string’s length.
For example:
Insert ccc // null <- ccc ->null
Insert bb // null <- bb <-> ccc -> null
Insert a // null <- a <-> bb <-> ccc -> null
Insert xx // null <- a <-> bb <-> xx <-> ccc -> null
- string StringInOrder() – Visit all the nodes in the doubly linked list from head to tail. Add up the string in every nodes’ data and return. If the doubly linked list is empty return empty string “”.
- string StringInReverse() – Visit all the nodes in the doubly linked list from tail to head. Add up the reverse string in every nodes’ data and return. If the doubly linked list is empty return empty string “”.
For example:
Insert ab // null <- ab ->null
Insert bc // null <- ab <-> bc -> null
Insert cd // null <- ab <-> bc <-> cd -> null
str // return string: abbccd
strrev // return string: dccbba
/* You Don’t Need to Implement Below Two Methods */
- bool IsPalindrome() – Return true if the doubly linked list is not empty and StringInOrder() == StringInReverse(); otherwise return false.
- bool IsEmpty() – Return true if the doubly linked list is empty (head == nullptr && tail == nullptr); otherwise, return false.
Input
There are four kinds of input command.
insert str – Call Insert(str).
ispalindrome – Call IsPalindrome().
str– Call StringInOrder().
strrev– Call StringInReverse().
Output
No need to handle output. Check main.cpp for more details.