CSCI 2010 Lab11 Link-Lists
Lab 11A Linked-Lists
Preparation
//LinkedList.cpp
#include <cstdlib>
#include "LinkedList.h"
using namespace std;
//---------------------------------------------------
//List Element Members
//---------------------------------------------------
ListElement::ListElement(int d, ListElement * n)
{
datum=d;
next=n;
}
int ListElement::getDatum () const
{
return datum;
}
ListElement const* ListElement::getNext () const
{
return next;
}
//---------------------------------------------------
//LinkedList Members
//---------------------------------------------------
LinkedList::LinkedList ()
{
head=NULL;
}
void LinkedList::insertItem(int item)
{
ListElement *currPtr = head;
ListElement *prevPtr = NULL;
ListElement *newNodePtr;
//points to a new node
while(currPtr != NULL && item >
currPtr->datum)
{
prevPtr = currPtr;
currPtr = currPtr->next;
}
newNodePtr = new ListElement(item, currPtr);
if (prevPtr == NULL) // insert at the
beginning
head=newNodePtr;
else
prevPtr->next =
newNodePtr;
}
void LinkedList::makeList()
{
int InValue;
ListElement *currPtr;
ListElement *newNodePtr;
cout << "Enter values for a linked list, one
per line." << endl
<< "Enter 999 to end the
list." << endl;
cin >> InValue;
//Adding elements to end so that "next" will be
NULL
newNodePtr=new ListElement(InValue, NULL);
head=newNodePtr; //assign head to the first Node
currPtr=head;
cin >> InValue;
while ( InValue != 999)
{
newNodePtr=new ListElement(InValue,
NULL);
currPtr->next=newNodePtr; //link the new
node to list
currPtr=newNodePtr;
//move the currPtr so it is at end of list
cin >> InValue;
}
}
void LinkedList::appendItem (int item)
{
//REPLACE THE LINE BELOW WITH YOUR OWN CODE
cout << "You must implement this function"
<<endl;
}
void LinkedList::deleteItem (int item)
{
//REPLACE THE LINE BELOW WITH YOUR OWN CODE
cout << "You must implement this function"
<<endl;
}
void LinkedList::printList ()
{
//REPLACE THE LINE BELOW WITH YOUR OWN CODE
cout << "You must implement this function"
<<endl;
}
// LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <cstdlib>
#include <iostream>
using namespace std;
class LinkedList; // needed for friend line below
class ListElement
{
private:
int datum;
ListElement* next;
public:
ListElement (int, ListElement*);
int getDatum () const;
ListElement const* getNext () const;
friend class LinkedList; // gives LinkedList access
to datum and next
};
class LinkedList
{
private:
ListElement* head;
public:
LinkedList ();
void insertItem (int);
void makeList ();
void appendItem (int);
void deleteItem (int);
void printList ();
};
#endif
//main.cpp
#include<iostream>
#include"LinkedList.h"
#include <string>
using namespace std;
int readInt(string);
int main()
{
char choice;
int item;
LinkedList a;
cout << "This program demonstrates the linked
list. " << endl;
cout << "Initially, you will be asked to create
the list." << endl;
cout << "You will be later prompted to
manipulate the list." <<endl << endl;
a.makeList();
choice='b';
while(choice != 'q')
{
cout <<
"*******************************************************" <<
endl;
cout<<"i: Insert (Insert an
element and keep the list ordered)\n";
cout<<"a: Append (Append an
element to the end of the list)\n";
cout<<"d: Delete (Delete a
node with the given value)\n";
cout<<"p: Print (Print the
content of the current list)\n";
cout<<"q: Quit
(Quit the program)\n";
cout <<
"*******************************************************" <<
endl << endl;
cout<<"\n Please
enter your choice here:";
cin>>choice;
switch(choice)
{
case 'i':
item=readInt("to
insert:");
a.insertItem(item);
break;
case 'a':
item=readInt("to append to
the end:");
a.appendItem(item);
break;
case 'd':
item=readInt("to
delete:");
a.deleteItem(item);
break;
case 'p':
cout << "The content of
the current ordered list is: "<<endl;
a.printList();
break;
case 'q':
break;
default:
cout<<"\n Invalid
choice. Please try again.\n";
break;
}
}
cout<<"\n Bye\n";
return 0;
}
int readInt(string descr)
{
int item;
cout << "\n Please enter an integer
value " << descr;
cin >> item;
while (item < 0)
{
cout << "\n Please try
again:";
cin >> item;
}
return item;
}
The purpose of the program is to demonstrate operations on a simple singly linked list.
Exercise 1
Use each line only once:
Note what changes from one picture to the next. This represents the sequence of operations.
Fill in answer. |
|
Fill in answer. |
|
Fill in answer. |
|
Fill in answer. |
|
Fill in answer. |
|
Fill in answer. |
Exercise 2
Now you should be ready to start adding code to that program.
Try deleting the first, last and middle node. Also try to remove something that is not in the list (an appropriate message should be printed).
When you are happy with the results, script the following test run.
Test Run
(Paste your .h and .cpp files and a screen capture of the program output here – upload this document to lab11A.)
Hope this helps you. Thank you.
Exercise-1
According to the diagrams
Exercise-2
LinkedList.cpp file
//LinkedList.cpp
#include <cstdlib>
#include "LinkedList.h"
using namespace std;
//---------------------------------------------------
//List Element Members
//---------------------------------------------------
ListElement::ListElement(int d, ListElement * n)
{
datum=d;
next=n;
}
int ListElement::getDatum () const
{
return datum;
}
ListElement const* ListElement::getNext () const
{
return next;
}
//---------------------------------------------------
//LinkedList Members
//---------------------------------------------------
LinkedList::LinkedList ()
{
head=NULL;
}
void LinkedList::insertItem(int item)
{
ListElement *currPtr = head;
ListElement *prevPtr = NULL;
ListElement *newNodePtr; //points to a new node
while(currPtr != NULL && item >
currPtr->datum)
{
prevPtr = currPtr;
currPtr = currPtr->next;
}
newNodePtr = new ListElement(item, currPtr);
if (prevPtr == NULL) // insert at the beginning
head=newNodePtr;
else
prevPtr->next = newNodePtr;
}
void LinkedList::makeList()
{
int InValue;
ListElement *currPtr;
ListElement *newNodePtr;
cout << "Enter values for a linked list, one per line."
<< endl
<< "Enter 999 to end the list." << endl;
cin >> InValue;
//Adding elements to end so that "next" will be NULL
newNodePtr=new ListElement(InValue, NULL);
head=newNodePtr; //assign head to the first Node
currPtr=head;
cin >> InValue;
while ( InValue != 999)
{
newNodePtr=new ListElement(InValue, NULL);
currPtr->next=newNodePtr; //link the new node to list
currPtr=newNodePtr; //move the currPtr so it is at end of
list
cin >> InValue;
}
}
void LinkedList::appendItem (int item) {
//REPLACE THE LINE BELOW WITH YOUR OWN CODE
//cout << "You must implement this function"
<<endl;
ListElement *temp = head, *newNodePtr = NULL;
while(temp->getNext () != NULL) {
temp = temp->next;
}
newNodePtr = new ListElement(item, temp);
temp -> next = newNodePtr;
newNodePtr -> next = NULL;
}
void LinkedList::deleteItem (int item) {
//REPLACE THE LINE BELOW WITH YOUR OWN CODE
//cout << "You must implement this function"
<<endl;
bool flag = false;
if(head->getDatum() == item ) {
flag = true;
head = head->next;
} else {
ListElement *currPtr =
head->next, *prevPtr = head;
while(currPtr != NULL) {
if(currPtr->getDatum() == item) {
flag = true;
prevPtr -> next = currPtr -> next;
} else {
prevPtr = currPtr;
}
currPtr =
currPtr -> next;
}
}
if(!flag) {
cout << "No matching data
found in the list" << endl;
}
}
void LinkedList::printList () {
//REPLACE THE LINE BELOW WITH YOUR OWN CODE
//cout << "You must implement this function"
<<endl;
ListElement *temp = head;
while( temp != NULL) {
cout << temp->getDatum() << " ";
temp = temp->next;
}
cout << endl;
}
Output:
This program demonstrates the linked list.
Initially, you will be asked to create the list.
You will be later prompted to manipulate the list.
Enter values for a linked list, one per line.
Enter 999 to end the list.
4
12
16
999
*******************************************************
i: Insert (Insert an element and keep the list ordered)
a: Append (Append an element to the end of the list)
d: Delete (Delete a node with the given value)
p: Print (Print the content of the current list)
q: Quit (Quit the program)
*******************************************************
Please enter your choice here:i
Please enter an integer value to insert:8
*******************************************************
i: Insert (Insert an element and keep the list ordered)
a: Append (Append an element to the end of the list)
d: Delete (Delete a node with the given value)
p: Print (Print the content of the current list)
q: Quit (Quit the program)
*******************************************************
Please enter your choice here:p
The content of the current ordered list is:
4 8 12 16
*******************************************************
i: Insert (Insert an element and keep the list ordered)
a: Append (Append an element to the end of the list)
d: Delete (Delete a node with the given value)
p: Print (Print the content of the current list)
q: Quit (Quit the program)
*******************************************************
Please enter your choice here:a
Please enter an integer value to append to the end:30
*******************************************************
i: Insert (Insert an element and keep the list ordered)
a: Append (Append an element to the end of the list)
d: Delete (Delete a node with the given value)
p: Print (Print the content of the current list)
q: Quit (Quit the program)
*******************************************************
Please enter your choice here:p
The content of the current ordered list is:
4 8 12 16 30
*******************************************************
i: Insert (Insert an element and keep the list ordered)
a: Append (Append an element to the end of the list)
d: Delete (Delete a node with the given value)
p: Print (Print the content of the current list)
q: Quit (Quit the program)
*******************************************************
Please enter your choice here:d
Please enter an integer value to delete:4
*******************************************************
i: Insert (Insert an element and keep the list ordered)
a: Append (Append an element to the end of the list)
d: Delete (Delete a node with the given value)
p: Print (Print the content of the current list)
q: Quit (Quit the program)
*******************************************************
Please enter your choice here:p
The content of the current ordered list is:
8 12 16 30
*******************************************************
i: Insert (Insert an element and keep the list ordered)
a: Append (Append an element to the end of the list)
d: Delete (Delete a node with the given value)
p: Print (Print the content of the current list)
q: Quit (Quit the program)
*******************************************************
Please enter your choice here:d
Please enter an integer value to delete:30
*******************************************************
i: Insert (Insert an element and keep the list ordered)
a: Append (Append an element to the end of the list)
d: Delete (Delete a node with the given value)
p: Print (Print the content of the current list)
q: Quit (Quit the program)
*******************************************************
Please enter your choice here:p
The content of the current ordered list is:
8 12 16
*******************************************************
i: Insert (Insert an element and keep the list ordered)
a: Append (Append an element to the end of the list)
d: Delete (Delete a node with the given value)
p: Print (Print the content of the current list)
q: Quit (Quit the program)
*******************************************************
Please enter your choice here:d
Please enter an integer value to delete:12
*******************************************************
i: Insert (Insert an element and keep the list ordered)
a: Append (Append an element to the end of the list)
d: Delete (Delete a node with the given value)
p: Print (Print the content of the current list)
q: Quit (Quit the program)
*******************************************************
Please enter your choice here:p
The content of the current ordered list is:
8 16
*******************************************************
i: Insert (Insert an element and keep the list ordered)
a: Append (Append an element to the end of the list)
d: Delete (Delete a node with the given value)
p: Print (Print the content of the current list)
q: Quit (Quit the program)
*******************************************************
Please enter your choice here:d
Please enter an integer value to delete:2
No matching data found in the list
*******************************************************
i: Insert (Insert an element and keep the list ordered)
a: Append (Append an element to the end of the list)
d: Delete (Delete a node with the given value)
p: Print (Print the content of the current list)
q: Quit (Quit the program)
*******************************************************
Please enter your choice here:q
Bye
Thanks. Please do comment if you could not understand anything.
CSCI 2010 Lab11 Link-Lists Lab 11A Linked-Lists Preparation Create a Visual Studio C++ Project C...
C++ - I have a doubly linked list, but I haven't been able to get the "reverse list" option in the code to work(It's option #in the menu in the program). I received this guidance for testing: Test 4 cases by entering (in this order) c,a,z,k,l,m This tests empty list, head of list, end of list and middle of list. Then delete (in this order) a,z,l. This tests beginning, end and middle deletes. This exhaustively tests for pointer errors. #include...
Q) Modify the class Linked List below to make it a Doubly Linked List. Name your class DoublyLinkedList. Add a method addEnd to add an integer at the end of the list and a method displayInReverse to print the list backwards. void addEnd(int x): create this method to add x to the end of the list. void displayInReverse(): create this method to display the list elements from the last item to the first one. Create a main() function to test...
For the LinkedList class, create a getter and setter for the private member 'name', constructing your definitions based upon the following declarations respectively: std::string get_name() const; and void set_name(std::string); In the Main.cpp file, let's test your getter and setter for the LinkedLIst private member 'name'. In the main function, add the following lines of code: cout << ll.get_name() << endl; ll.make_test_list(); ll.set_name("My List"); cout << ll.get_name() << endl; Output should be: Test List My List Compile and run your code;...
BELOW IS THE CODE I ALREADY HAVE Linked List - Delete Modify Lab 5 and include the method to delete a node from the Linked List. In summary: 1) Add the method Delete 2) Method call to delete, with a number that IS in the list 3) Method call to delete, with a number that is NOT in the list - Be sure to include comments - Use meaningful identifier names (constants where appropriate) import java.io.*; 1/ Java program to...
Requirements: Finish all the functions which have been declared inside the hpp file. Details: string toString(void) const Return a visible list using '->' to show the linked relation which is a string like: 1->2->3->4->5->NULL void insert(int position, const int& data) Add an element at the given position: example0: 1->3->4->5->NULL instert(1, 2); 1->2->3->4->5->NULL example1: NULL insert(0, 1) 1->NULL void list::erase(int position) Erase the element at the given position 1->2->3->4->5->NULL erase(0) 2->3->4->5->NULL //main.cpp #include <iostream> #include <string> #include "SimpleList.hpp" using std::cin; using...
#include <iostream> using namespace std; struct ListNode { float value; ListNode *next; }; ListNode *head; class LinkedList { public: int insertNode(float num); void deleteNode(float num); void destroyList(); void displayList(); LinkedList(void) {head = NULL;} ~LinkedList(void) {destroyList();} }; int LinkedList::insertNode(float num) { struct ListNode *newNode, *nodePtr = head, *prevNodePtr = NULL; newNode = new ListNode; if(newNode == NULL) { cout << "Error allocating memory for new list member!\n"; return 1; } newNode->value = num; newNode->next = NULL; if(head==NULL) { cout << "List...
In C++, for the provided template linked list class create a derived class of it which adds the functionality to it to find the high and low value of any given data stored in the list. The derived class must be a template. LinkedList.h #pragma once #include <iostream> using namespace std; template <class T> class ListNode { public: T data; ListNode<T>* next; ListNode(T data) { this->data = data;...
Linkedlist implementation in C++ The below code I have written is almost done, I only need help to write the definition for delete_last() function. Language C++ // LinkedList.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <string> #include <iostream> using namespace std; struct Node { int dataItem;//Our link list stores integers Node *next;//this is a Node pointer that will be areference to next node in the list }; class LinkedList { private: Node *first;...
Please fill in this code to reverse a linked list: (written in C/C++) #include #include #include using namespace std; /* Link list node */ struct Node { int data; // your code here }; /* Function to reverse the linked list */ static void reverse(struct Node** head_ref) { // your code here } /* Function to push a node */ void push(struct Node** head_ref, int new_data) { // your code here } /* Function to print linked list */ void...
I have a problem with merging the two linked lists together. In the function AscendMerge, I am trying to compare the values of each node in the two lists and output them into one list in ascended order. Everything works except for the one function. Can someone tell me what im doing wrong, when I run it it skips over values. #include <iostream> #include <cassert> using namespace std; struct nodeType { int info; nodeType *link; nodeType *current;...