Homework SourseC Goals Build single linked lists using pointers Learn how t
C++
Goals
Build single linked lists using pointers
Learn how to manipulate linked lists
In this lab, you will create simple single linked structures consisting of Node objects. Each node will have a pointer to the next node. You will use a head pointer to keep track of the first node in the linked list, and a tail pointer to keep track of the last node in the linked list. Set both head and tail to NULL when the list is empty.
All of the code manipulating the linked list should be in the main function. For this lab, you will not implement the linked list operations using functions/methods. The idea is to focus on the low-level manipulation of the links that connect the nodes in the list.
1. Create the linked list: store integer values entered by the user in the linked list. Each node in the list should store one value. Use a menu to get user input values. After the user has entered the sequence of values, the program should print the values in order. Think about how to traverse the list in order to print the values. Meanwhile, you need to set the head and tail pointers to point to the first and last node in the list.
2. Get the head or tail node value: print the values of head or tail node in screen. If the list is empty, print a note as “List is empty!!”
3. Delete the head or tail value: ask the user whether to delete the node in the head or tail of the list. When user chooses one, delete that node by manipulate pointers and print the new head/tail node value. If the list is already empty, print a note like “Deleting failed, list is empty!!” Remember to free the memory after deleting.
Finally, give users options to exit the program or do it again.
Example running:
Welcome to my linked list!
Enter a number: 100
Do you want another num(y or n): y
Enter a number: 30
Do you want another num(y or n): y
Enter a number: 50
Do you want another num(y or n): y
Enter a number: 10
Do you want another num(y or n): n
Your linked list is: 100 30 50 10
Do you want to do get head or tail node value (h or t): t
Tail node is: 10
Do you want to delete head or tail node (h or t): h
The new head node is 30!
Do you want to do this again (y or n)? n
Solution
we will create a ListNode class to hold integer item.
Below is the code
/*
* LinkedList.cpp
*
* Created on: 16-Feb-2017
* Author: yourname
*/
#include<iostream>
using namespace std;
class ListNode {
public:
int item;
ListNode *next;
ListNode(int item) {
next = NULL;
this->item = item;
}
ListNode(int item, ListNode *next) {
this->item = item;
this->next = next;
}
};
int main(int argc, const char * argv[]) {
ListNode *head, *tail;
head = tail = NULL;
bool wanna_continue = true;
cout << \"Welcome to my linked list! \ \";
int number;
do {
bool wanna_enter_number = true;
while (wanna_enter_number) {
cout << \"Enter a number: \";
cin >> number;
//insert into list
if (head == NULL) {
head = new ListNode(number);
tail = head;
} else {
ListNode *newNode = new ListNode(number);
tail->next = newNode;
tail = newNode;
}
char flag;
cout << \"Do you want another num(y or n):\";
cin >> flag;
if (flag != \'y\')
wanna_enter_number = false;
}
//print the list
cout << \"Your linked list is: \";
ListNode *it = head;
while (it != NULL) {
cout << it->item << \" \";
it = it->next;
}
cout << endl;
while (1) {
cout << \"Do you want to do get head or tail node value (h or t):\";
char direction;
cin >> direction;
if (direction == \'h\') {
//print head
if (head == NULL)
cout << \"List is empty!!\ \";
else
cout << \"Head node is: \" << head->item;
break;
} else if (direction == \'t\') {
//print tail
if (head == NULL)
cout << \"List is empty!!\ \";
else
cout << \"Tail node is: \" << tail->item;
break;
break;
}
}
cout << endl;
while (1) {
cout
<< \"Do you want to do delete head or tail node value (h or t):\";
char direction;
cin >> direction;
if (direction == \'h\') {
//delete head
if (head == NULL)
cout << \"Deleting failed, list is empty!!\";
else {
head = head->next;
if (head == NULL)
tail = NULL;
}
if (head != NULL) {
cout << \"The new head node is \" << head->item << \"! \";
}
break;
} else if (direction == \'t\') {
//delete tail
if (head == NULL)
cout << \"Deleting failed, list is empty!!\";
else {
if (head->next == NULL) {
delete (head);
head = tail = NULL;
} else {
ListNode *newTail = head;
while (newTail->next->next != NULL) {
newTail = newTail->next;
}
tail = newTail;
newTail = newTail->next;
tail->next = NULL;
delete (newTail);
}
}
if (tail != NULL) {
cout << \"The new tail node is \" << tail->item << \"! \";
}
break;
}
}
cout << endl;
char ch;
cout << \"Do you want to do this again (y or n) ?\";
cin >> ch;
if (ch != \'y\') {
wanna_continue = false;
}
} while (wanna_continue);
return 0;
}
