Question

Create a linked list with the following features. A Node class that stores the data type...

Create a linked list with the following features.

A Node class that stores the data type of your choice.

A constructor that creates a dummy header node.

void display() -- A method for printing the list.

void add(item) -- A method for adding a value to the beginning of the list

void addEnd(item) -- A method of adding a value to the end of the list.

bool contains(item) -- A method for finding a specified value in the list.

int count() -- A method for returning the number of values in the list.

int count(item) -- A method for counting the number of instances of a specified value in the list.

int remove(item) -- A method for deleting a value from the list.

A destructor for destroying the list.

Write a test program in C++ that creates a linked list and demonstrates all of the above functions.

0 0
Add a comment Improve this question Transcribed image text
Answer #1
#include<iostream>

using namespace std;

struct Node
{
    int data;
    Node *next;
};

class LinkedList
{
private:
    Node *head;
public:
    //Constructor
    LinkedList();

    //Prints the list
    void display() const;

    //Insert in front of list
    void add(int item);

    //Insert in front of list
    void addEnd(int item);

    //Check if item is in list or not
    bool contains(int item);

    //Return number of values in the list
    int count();

    //Return number of values of specified item in the list
    int count(int item);

    //Remove item from list
    void remove(int item);

    //Destructor
    ~LinkedList();
};

//Constructor
LinkedList::LinkedList() : head(nullptr) {}

//Prints the list
void LinkedList::display() const{
    Node *ptr = head;
    while(ptr != nullptr)
    {
        cout << ptr->data << " ";
        ptr = ptr->next;
    }
}

//Insert in front of list
void LinkedList::add(int item){
    Node *newNode = new Node;
    newNode->data = item;
    newNode->next = nullptr;
    if(head == nullptr)//When list is empty
        head = newNode;
    else
    {
        newNode->next = head;
        head = newNode;
    }
}

//Insert in front of list
void LinkedList::addEnd(int item){
    Node *newNode = new Node;
    newNode->data = item;
    newNode->next = nullptr;

    if(head == nullptr)
        head = newNode;
    else {
        Node *ptr = head;
        while (ptr->next != nullptr)
            ptr = ptr->next;
        ptr->next = newNode;
    }
}

//Check if item is in list or not
bool LinkedList::contains(int item){
    Node *ptr = head;
    while(ptr != nullptr && ptr->data != item)
        ptr = ptr->next;

    if(ptr == nullptr)//If value not found in the list
        return false;

    return true;
}

//Return number of values in the list
int LinkedList::count(){
    Node *ptr = head;
    int count = 0;

    while(ptr != nullptr) {
        count++;
        ptr = ptr->next;
    }
    return count;
}

//Return number of values of specified item in the list
int LinkedList::count(int item){
    Node *ptr = head;
    int count = 0;

    while(ptr != nullptr) {
        if(ptr->data == item)
            count++;
        ptr = ptr->next;
    }
    return count;
}

//Remove item from list
void LinkedList::remove(int item){
    Node *pre = nullptr;
    Node *cur = head;

    while(cur != nullptr && cur->data != item)
    {
        pre = cur;
        cur = cur->next;
    }

    if(cur == nullptr)//If value not found in list
        return;

    if(cur == head)//If value is first in the list
        head = head->next;
    else
        pre->next = cur->next;
    delete cur;//Free memory allocated for the node
}

//Destructor
LinkedList::~LinkedList(){
    Node *ptr = head;
    while(ptr != nullptr){
        int item = ptr->data;
        ptr = ptr->next;
        remove(item);
    }
}

int main(){
    /*Create a list of integers*/
    LinkedList list;

    //Test add and addEnd
    list.add(3);
    list.add(2);
    list.add(1);
    list.addEnd(4);
    list.addEnd(5);
    list.addEnd(1);

    cout << "The list is: ";
    list.display();
    cout << endl << endl;

    //Test remove
    list.remove(3);
    list.remove(2);

    cout << "The list is: ";
    list.display();
    cout << endl << endl;

    //Test contains
    if(list.contains(5))
        cout << "List contains 5" << endl;
    else
        cout << "List does not contain 5" << endl;

    //Test count
    cout << "Number of values in the list: " << list.count() << endl;
    cout << "Number of 1's in the list: " << list.count(1) << endl;

    return 0;
}

OUTPUT:

