I'm a second year CS major currently studying Data Structures, I wanted to implemented a Linked List with whatever knowledge I have at my disposal without referring much to any books or references, just a pen and paper and what I know in C++, I would be glad if someone takes a look at the code and finds potential issues, tips, logic problems and whatnot.
template <class DataType>
class dList
{
private:
// The Node Structure.
struct Node
{
DataType data;
Node *next;
Node *prev;
};
// The 'head' And 'tail' Pointers.
Node *head, *tail;
// Miscellaneous Variables.
int itemsInList; // The Number Of Items In The List.
public:
// The Default Constructor.
dList()
{
head = nullptr;
tail = nullptr;
itemsInList = 0;
}
// Insertion Operations.
void insertEnd(DataType itemToInsert);
void insertBeginning(DataType itemToInsert);
int insertAfterNth(DataType itemToInsert, int afterNth);
int insertAfterSpecific(DataType itemToInsert, DataType afterData);
// Deletion Operations.
int deleteBeginning();
int deleteEnd();
int deleteNthNode(int nthNode);
int deleteSpecificNode(DataType nodeToDelete);
// Display Operations.
int displayF();
int displayB();
// Useful Utility Operations.
int numberOfItems();
bool isEmpty();
DataType searchFor(DataType searchTerm);
};
// The Insert To The End Function.
template <class DataType>
void dList<DataType>::insertEnd(DataType itemToInsert)
{
// Creating The New Node With The Item We Want To Insert First.
Node *newNode = new Node;
newNode->data = itemToInsert;
newNode->next = nullptr; // Since We Are Adding To The End, It'll Point Nowhere.
// Checking If The List Is Full.
if (head == nullptr)
{
newNode->prev = nullptr;
head = tail = newNode;
}
// Otherwise (If The List Is Not Empty).
else
{
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}
itemsInList++; // Increase The Items In The List.
}
// The Insert To The Beginning Function.
template <class DataType>
void dList<DataType>::insertBeginning(DataType itemToInsert)
{
Node *newNode = new Node;
newNode->data = itemToInsert;
if (head == nullptr)
{
newNode->next = newNode->prev = nullptr; // Set Both Of 'newNode->next' And 'newNode->prev' To 'nullptr'
head = tail = newNode;
}
else
{
newNode->prev = nullptr;
head->prev = newNode;
newNode->next = head;
head = newNode;
}
itemsInList++;
}
// The Insert After Nth Node Function.
template <class DataType>
int dList<DataType>::insertAfterNth(DataType itemToInsert, int afterNth)
{
Node *newNode = new Node;
newNode->data = itemToInsert;
Node *temp1 = head;
int counter = 1;
while (temp1 != nullptr)
{
if (counter == afterNth) break;
if (temp1->next == nullptr) return 1;
counter++;
temp1 = temp1->next;
}
// Special Case For Tail, If Inserting After The Last Node.
if (temp1 == tail)
{
newNode->next = nullptr;
temp1->next = newNode;
newNode->prev = temp1;
tail = newNode;
}
// All Other Cases.
else
{
Node *temp2 = temp1->next;
temp1->next = newNode;
newNode->prev = temp1;
temp2->prev = newNode;
newNode->next = temp2;
}
itemsInList++;
return 0;
}
// The Insert After Specific Data Function.
template <class DataType>
int dList<DataType>::insertAfterSpecific(DataType itemToInsert, DataType afterData)
{
Node *newNode = new Node;
newNode->data = itemToInsert;
Node *temp = head;
while (temp->data != afterData)
{
if (temp->next == nullptr) return 1; // Indicating That The Node Data To Insert After Was Not Found.
temp = temp->next;
}
if (temp == tail)
{
newNode->next = nullptr;
temp->next = newNode;
newNode->prev = temp;
tail = newNode;
}
else
{
Node *temp2 = temp->next;
temp->next = newNode;
newNode->prev = temp;
temp->prev = newNode;
newNode->next = temp2;
}
itemsInList++;
return 0;
}
// The Delete Beginning Function.
template <class DataType>
int dList<DataType>::deleteBeginning()
{
// Check If The List Is Empty.
if (head == nullptr) return 1; // Indicating That The Operation Failed, Since List Is Empty.
// Otherwise.
if (tail == head)
{
delete head;
head = tail = nullptr;
}
else
{
Node *temp = head;
head = head->next;
head->prev = nullptr;
delete temp;
}
return 0;
}
// The Delete End Function.
template <class DataType>
int dList<DataType>::deleteEnd()
{
if (head == nullptr) return 1;
if (tail == head)
{
delete head;
head = tail = nullptr;
}
else
{
Node *temp = tail;
tail = tail->prev;
tail->next = nullptr;
delete temp;
}
return 0;
}
// The Delete Nth Node Function.
template <class DataType>
int dList<DataType>::deleteNthNode(int nthNode)
{
if (head == nullptr) return 1;
int counter = 1;
Node *temp = head;
while (temp != nullptr)
{
if (counter == nthNode) break;
if (temp->next == nullptr) return 2;
counter++;
temp = temp->next;
}
if (head == tail)
{
delete head;
head = tail = nullptr;
}
else
{
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
delete temp;
}
return 0;
}
// The Delete Specific Node Data Function.
template <class DataType>
int dList<DataType>::deleteSpecificNode(DataType nodeToDelete)
{
if (head == nullptr) return 1;
Node *temp = head;
while (temp != nullptr)
{
if (temp->data == nodeToDelete) break;
if (temp->next == nullptr) return 2;
temp = temp->next;
}
if (head == tail)
{
delete head;
head = tail = nullptr;
}
else
{
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
delete temp;
}
return 0;
}
// The Display Forward Function.
template <class DataType>
int dList<DataType>::displayF()
{
// Check Whether The List Is Empty.
if (head == nullptr) return 1; // Indicating That The List Is Empty.
// Otherwise (If List Is Not Empty).
Node *temp = head;
cout << "\n\n\n" << "\t" << "| ";
while (temp != nullptr)
{
cout << temp->data << " | ";
temp = temp->next;
}
cout << "\n\n\n";
return 0; // Indicating That The List Was Displayed Successfully.
}
// The Display Backward Function.
template <class DataType>
int dList<DataType>::displayB()
{
if (head == nullptr) return 1;
Node *temp = tail;
cout << "\n\n\n" << "\t" << "| ";
while (temp != nullptr)
{
cout << temp->data << " | ";
temp = temp->prev;
}
cout << "\n\n\n";
return 0;
}
// The Number Of Items Inside The List Function.
template <class DataType>
int dList<DataType>::numberOfItems()
{
return (itemsInList);
}
// The Is Empty Function.
template <class DataType>
bool dList<DataType>::isEmpty()
{
if (head == nullptr) return true;
return false;
}
// The Search For A Specific Node Function.
template <class DataType>
DataType dList<DataType>::searchFor(DataType searchTerm)
{
if (head == nullptr) return -1; // Indicating That The List Is Empty.
Node *temp = head;
int counter = 1;
while (temp != nullptr)
{
if (temp->data == searchTerm) break;
if (temp->next == nullptr) return -2; // Indicating That The Item Was Not Found In The List.
counter++;
temp = temp->next;
}
return counter; // Returns The Node Number Of The Searched Item If It's Found.
}
Thanks in advance