Added the ReverseList function to reverse the singly linked list operation.
Fixed a bug that specially handles the case of a single node when reversing the linked list.
Fixed several bugs, specially handling the case of an empty linked list.
Try using the template class with data structures.
There will definitely still be omissions, corrections are welcome.
Without further ado, here is the code.
ps: nullptr is a C++11 feature, please pay attention when using it.
Node Definition#
template <class T> class LNode {
private:
LNode* next; // Pointer
T Data; // Data
public:
friend class List;
LNode(T data = 0) {
Data = data;
next = nullptr;
}
void showdata() { cout << Data << endl; }
};
Linked List Operation Class Definition#
template <class T> class List {
private:
LNode<T>* head; // Head node does not store elements but allocates space
public:
friend class LNode<T>;
List();
~List();
LNode<T>* FindKth(int K); // Find the Kth element in the linked list by index
// Returns a pointer to the node if found, returns nullptr if not found
LNode<T>* Find(T data); // Find element data by value
// Returns a pointer to the node if found, returns nullptr if not found
void
Delete(int pos =
1); // Delete operation (delete the node at position pos in the linked list) defaults to deleting the first element
void Insert(T data, int pos = 1); // Defaults to head insertion, inserts data at the pos-th element
void PrintList(); // Display the linked list
int getLength(); // Get the length of the linked list
};
Constructor and Destructor#
The head node does not hold data, all operations start from head->next.
// Constructor allocates space for head, does not hold data
template <class T> List<T>::List() {
head = new LNode<T>;
head->next = nullptr;
}
// Destructor releases space
template <class T> List<T>::~List() {
while (head->next) {
Delete(1);
}
delete head;
}
Operation Class Implementation#
(1) Find by Index#
Find the Kth element in the linked list, returns a pointer to the node if found, returns nullptr if not found or if the position is invalid.
template <class T> LNode<T>* List<T>::FindKth(int K) {
LNode<T>* p = head->next; // First element
if (!p) {
cout << "Element not found, this List is empty!" << endl;
return nullptr;
}
int pos = 1;
while (p->next && pos < K) {
p = p->next;
pos++;
}
if (pos == K)
return p; // Return pointer if the Kth element is found
else { // Otherwise, the position is invalid, return nullptr
cout << "The location is illegal." << endl;
return nullptr;
}
}
(2) Find by Value#
Find element data, returns a pointer to the node if found, returns nullptr if not found.
template <class T> LNode<T>* List<T>::Find(T data) {
LNode<T>* p = head->next;
if (!p) {
cout << "Element not found, this List is empty!" << endl;
return nullptr;
}
while (p->next && p->Data != data)
p = p->next;
if (p->Data != data) { // Reached the end but the element is still not data
cout << "Element not found!" << endl;
return nullptr;
}
else
return p;
}
(3) Delete Operation#
Delete the node at position pos in the linked list, defaults to deleting the first element.
template <class T>
void List<T>::Delete(int pos) { // Delete operation (delete the node at position i in the linked list)
LNode<T>* p = head->next;
if (!p) {
cout << "Delete failed, this List is empty!" << endl;
return;
}
if (pos == 1) { // If the first node is to be deleted
head->next = p->next;
if (p)
delete p;
return;
}
LNode<T>* s = FindKth(pos - 1); // Find the (pos-1)th element
if (!s) {
cout << "The " << pos-1 << " node does not exist!" << endl;
return;
}
p = s->next;
if (!p) {
cout << "The " << pos << " node does not exist!" << endl;
return;
} else {
s->next = p->next; // s points to the (pos+1)th node
delete p; // Delete p from the linked list
cout << "Successfully deleted!" << endl;
}
}
(4) Insert Operation#
Defaults to head insertion, inserts data at the pos-th element.
template <class T> void List<T>::Insert(T data, int pos) {
LNode<T>* p = new LNode<T>();// Allocate space for the new node p
p->Data = data;
if (pos == 1) { // Insert at the first position
p->next = head->next;
head->next = p;
cout << "Successfully Inserted!" << endl;
return;
}
LNode<T>* s = FindKth(pos - 1); // Find the (pos-1)th element
if (!s) {
cout << "The location is illegal, insertion failed!" << endl;
return;
}
p->next = s->next;
s->next = p;
cout << "Successfully Inserted!" << endl;
}
(5) Get the Length of the Linked List#
template <class T> int List<T>::getLength() {
LNode<T>* p = head; // p points to the head node of the list
int cnt = 0;
while (p->next) {
p = p->next;
cnt++;
}
return cnt;
}
(6) Display the Linked List#
template <class T> void List<T>::PrintList() {
LNode<T>* p = head; // p points to the head node of the list
if (!head->next)
cout << "This List is empty!" << endl;
int cnt = 0;
while (p->next) {
p = p->next;
cnt++;
cout << "The " << cnt << "th Data is:";
p->showdata();
}
cout << "The list has " << cnt << " elements in total." << endl;
}
(7) Reverse the Linked List#
General idea:
Code:
template <class T> void List<T>::ReverseList() {
LNode<T>* now = head->next; // now points to the first node of the list
if (!now) {
cout << "This List is empty!" << endl;
return;
}
LNode<T>* tmp = now->next; // Points to the node after now
while (tmp) { // Move tmp to the back of the head node
now->next = tmp->next;
tmp->next = head->next;
head->next = tmp;
tmp = now->next;
}
}
Complete Code#
#include <Windows.h>
#include <iostream>
#include <string>
using namespace std;
class Student {
public:
string id; // Student ID
string name; // Student Name
int age; // Age
bool operator==(const Student& s) { return id == s.id; }
bool operator!=(const Student& s) { return id != s.id; }
bool operator<(const Student& s) { return id < s.id; }
Student() : name("Xiao Ming"), age(18) {}
friend istream& operator>>(istream& is, Student& s) {
is >> s.id >> s.name >> s.age;
getchar();
return is;
}
friend ostream& operator<<(ostream& os, const Student& s) {
os << "Student ID:" << s.id << " Name:" << s.name << " Age:" << s.age
<< endl;
return os;
}
};
template <class T> class List;
// Node Definition
template <class T> class LNode {
private:
LNode* next; // Pointer
T Data; // Data
public:
friend class List<T>;
LNode() { next = nullptr; }
void showdata() { cout << Data << endl; }
};
// Linked List Operation Class Definition
template <class T> class List {
private:
LNode<T>* head; // Head node does not store elements but allocates space
public:
friend class LNode<T>;
List();
~List();
LNode<T>* FindKth(int K); // Find the Kth element in the linked list by index
// Returns a pointer to the node if found, returns nullptr if not found
LNode<T>* Find(T data); // Find element data by value
// Returns a pointer to the node if found, returns nullptr if not found
void
Delete(int pos =
1); // Delete operation (delete the node at position pos in the linked list) defaults to deleting the first element
void Insert(T data, int pos = 1); // Defaults to head insertion, inserts data at the pos-th element
void PrintList(); // Display the linked list
int getLength(); // Get the length of the linked list
void ReverseList(); // Reverse the linked list
};
// Linked List Operation Class Implementation
// Constructor allocates space for head, does not hold data
template <class T> List<T>::List() {
head = new LNode<T>;
head->next = nullptr;
}
// Destructor releases space
template <class T> List<T>::~List() {
while (head->next) {
Delete(1);
}
delete head;
}
// (1) Find by Index: Find the Kth element in the linked list
// Returns a pointer to the node if found, returns nullptr if not found
template <class T> LNode<T>* List<T>::FindKth(int K) {
LNode<T>* p = head->next; // First element
if (!p) {
cout << "Element not found, this List is empty!" << endl;
return nullptr;
}
int pos = 1;
while (p->next && pos < K) {
p = p->next;
pos++;
}
if (pos == K)
return p; // Return pointer if the Kth element is found
else { // Otherwise, the position is invalid, return nullptr
cout << "The location is illegal." << endl;
return nullptr;
}
}
// (2) Find by Value: Find element data
// Returns a pointer to the node if found, returns nullptr if not found
template <class T> LNode<T>* List<T>::Find(T data) {
LNode<T>* p = head->next;
if (!p) {
cout << "Element not found, this List is empty!" << endl;
return nullptr;
}
while (p->next && p->Data != data)
p = p->next;
if (p->Data != data) { // Reached the end but the element is still not data
cout << "Element not found!" << endl;
return nullptr;
}
else
return p;
}
// (3) Delete Operation: Delete the node at position pos in the linked list, defaults to deleting the first element
template <class T>
void List<T>::Delete(int pos) { // Delete operation (delete the node at position i in the linked list)
LNode<T>* p = head->next;
if (!p) {
cout << "Delete failed, this List is empty!" << endl;
return;
}
if (pos == 1) { // If the first node is to be deleted
head->next = p->next;
if (p)
delete p;
return;
}
LNode<T>* s = FindKth(pos - 1); // Find the (pos-1)th element
if (!s) {
cout << "The " << pos-1 << " node does not exist!" << endl;
return;
}
p = s->next;
if (!p) {
cout << "The " << pos << " node does not exist!" << endl;
return;
} else {
s->next = p->next; // s points to the (pos+1)th node
delete p; // Delete p from the linked list
cout << "Successfully deleted!" << endl;
}
}
// (4) Insert Operation: Defaults to head insertion, inserts data at the pos-th element
template <class T> void List<T>::Insert(T data, int pos) {
LNode<T>* p = new LNode<T>();// Allocate space for the new node p
p->Data = data;
if (pos == 1) { // Insert at the first position
p->next = head->next;
head->next = p;
cout << "Successfully Inserted!" << endl;
return;
}
LNode<T>* s = FindKth(pos - 1); // Find the (pos-1)th element
if (!s) {
cout << "The location is illegal, insertion failed!" << endl;
return;
}
p->next = s->next;
s->next = p;
cout << "Successfully Inserted!" << endl;
}
// (5) Get the Length of the Linked List
template <class T> int List<T>::getLength() {
LNode<T>* p = head; // p points to the head node of the list
int cnt = 0;
while (p->next) {
p = p->next;
cnt++;
}
return cnt;
}
// (6) Display the Linked List
template <class T> void List<T>::PrintList() {
LNode<T>* p = head; // p points to the head node of the list
if (!head->next)
cout << "This List is empty!" << endl;
int cnt = 0;
while (p->next) {
p = p->next;
cnt++;
cout << "The " << cnt << "th Data is:";
p->showdata();
}
cout << "The list has " << cnt << " elements in total." << endl;
}
// (7) Reverse the Linked List
template <class T> void List<T>::ReverseList() {
LNode<T>* now = head->next; // now points to the first node of the list
if (!now) {
cout << "This List is empty!" << endl;
return;
}
LNode<T>* tmp = now->next; // Points to the node after now
while (tmp) { // Move tmp to the back of the head node
now->next = tmp->next;
tmp->next = head->next;
head->next = tmp;
tmp = now->next;
}
}
// Functions called in the main function
template <class T> void input(List<T>& Head) {
T data;
cout << "Please enter the linked list elements (separated by spaces, press enter to finish):";
cin >> data;
Head.Insert(data);
}
template <class T> void remove(List<T>& Head) {
int i;
cout << "Please enter i (delete the i-th element of the linked list):";
cin >> i;
getchar();
Head.Delete(i);
}
template <class T> void findKth(List<T>& Head) {
int K;
LNode<T>* s = nullptr;
cout << "(Find by index) Please enter K, to find the K-th element in the linked list:";
cin >> K;
getchar();
s = Head.FindKth(K);
if (!s)
cout << "Not found!" << endl;
else {
cout << "Search successful! The element is:";
s->showdata();
}
}
template <class T> void findData(List<T>& Head) {
string data;
cout << "Please enter the student ID to search:";
cin >> data;
Student t;
t.id = data;
getchar();
LNode<T>* s = nullptr;
s = Head.Find(t);
if (!s)
cout << "Element not found!" << endl;
else {
cout << "Search successful! The element is in the linked list.";
}
}
template <class T> void insert(List<T>& Head) {
int i;
T data;
cout << "Insert a student's information at the i-th position in the linked list, enter i:";
cin >> i;
cout << "Enter the student's information, ID Name Age separated by spaces, press enter to finish:";
cin >> data;
Head.Insert(data, i);
}
template <class T> inline void getlength(List<T>& Head) {
cout << "The length of the linked list is:" << Head.getLength() << endl;
}
template <class T> void printList(List<T>& Head) {
cout << "---------------------- List P --------------------" << endl;
Head.PrintList();
}
template <class T> void reverseList(List<T>& Head) {
T data;
cout << "---------------------- List P --------------------" << endl;
Head.PrintList();
cout << endl;
Head.ReverseList();
cout << "------------- After reverse, List P ---------------" << endl;
Head.PrintList();
}
int main() {
List<Student> P;
int choice;
cout << "1 Add a student's information" << endl;
cout << "2 Delete the i-th element of the linked list" << endl;
cout << "3 Find the K-th element in the linked list by index" << endl;
cout << "4 Find element data by value" << endl;
cout << "5 Insert element data at the i-th position in the linked list" << endl;
cout << "6 Get the length of the linked list" << endl;
cout << "7 Print all student information" << endl;
cout << "8 Reverse the linked list" << endl;
cout << "9 Exit" << endl;
while (1) {
cout << "Menu selection (1-6):";
cin >> choice;
getchar();
switch (choice) {
case 1: input(P); break;
case 2: remove(P); break;
case 3: findKth(P); break;
case 4: findData(P); break;
case 5: insert(P); break;
case 6: getlength(P); break;
case 7: printList(P); break;
case 8: reverseList(P); break;
case 9: break;
default: cout << "Input error, please re-enter";
}
if (choice == 9)
exit(0);
cout << "Press Enter to continue…" << endl;
getchar();
};
return 0;
}