QuestionQuestion

Doubly-linked List
Goals
Build a doubly-linked list that utilizes pointers
Learn how to modify data in a linked list
In this lab, we will create a simple doubly-linked list data structures consisting of Node objects.
Requirements
For simplicity, our doubly-linked list will only contain integer as value.
Note: You are not allowed to use any standard containers for this lab.

Node Class
Node class has the following member variables:
next, a pointer to the next Node object
prev, a pointer to the previous Node object
val, integer value the specific Node contains

Doubly-Linked List
For the doubly-linked list object, it has a head pointer that points to the first Node in the linked list, and a tail
pointer that points to the last Node in the linked list. If the linked list is empty, the head and tail should point
to NULL. If the linked list has only one Node object, the head and tail should both point to that Node object.
Note: You can decide the class name for doubly-linked list
Functions for the Linked List
Implement the functions to do the following linked list operations:

1. Add a new node to the head.
2. Add a new node to the tail.
3. Delete the first node in the list.
4. Delete the last node in the list.
5. Traverse the list reversely, that is to print the nodes from back of the linked list to the front (tail to head).
6. Traverse the list, that is to print the nodes from front of the linked list to the back (head to tail).

Menu
Function #1, #2
When user adds a new node, the program should prompt the user to enter a number and validate the input, before calling the function.
Operation of adding functions:
The function should create a new Node with inputted value stored inside, add the Node object to the list, and re-assign the head tail pointer accordingly. After the Node is added, the menu should call function #6, which prints the linked list from head to tail.

Function #3, #4
When user chooses to remove a node, the program should check whether the list is empty: if so, give a warning message, and if not, proceed with the function.
Operation of removal functions: The function should delete the Node and free the memory, then re-assign head/tail pointers as well as the pointers inside adjacent Node of the Node removed.
After the Node is removed, the menu should call function #6, which prints the linked list from head to tail.
Function #5
When user chooses to print the list in reverse from tail to head, the program should print the value of all Nodes in the linked list from tail to head. If the list is empty, print a message to indicate that.
Function #6

Note: Function #6 is special, it does not exist in the menu option, but it gets called every time the user adds or removes a Node from the list.
Whenever this function is called inside the program, it should print the value of all Nodes in the linked list from head to tail. If the list is empty, print a message to indicate that.
Lastly, you need to add one more option in the menu to exit the program.
Important: For this lab, you cannot implement the linked list operations using functions from outside source.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

/*
* File:   DoublyLinkedList.cpp
* Author:
*
*
*/

#include "DoublyLinkedList.hpp"
#include <iostream>
using namespace std;

/**
* constructor
* all pointer points to null
*/
DoublyLinkedList::DoublyLinkedList() {
    head = 0;
    tail = 0;
}

/**
* destructor
*/
DoublyLinkedList::~DoublyLinkedList() {
    // clear all allocated memory
    clear();
}

/**
* add to head of the list
* @param val node's value
*/
void DoublyLinkedList::addToHead(int val) {

    // allocate memory
    Node * n = new Node();
    // set its value
    n->setVal(val);
    // set address of next pointer
    n->setNext(head);

    // the list is empty at the moment
    if (tail == 0) {
       tail = n;
    } else {
       // the list isn't empty at the moment
       head->setPrev(n);
    }
    // add to head so head pointer points to the newly created node
    head = n;
}

/**
* add to tail of the list
* @param val node's value
*/
void DoublyLinkedList::addToTail(int val) {

    // allocate memory
    Node * n = new Node();
    // set its value
    n->setVal(val);
    // set address of previous pointer
    n->setPrev(tail);

    // the list is empty at the moment
    if (tail == 0) {
       head = n;
    } else {
       // the list isn't empty at the moment
       tail->setNext(n);
    }
    // add to tail so tail pointer points to the newly created node
    tail = n;
}

/**
* remove head of the list
*/
void DoublyLinkedList::deleteHead() {

    // empty list
    if (head == 0) {
       return;
    }

    // pointer points to the head
    Node * tmp = head;

    // move head to the next node
    head = head->getNext();

    // list is empty now
    if (head == 0) {
       tail = 0;
    } else {
       // list isn't empty
       head->setPrev(0);
    }
    // free a block of memory
    delete tmp...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

50% discount

Hours
Minutes
Seconds
$55.00 $27.50
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available C-Family Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats