This is a common example of a situation when changing the data structure a little could make the logic a lot simple by unifying the cases that otherwise look different *.
The main issue with the logic is that you have lots of conditions to check:
- Deleting the first node that has other nodes after it
- Deleting the last node that has other nodes preceding it
- Deleting the only node
- Deleting a node in the middle
You can make these four conditions identical to the last one by ensuring that there is always a node on the left and a node on the right of any node. Here is how you can do it:
class LinkedList
{
private:
struct Node
{
int data;
Node *next;
Node *previous;
};
int count;
// The change begins here
Node headTail;
// End of the change
public:
LinkedList() {head = NULL; tail = NULL; count = 0;} //Constructor
void insert(const int );
bool remove(const int );
bool contains(const int );
size_t lenght() {return count;}
};
The head
pointer is headTail
's next
; the tail
pointer is its previous
. Both next and previous point back to itself in an empty list.
This is a little inefficient, because the data
of the headTail
is unused. The list becomes circular, with one node always present. With this node in place, you can safely remove any node in the middle, and update the prior and the next pointers as if they belonged to different objects.
* Here is a link to an excellent reading not directly related to the problem at hand, but very useful to understanding the philosophy of this approach.