Part 1: Singly Linked List As discussed in class, create a singly linked list us
ID: 645501 • Letter: P
Question
Part 1: Singly Linked List
As discussed in class, create a singly linked list using list and node classes/structs. You must create your linked list on the heap (using malloc or new). Your linked list should have the following operations:
1) Front - returns a pointer to the first node of the list
node * front();
2) Back - returns a pointer to the last node of the list
node * back();
3) Insert - inserts an element at the end of the list and returns a pointer to the beginning node
node * insert(int value);
4) Delete - deletes an element from the end of the list.
int remove();
Prompt the user for a number of the command line. Use your linked list to store numbers entered. After each number entered, you should print out the current values in the linked list.
Upon exiting, use you delete functionality to clean up the linked list memory
Part 2: Doubly Linked List
Alter your linked list so it is a doubly linked list
Add the following functionality:
1) searchForward - search for the value starting form the front node
2) searchBackward - search for the value starting from the back node.
Prompt the user to enter a search value, and print the number of steps before the value is found foward and backward.
Do not worry about duplicate values in the list. In this case the number of steps won't equal the size of the list.
Explanation / Answer
#include <iostream>
using namespace std;
struct node{
int num;
node *next;
};
class List{
private:
node *head;
int count;
public:
List(){
head = NULL;
}
void freeUpMemory(node *temp){
if(temp == NULL){
return;
}
else{
freeUpMemory(temp->next);
delete temp;
}
}
~List(){
freeUpMemory(head);
}
node * front(){
return head;
}
node * back(){
if(head == NULL){
return NULL;
}
node *temp = head;
while(temp->next != NULL){
temp = temp->next;
}
return temp;
}
node * insert(int value){
node *temp = new node;
temp->num = value;
temp->next = NULL;
if(head == NULL){
head = temp;
}
else{
node *t = head;
while(t->next != NULL){
t = t->next;
}
t->next = temp;
}
return head;
}
int remove(){
if(head == NULL){
return -1;
}
else{
int n;
if(head->next == NULL){
n = head->num;
head = NULL;
}
else{
node *temp = head;
while(temp->next->next != NULL){
temp = temp->next;
}
n = temp->next->num;
temp->next = NULL;
}
return n;
}
}
void print(){
node *temp = head;
while(temp != NULL){
cout << temp->num << " ";
temp = temp->next;
}
cout << endl;
}
};
int main(){
List l;
int num;
while(true){
cout << "Enter a number(-1 to exit): ";
cin >> num;
if(num == -1){
break;
}
else{
l.insert(num);
l.print();
}
}
cout << "Removed " << l.remove() << endl;
l.print();
cout << "Back element is " << l.back()->num << endl;
cout << "Front Element is " << l.front()->num << endl;
return 0;
}
____________________________________________________________________________________
#include <iostream>
using namespace std;
struct node{
int num;
node *next;
node *prev;
};
class List{
private:
node *head;
int count;
public:
List(){
head = NULL;
}
void freeUpMemory(node *temp){
if(temp == NULL){
return;
}
else{
freeUpMemory(temp->next);
delete temp;
}
}
~List(){
freeUpMemory(head);
}
node * front(){
return head;
}
node * back(){
if(head == NULL){
return NULL;
}
node *temp = head;
while(temp->next != NULL){
temp = temp->next;
}
return temp;
}
node * insert(int value){
node *temp = new node;
temp->num = value;
temp->next = NULL;
temp->prev = NULL;
if(head == NULL){
head = temp;
}
else{
node *t = head;
while(t->next != NULL){
t = t->next;
}
t->next = temp;
temp->prev = t;
}
return head;
}
int remove(){
if(head == NULL){
return -1;
}
else{
int n;
if(head->next == NULL){
n = head->num;
head = NULL;
}
else{
node *temp = head;
while(temp->next->next != NULL){
temp = temp->next;
}
n = temp->next->num;
temp->next = NULL;
}
return n;
}
}
int searchForward(int val){
node *f = front();
int n = 0;
while(f != NULL){
n++;
if(f->num == val){
break;
}
else{
f = f->next;
}
}
return n;
}
int searchBackward(int val){
node *b = back();
int n = 0;
while(b != NULL){
n++;
if(b->num == val){
break;
}
else{
b = b->prev;
}
}
return n;
}
void print(){
node *temp = head;
while(temp != NULL){
cout << temp->num << " ";
temp = temp->next;
}
cout << endl;
}
void printBack(){
node *temp = back();
while(temp != NULL){
cout << temp->num << " ";
temp = temp->prev;
}
cout << endl;
}
};
int main(){
List l;
int num;
while(true){
cout << "Enter a number(-1 to exit): ";
cin >> num;
if(num == -1){
break;
}
else{
l.insert(num);
l.print();
}
}
cout << "Removed " << l.remove() << endl;
l.print();
cout << "Back element is " << l.back()->num << endl;
cout << "Front Element is " << l.front()->num << endl;
cout << "Enter a number to serach backward: ";
cin >> num;
cout << l.searchBackward(num) << " backward steps" << endl;
cout << "Enter a number to serach forward: ";
cin >> num;
cout << l.searchForward(num) << " forward steps" << endl;
return 0;
}