FOR ANY HELP JUST DROP A COMMENT

Add a comment
Know the answer?
Add Answer to:
Create a linked list with the following features. A Node class that stores the data type...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • Q) Modify the class Linked List below to make it a Doubly Linked List. Name your...

    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...

  • C++ Create a class that implements a sorted, doubly-linked list: Start with a copy of the...

    C++ Create a class that implements a sorted, doubly-linked list: Start with a copy of the sortedList class. Call your new class doublyLinkedList. Convert the baseline code into a doubly linkedlist, and thoroughly test all existing operations (make sure to check all edge conditions), and then implement the new operations below. The class should have the following additional class methods: • A reverse method: this method will reverse the order of the doubly linked list. This method takes no parameters,...

  • Consider a Linked List program with the following class: typedef int datatype; struct node {   datatype...

    Consider a Linked List program with the following class: typedef int datatype; struct node {   datatype data; node *tail; }; class LinkedList{ private: node *head; node *current;public: //constructors LinkedList(); LinkedList(int i); //destructor ~LinkedList(); bool start(); //sets list postion to header bool nextNode(); //increments to next node in list int getCurrent(); //returns data from current node void insertNode(int i); //inserts node after current node    //then sets current node to new node bool deleteNode();//deletes currentnode void deleteAll(); //deletes all nodes };...

  • Part I: Create a doubly linked circular list class named LinkedItemList that implements the following interface:...

    Part I: Create a doubly linked circular list class named LinkedItemList that implements the following interface: /** * An ordered list of items. */ public interface ItemList<E> {      /**       * Append an item to the end of the list       *       * @param item – item to be appended       */ public void append(E item);      /**       * Insert an item at a specified index position       *       * @param item – item to be...

  • C programming A linked list is a linear data structure that allows us to add and remove items fro...

    c programming A linked list is a linear data structure that allows us to add and remove items from the list very quickly, by simply changing a few pointers. There are many different variations of linked lists. We have studied the doubly-linked, circular, with a dummy-header-node version of a linked list. In the class notes we studied several functions to manipulate a Linked List. For this assignment you must write the code for the following additional linked list functions: addFirst,...

  • Create an h file called list. It should have the following features: lisi's funnc In no particular order: List(): Default constructor. This should construct an empty List, the member variables sh...

    Create an h file called list. It should have the following features: lisi's funnc In no particular order: List(): Default constructor. This should construct an empty List, the member variables should be initialized to reflect this state. This function is already fully implemented. 1. List(const List<Type>& other): Copy constructor for the linked list. This should create an entirely new linked list with the same number of Nodes and the Values stored these Nodes in the same order as seen the...

  • Your task is to complete the following function/functions: 1. Given a position in the linked list,...

    Your task is to complete the following function/functions: 1. Given a position in the linked list, delete the node at that position.(Silver problem - Mandatory ) 2. Print the sum of all negative elements in the linked list.(Gold problem) If you want, you can refer to the the previous recitation manual (which was on Linked Lists) to implement node deletion. #include <iostream> using namespace std; //----------- Define Node --------------------------------------------------- struct Node{ int key; Node *next; }; //----------- Define Linked List...

  • n JAVA, students will create a linked list structure that will be used to support a...

    n JAVA, students will create a linked list structure that will be used to support a role playing game. The linked list will represent the main character inventory. The setting is a main character archeologist that is traveling around the jungle in search of an ancient tomb. The user can add items in inventory by priority as they travel around (pickup, buy, find), drop items when their bag is full, and use items (eat, spend, use), view their inventory as...

  • Inventory (linked lists: insert at the front of a list)

    import java.util.Scanner;public class Inventory {   public static void main (String[] args) {      Scanner scnr = new Scanner(System.in);             InventoryNode headNode;                                                    InventoryNode currNode;      InventoryNode lastNode;      String item;      int numberOfItems;      int i;      // Front of nodes list           ...

  • Binary Tree Template Write your own version of a class template that will create a binary...

    Binary Tree Template Write your own version of a class template that will create a binary tree that can hold values of any data type. Demonstrate the class with a driver program. Place your binary tree template in it's own header file, Btree.h. Include methods for the following: inserting new values into the tree removing nodes from the tree searching the tree returning the number of nodes in the tree displaying the contents of the tree using preorder traversal Your...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT