Write a C program for the following question. The codes are given below. LinkedL
ID: 3589471 • Letter: W
Question
Write a C program for the following question. The codes are given below.
LinkedList.cpp Code:
#include "LinkedList.h"
#include
LinkedList::LinkedList() : headPtr(nullptr), itemCount(0)
{
} // end default constructor
void LinkedList::clear()
{
while (!isEmpty())
remove(1);
} // end clear
int LinkedList::getLength() const
{
return itemCount;
} // end getLength
bool LinkedList::isEmpty() const
{
return itemCount == 0;
} // end isEmpty
ItemType LinkedList::getEntry(int position) const
{
bool ableToGet = (position >= 1) && (position <= itemCount);
if (ableToGet)
{
Node* nodePtr = getNodeAt(position);
return nodePtr->getItem();
}
else
{
std::string message = "getEntry() called with an empty list or ";
message = message + "invalid position.";
throw(message);
}
} // end getEntry
bool LinkedList::insert(int newPosition, const ItemType& newEntry)
{
bool ableToInsert = (newPosition >= 1) && (newPosition <= itemCount + 1);
if (ableToInsert)
{
// Create a new node containing the new entry
Node* newNodePtr = new Node(newEntry);
// Attach new node to chain
if (newPosition == 1)
{
// Insert new node at beginning of chain
newNodePtr->setNext(headPtr);
headPtr = newNodePtr;
}
else
{
// Find node that will be before new node
Node* prevPtr = getNodeAt(newPosition - 1);
// Insert new node after node to which prevPtr points
newNodePtr->setNext(prevPtr->getNext());
prevPtr->setNext(newNodePtr);
}
itemCount++; // Increase count of entries
}
return ableToInsert;
} // end insert
bool LinkedList::remove(int position)
{
bool ableToRemove = (position >= 1) && (position <= itemCount);
if (ableToRemove)
{
Node* curPtr = nullptr;
if (position == 1)
{
// Remove the first node in the chain
curPtr = headPtr; // Save pointer to node
headPtr = headPtr->getNext();
}
else
{
// Find node that is before the one to remove
Node* prevPtr = getNodeAt(position - 1);
// Point to node to remove
curPtr = prevPtr->getNext();
// Disconnect indicated node from chain by connecting the
// prior node with the one after
prevPtr->setNext(curPtr->getNext());
}
// Return node to system
curPtr->setNext(nullptr);
delete curPtr;
curPtr = nullptr;
itemCount--; // Decrease count of entries
}
return ableToRemove;
} // end remove
ItemType LinkedList::replace(int position, const ItemType& newEntry)
{
bool ableToReplace = (position >= 1) && (position <= itemCount);
if (ableToReplace)
{
Node* entryPtr = getNodeAt(position);
ItemType oldEntry = entryPtr->getItem();
entryPtr->setItem(newEntry);
return oldEntry;
}
else
{
std::string message = "replace() called with an empty list or ";
message = message + "invalid position.";
throw(message);
}
} // end replace
Node* LinkedList::getNodeAt(int position) const
{
// Debugging check of precondition
assert( (position >= 1) && (position <= itemCount) );
// Count from the beginning of the chain
Node* curPtr = headPtr;
for (int skip = 1; skip < position; skip++)
curPtr = curPtr->getNext();
return curPtr;
} // end getNodeAt
LinkedList::~LinkedList()
{
clear();
} // end destructor
LinkedList.h Code:
#ifndef LINKED_LIST_
#define LINKED_LIST_
#include "Node.h"
#include
using namespace std;
typedef int ItemType;
class LinkedList
{
private:
Node* headPtr; // Pointer to first node in the chain;
int itemCount; // Current count of list items
// Locates a specified node in this linked list.
Node* getNodeAt(int position) const;
public:
LinkedList();
// Copy constructor and destructor are supplied by compiler
bool isEmpty() const;
int getLength() const;
bool insert(int newPosition, const ItemType& newEntry);
bool remove(int position);
void clear();
ItemType getEntry(int position) const;
ItemType replace(int position, const ItemType& newEntry);
virtual ~LinkedList();
}; // end ArrayList
#endif
LinkedListTest.cpp Code:
#include "LinkedList.h"
#include
int main()
{
LinkedList list;
for (int i = 1; i <= 10; i++)
{
list.insert(i, 100 + i);
}
cout << "length [10]: " << list.getLength() << endl;
cout << "isEmpty [0]: " << list.isEmpty() << endl;
list.remove(3);
cout << "length [9]: " << list.getLength() << endl;
int entry = list.getEntry(3);
cout << "Entry [104]: " << entry << endl;
list.replace(3, 999);
entry = list.getEntry(3);
cout << "Entry [999]: " << entry << endl;
cout << "list: ";
for (int i = 1; i <= list.getLength(); i++)
{
cout << list.getEntry(i) << " ";
}
cout << endl;
list.clear();
cout << "length [0]: " << list.getLength() << endl;
cout << "isEmpty [1]: " << list.isEmpty() << endl;
}
Node.cpp Code:
#include "Node.h"
Node::Node() : next(nullptr)
{
} // end default constructor
Node::Node(const ItemType& anItem) : item(anItem), next(nullptr)
{
} // end constructor
Node::Node(const ItemType& anItem, Node* nextNodePtr) :
item(anItem), next(nextNodePtr)
{
} // end constructor
void Node::setItem(const ItemType& anItem)
{
item = anItem;
} // end setItem
void Node::setNext(Node* nextNodePtr)
{
next = nextNodePtr;
} // end setNext
ItemType Node::getItem() const
{
return item;
} // end getItem
Node* Node::getNext() const
{
return next;
} // end getNext
Node.h Code:
#ifndef NODE_
#define NODE_
#include
using namespace std;
typedef int ItemType;
class Node
{
private:
ItemType item; // A data item
Node* next; // Pointer to next node
public:
Node();
Node(const ItemType& anItem);
Node(const ItemType& anItem, Node* nextNodePtr);
void setItem(const ItemType& anItem);
void setNext(Node* nextNodePtr);
ItemType getItem() const ;
Node* getNext() const ;
}; // end Node
#endif
You are going to implement a Doubly Linked List. Your class will be called DoublyLinkedList Its best to start with a copy of the implementation for a regular Linked List discussed in class, and make the appropriate adjustments for it to become a doubly linked list. • Keep all the existing methods (suitably modified) • Add a tail pointer to the implementation Add a Copy Constructor that does a deep copy. (Use the Bag copy constructor as a reference) • Add another new constructor that takes a (singly) Linked List as an argument and creates the Doubly Linked List from it: DoublyLinkedList (const LinkedList & linkedList). You will create new Nodes for the doubly linked list - you will not modify the list passed in - rather, you will copy from it. You will, of course, need to include your regular LinkedList header and cpp file for this to compile. Add a method void reverse () which reverses the list. This method should not make a copy of the list, nor should it allocate any new nodes, nor should it swap data between nodes – it must reverse the list simply by modifying pointers. • Add the a method vectorExplanation / Answer
#include "DoublyLinkedList.h"
#include <iostream>
using namespace std;
int main()
{
LinkedList slist;
slist.insert(1, "aa");
slist.insert(2, "bb");
slist.insert(3, "cc");
slist.insert(4, "dd");
DoublyLinkedList dlist(slist);
cout << "Step 3 dlist: ";
vector<ItemType> list1 = dlist.toVector(false);
for (int i = 0; i < dlist.getLength(); i++) cout << " " << list1[i] ;
cout << " Step 4 dlist: ";
vector<ItemType> list2 = dlist.toVector(true);
for (int i = 0; i < dlist.getLength(); i++) cout << " " << list2[i];
dlist.reverse();
cout << " Step 6 dlist: ";
vector<ItemType> list3 = dlist.toVector(false);
for (int i = 0; i < dlist.getLength(); i++) cout << " " << list3[i];
DoublyLinkedList dlist2(dlist);
cout << " Step 8 dlist2: ";
vector<ItemType> list5 = dlist2.toVector(false);
for (int i = 0; i < dlist2.getLength(); i++) cout << " " << list5[i];
dlist2.reverse();
cout << " Step 10 dlist2: ";
vector<ItemType> list6 = dlist2.toVector(false);
for (int i = 0; i < dlist2.getLength(); i++) cout << " " << list6[i];
cout << " Step 11 dlist: ";
vector<ItemType> list7 = dlist.toVector(false);
for (int i = 0; i < dlist.getLength(); i++) cout << " " << list7[i];
cout << ' ';
dlist.clear(); dlist2.clear(); slist.clear();
}
----------------------------------------------------------------------------------------
DoublyLinkedList.cpp
-------------------------------------------------------
#include "DoublyLinkedList.h"
#include <cassert>
#include <iostream>
using namespace std;
DoublyLinkedList::DoublyLinkedList() : headPtr(nullptr), itemCount(0), tailPtr(nullptr)
{
} // end default constructor
DoublyLinkedList::DoublyLinkedList(const DoublyLinkedList &obj) : itemCount(obj.itemCount)
{
if (obj.headPtr == nullptr) {
headPtr = nullptr;
}
else {
headPtr = new Node(obj.headPtr->getItem());
Node *currentObj = obj.headPtr;
Node *current = headPtr;
while (currentObj->getNext() != NULL)
{
current->setNext(new Node(currentObj->getNext()->getItem()));
current->getNext()->setPrev(current);
current = current->getNext();
currentObj = currentObj->getNext();
}
tailPtr = current->getPrev();
}
} //end deep copy constructor
DoublyLinkedList::DoublyLinkedList(const LinkedList &obj) :itemCount(obj.getLength())
{
if (obj.getHeadPtr() == nullptr) {
headPtr = nullptr;
}
else {
headPtr = new Node(obj.getHeadPtr()->getItem());
Node *currentObj = obj.getHeadPtr();
Node *current = headPtr;
for (int i = 1; i < itemCount; i++)
{
current->setNext(new Node(obj.getEntry(i + 1)));
current->getNext()->setPrev(current);
current = current->getNext();
currentObj = currentObj->getNext();
}
tailPtr = current;
}
} // end LL to DLL
void DoublyLinkedList::reverse()
{
Node *ptr = headPtr;
while (ptr != nullptr) {
Node *tmp = ptr->getNext();
ptr->setNext(ptr->getPrev());
ptr->setPrev(tmp);
if (tmp == nullptr) {
tailPtr = headPtr;
headPtr = ptr;
}
ptr = tmp;
}
} // end reverse
void DoublyLinkedList::clear()
{
while (!isEmpty())
remove(1);
} // end clear
vector<ItemType> DoublyLinkedList::toVector(bool reverse)
{
vector<ItemType> list;
Node* current = (reverse ? tailPtr : headPtr);
while (current != nullptr)
{
list.push_back(current->getItem());
current = (reverse ? current->getPrev() : current->getNext());
}
return list;
}
int DoublyLinkedList::getLength() const
{
return itemCount;
} // end getLength
bool DoublyLinkedList::isEmpty() const
{
return itemCount == 0;
} // end isEmpty
ItemType DoublyLinkedList::getEntry(int position) const
{
bool ableToGet = (position >= 1) && (position <= itemCount);
if (ableToGet)
{
Node* nodePtr = getNodeAt(position);
return nodePtr->getItem();
}
else
{
std::string message = "getEntry() called with an empty list or ";
message = message + "invalid position.";
throw(message);
}
} // end getEntry
bool DoublyLinkedList::insert(int newPosition, const ItemType& newEntry)
{
bool ableToInsert = (newPosition >= 1)&& (newPosition <= itemCount + 1);
if (ableToInsert)
{
// Create a new node containing the new entry
Node* newNodePtr = new Node(newEntry);
// Attach new node to chain
if (newPosition == 1)
{
// Insert new node at beginning of chain
newNodePtr->setNext(headPtr);
//Prev is already nullptr
headPtr = newNodePtr;
}
else
{
// Find node that will be before new node
newNodePtr->setPrev(getNodeAt(newPosition - 1));
// Insert new node after node to which prevPtr points
newNodePtr->setNext(newNodePtr->getPrev()->getNext());
newNodePtr->getPrev()->setNext(newNodePtr);
if (newPosition = getLength()) tailPtr = newNodePtr;
}
itemCount++; // Increase count of entries
}
return ableToInsert;
} // end insert
bool DoublyLinkedList::remove(int position)
{
bool ableToRemove = (position >= 1)&& (position <= itemCount);
if (ableToRemove)
{
Node* curPtr = nullptr;
if (position == 1)
{
// Remove the first node in the chain
curPtr = headPtr; // Save pointer to node
headPtr = headPtr->getNext();
// Set previous to null
if (headPtr != nullptr)
headPtr->setPrev(nullptr);
}
else
{
// Find node that is before the one to remove
Node* prevPtr = getNodeAt(position - 1);
// Point to node to remove
curPtr = prevPtr->getNext();
// Disconnect indicated node from chain by connecting the
// prior node with the one after
prevPtr->setNext(curPtr->getNext());
curPtr->getNext()->setPrev(prevPtr);
}
// Return node to system
curPtr->setNext(nullptr);
curPtr->setPrev(nullptr);
delete curPtr;
curPtr = nullptr;
itemCount--; // Decrease count of entries
}
return ableToRemove;
} // end remove
ItemType DoublyLinkedList::replace(int position, const ItemType& newEntry)
{
bool ableToReplace = (position >= 1)&& (position <= itemCount);
if (ableToReplace)
{
Node* entryPtr = getNodeAt(position);
ItemType oldEntry = entryPtr->getItem();
entryPtr->setItem(newEntry);
return oldEntry;
}
else
{
std::string message = "replace() called with an empty list or ";
message = message + "invalid position.";
throw(message);
}
} // end replace
Node* DoublyLinkedList::getNodeAt(int position) const
{
// Debugging check of precondition
assert((position >= 1) && (position< = itemCount));
// Count from the beginning of the chain
Node* curPtr = headPtr;
for (int skip = 1; skip < position; skip++)
curPtr = curPtr->getNext();
return curPtr;
} // end getNodeAt
DoublyLinkedList::~DoublyLinkedList()
{
clear();
} // end destructor
-----------------------------------------------------------------------------------------
DoublyLinkedList.h
---------------------------------------
#ifndef DOUBLY_LINKED_LIST
#define DOUBLY_LINKED_LIST
#include "Node.h"
#include "LinkedList.h"
#include <vector>
#include <string>
using namespace std;
typedef string ItemType;
class DoublyLinkedList
{
private:
Node* headPtr; // Pointer to first node in the chain
Node* tailPtr; // Pointer to the last node in the chain
int itemCount; // Current count of list items
// Locates a specified node in this doubly linked list
Node* getNodeAt(int position) const;
public:
DoublyLinkedList();
// Copy constructor and destructor are supplied by compiler
DoublyLinkedList(const DoublyLinkedList& obj); // Deep copy constructor
DoublyLinkedList(const LinkedList &obj); // LL to DLL
bool isEmpty() const;
int getLength() const;
bool insert(int newPosition, const ItemType& newEntry);
bool remove(int position);
void clear();
void reverse();
ItemType getEntry(int position) const;
ItemType replace(int position, const ItemType& newEntry);
vector<ItemType> toVector(bool reverse);
virtual ~DoublyLinkedList();
}; // end ArrayList
#endif
-------------------------------------------------------------------------------
LinkedList.cpp
--------------------------------------------
#include "LinkedList.h"
#include <cassert>
LinkedList::LinkedList() : headPtr(nullptr), itemCount(0)
{
} // end default constructor
void LinkedList::clear()
{
while (!isEmpty())
remove(1);
} // end clear
int LinkedList::getLength() const
{
return itemCount;
} // end getLength
bool LinkedList::isEmpty() const
{
return itemCount == 0;
} // end isEmpty
ItemType LinkedList::getEntry(int position) const
{
bool ableToGet = (position >= 1) && (position <= itemCount);
if (ableToGet)
{
Node* nodePtr = getNodeAt(position);
return nodePtr->getItem();
}
else
{
std::string message = "getEntry() called with an empty list or ";
message = message + "invalid position.";
throw(message);
}
} // end getEntry
bool LinkedList::insert(int newPosition, const ItemType& newEntry)
{
bool ableToInsert = (newPosition >= 1)&& (newPosition <= itemCount + 1);
if (ableToInsert)
{
// Create a new node containing the new entry
Node* newNodePtr = new Node(newEntry);
// Attach new node to chain
if (newPosition == 1)
{
// Insert new node at beginning of chain
newNodePtr->setNext(headPtr);
headPtr = newNodePtr;
}
else
{
// Find node that will be before new node
Node* prevPtr = getNodeAt(newPosition - 1);
// Insert new node after node to which prevPtr points
newNodePtr->setNext(prevPtr->getNext());
prevPtr->setNext(newNodePtr);
}
itemCount++; // Increase count of entries
}
return ableToInsert;
} // end insert
bool LinkedList::remove(int position)
{
bool ableToRemove = (position >= 1)&& (position <= itemCount);
if (ableToRemove)
{
Node* curPtr = nullptr;
if (position == 1)
{
// Remove the first node in the chain
curPtr = headPtr; // Save pointer to node
headPtr = headPtr->getNext();
}
else
{
// Find node that is before the one to remove
Node* prevPtr = getNodeAt(position - 1);
// Point to node to remove
curPtr = prevPtr->getNext();
// Disconnect indicated node from chain by connecting the
// prior node with the one after
prevPtr->setNext(curPtr->getNext());
}
// Return node to system
curPtr->setNext(nullptr);
delete curPtr;
curPtr = nullptr;
itemCount--; // Decrease count of entries
}
return ableToRemove;
} // end remove
Node* LinkedList::getHeadPtr() const {
return headPtr;
}
ItemType LinkedList::replace(int position, const ItemType& newEntry)
{
bool ableToReplace = (position >= 1)&& (position <= itemCount);
if (ableToReplace)
{
Node* entryPtr = getNodeAt(position);
ItemType oldEntry = entryPtr->getItem();
entryPtr->setItem(newEntry);
return oldEntry;
}
else
{
std::string message = "replace() called with an empty list or ";
message = message + "invalid position.";
throw(message);
}
} // end replace
Node* LinkedList::getNodeAt(int position) const
{
// Debugging check of precondition
assert((position >= 1) && (position< = itemCount));
// Count from the beginning of the chain
Node* curPtr = headPtr;
for (int skip = 1; skip < position; skip++)
curPtr = curPtr->getNext();
return curPtr;
} // end getNodeAt
LinkedList::~LinkedList()
{
clear();
} // end destructor
----------------------------------------------------------------
LinkedList.h
--------------------------------
#ifndef LINKED_LIST_
#define LINKED_LIST_
#include "Node.h"
#include <string>
using namespace std;
typedef string ItemType;
class LinkedList
{
private:
Node* headPtr; // Pointer to first node in the chain;
int itemCount; // Current count of list items
// Locates a specified node in this linked list.
Node* getNodeAt(int position) const;
public:
LinkedList();
// Copy constructor and destructor are supplied by compiler
bool isEmpty() const;
int getLength() const;
bool insert(int newPosition, const ItemType& newEntry);
bool remove(int position);
void clear();
Node* getHeadPtr() const;
ItemType getEntry(int position) const;
ItemType replace(int position, const ItemType& newEntry);
virtual ~LinkedList();
}; // end ArrayList
#endif
----------------------------------------------------------------------------
Node.cpp
----------------------------------
#include "Node.h"
Node::Node() : next(nullptr), prev(nullptr)
{
} // end default constructor
Node::Node(const ItemType& anItem) : item(anItem), next(nullptr), prev(nullptr)
{
} // end constructor
Node::Node(const ItemType& anItem, Node* nextNodePtr) :
item(anItem), next(nextNodePtr)
{
} // end constructor
void Node::setItem(const ItemType& anItem)
{
item = anItem;
} // end setItem
void Node::setNext(Node* nextNodePtr)
{
next = nextNodePtr;
} // end setNext
void Node::setPrev(Node* prevNodePtr)
{
prev = prevNodePtr;
} // end setPrev
ItemType Node::getItem() const
{
return item;
} // end getItem
Node* Node::getNext() const
{
return next;
} // end getNext
Node* Node::getPrev() const
{
return prev;
} // end getPrev
------------------------------------------------------------------------------
Node.h
------------------------------------------
#ifndef NODE_
#define NODE_
#include <string>
using namespace std;
typedef string ItemType;
class Node
{
private:
ItemType item; // A data item
Node* prev; // Pointer to prev node
Node* next; // Pointer to next node
public:
Node();
Node(const ItemType& anItem);
Node(const ItemType& anItem, Node* nextNodePtr);
void setItem(const ItemType& anItem);
void setNext(Node* nextNodePtr);
void setPrev(Node* nextNodePtr);
ItemType getItem() const;
Node* getNext() const;
Node* getPrev() const;
}; // end Node
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.