Description
Doubly linked list is a more complicated singly linked list. The difference is, in singly linked list, we only store an address for our next node.
But, 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
- Node* Find(string str) – Return the address of the first node found in order which data is equal to str. If can’t find any, return nullptr.
- void Delete(string str) – Delete the first node found in order which data is equal to str. If can’t find any, do nothing.
hint: use Find().
/* You Don’t Need to Implement Below Three Methods */
- void TraversalInOrder() – Print all the node’s data stored in doubly linked list in order. If the list is empty print ”/* empty */”.
- void TraversalInReverse() – Print all the node’s data stored in doubly linked list in reverse order. If the list is empty print ”/* empty */”.
- bool IsEmpty() – Return true if the doubly linked list is empty (head == nullptr && tail == nullptr); otherwise, return false.
Input
There are five kinds of input command.
insert str – Call Insert(str).
delete str – Call Delete(str).
find str – Call Find(str).
print – Call TraversalInOrder().
reverse – Call TraversalInReverse().
Output
No need to handle output. Check main.cpp for more details.