This is what I have so far.. #include <iostream> #include <string> using namespa
ID: 3702595 • Letter: T
Question
This is what I have so far..
#include <iostream>
#include <string>
using namespace std;
#ifndef NODE_H
#define NODE_H
class Node
{
private:
string data;
Node *nextPtr;
public:
Node();
Node(string d);
void setData(string);
string getData() const;
void setNextPtr(Node*);
Node* getNextPtr() const;
};
#endif
#include <iostream>
#include "Node.h"
#include <string>
using namespace std;
Node::Node()
{
}
Node::Node(string d)
{
data = d;
nextPtr = NULL;
}
void Node::setData(string s)
{
data = s;
}
string Node::getData() const
{
return data;
}
void Node::setNextPtr(Node * ptr)
{
nextPtr = ptr;
}
Node* Node::getNextPtr() const
{
return nextPtr;
}
#ifndef LINKEDLISTNODE_H
#define LINKEDLISTNODE_H
#include "Node.h"
#include <string>
using namespace std;
class LinkedList
{
private:
Node * head, *tail;
public:
LinkedList();
~LinkedList();
int size();
void add(string);
void addHead(string value);
void add_pos(int pos, string value);
bool isEmpty();
string deleteHead();
string deleteTail();
string delete_pos(int pos);
void display();
string to_string();
string first();
string last();
void addFirst(string);
void addLast(string);
void removeFirst();
};
#endif
#include "LinkedListNode.h"
#include "Node.h"
#include <iostream>
#include<string>
using namespace std;
LinkedList::LinkedList()
{
head = NULL;
tail = NULL;
}
LinkedList::~LinkedList() {
Node *n = this->head, *current = NULL; //initialization part
while (n) //start cleanup of nodes of the list
{
current = n;
n = n->getNextPtr();
delete(current);
}
head = tail = NULL;
}int LinkedList::size() {
Node *cur = new Node;
cur = head;
int size = 0;
while (cur != NULL)
{
size++;
cur = cur->getNextPtr();
}
return size;
}
//at the end of the list
void LinkedList::add(string value)
{
Node *temp = new Node;
temp->setData(value);
temp->setNextPtr(NULL);
if (head == NULL)
{
head = temp;
tail = temp;
temp = NULL;
}
else
{
tail->setNextPtr(temp);
tail = temp;
}
}
void LinkedList::addHead(string value)
{
Node *newest = new Node;
newest->setData(value);
newest->setNextPtr(head);
head = newest;
}
void LinkedList::add_pos(int pos, string value)
{
if (pos<0 or pos>size())
cout << "out of range ... can't insert";
else {
Node *pre = new Node;
Node *cur = new Node;
Node *newest = new Node;
cur = head;
for (int i = 1; i<pos; i++)
{
pre = cur;
cur = cur->getNextPtr();
}
newest->setData(value);
pre->setNextPtr(newest);
newest->setNextPtr(cur);
}
}
bool LinkedList::isEmpty()
{
Node *cur = new Node;
cur = head;
if (head == NULL)
{
return true;
cout << endl;
}
else return false;
cout << endl;
}
string LinkedList::deleteHead()
{
string a = "";
if (size() == 0)
//we have a problem here.. if the list is empty
//I am still returning an integer value
cout << "Empty List, nothing to delete";
else {
Node *temp = new Node;
a = head->getData();
temp = head;
head = head->getNextPtr();
delete temp;
}
return a;
}
string LinkedList::deleteTail()
{
//check if empty
Node *current = new Node;
Node *previous = new Node;
current = head;
while (current->getNextPtr() != NULL)
{
previous = current;
current = current->getNextPtr();
}
tail = previous;
previous->setNextPtr(NULL);
string a = current->getData();
delete current;
return a;
}
string LinkedList::delete_pos(int pos)
{
//we have a problem here.. if the list is empty
//I am still returning an integer value
string a = "";
if (pos<0 or pos>size())cout << "out of range ... nothing to delete";
else {
Node *current = new Node;
Node *previous = new Node;
current = head;
for (int i = 1; i<pos; i++)
{
previous = current;
current = current->getNextPtr();
}
a = current->getData();
previous->setNextPtr(current->getNextPtr());
delete current;
}
return a;
}
void LinkedList::display()
{
Node *cur = new Node;
cur = head;
while (cur != NULL)
{
cout << cur->getData() << " ";
cur = cur->getNextPtr();
}
}
string LinkedList::to_string()
{
string str = "";
Node *temp = new Node;
temp = head;
while (temp != NULL)
{
//in java I can str + int
str = str + (temp->getData()) + " ";
temp = temp->getNextPtr();
}
return str;
}
string LinkedList::first()
{
Node *cur = new Node;
cur = head;
string str = cur->getData();
return str;
}
string LinkedList::last()
{
Node *cur = new Node;
cur = tail;
string str = cur->getData();
return str;
}
void LinkedList::addFirst(string x)
{
Node *temp = new Node;
temp->setData(x);
temp->setNextPtr(head);
head = temp;
}
void LinkedList::addLast(string x)
{
Node *temp = new Node;
temp->setData(x);
temp->setNextPtr(NULL);
if (head == NULL)
{
head = temp;
tail = temp;
temp = NULL;
}
else
{
tail->setNextPtr(temp);
tail = temp;
}
}
void LinkedList::removeFirst()
{
Node *temp = new Node;
temp = head;
head->setNextPtr(tail->getNextPtr());
delete temp;
}
#include <string>
#include <iostream>
#include "LinkedListNode.h"
using namespace std;
int main(int argc, const char * argv[]) {
// insert code here...
std::cout << "Hello, World! ";
int a = 3;
string s = "M";
cout << s << a;
s = s + to_string(a);
cout << s;
LinkedList myList;
cout << myList.size();
myList.deleteHead();
myList.add("1");
myList.add("2");
myList.add("3");
myList.add("4");
myList.addHead("11");
myList.addHead("22");
myList.addHead("33");
myList.add_pos(-1, "55");
cout << " Size..." << myList.size() << endl;
myList.add_pos(5, "55");
cout << myList.to_string();
cout << " Delelte Head.. " << myList.deleteHead();
cout << " Size..." << myList.size() << endl;
cout << myList.to_string();
cout << " Delete Tail.. " << myList.deleteTail();
cout << " Size..." << myList.size() << endl;
cout << myList.to_string();
cout << " Delete at position... " << myList.delete_pos(3);
cout << " Size..." << myList.size() << endl;
cout << myList.to_string();
cout << endl;
cout << myList.isEmpty()<<endl;
cout << myList.to_string()<<endl;
cout << myList.first()<<endl;
myList.add("77");
cout << myList.to_string() << endl<<endl<<endl;
cout << myList.first()<<endl;
cout << myList.to_string() << endl;
cout<< myList.last();
cout << endl;
myList.addFirst("100");
cout << myList.to_string()<<endl<<endl;
cout << "Adding element to the end: " << endl;
myList.addLast("27");
cout << myList.to_string()<< endl;
myList.removeFirst();
cout << myList.to_string();
system("pause");
return 0;
}
Project Linked Lists A. Convert the singly linked list class that we implemented in the lab -or the one under content- to have a circularly linked list. Set the next reference of the tail node of the singly linked list to reference back to the head of the list. Modify all the public behaviors of the singly linked list to match the modification of the circularly linked list • Define method rotate(), this method moves the first element to the end of the list B. Implement a doubly linked list: In a doubly linked list each node keeps an explicit reference "prev" to the node before it and a reference “next" to the node after it. Add special “dummy” nodes at both ends of the list, name them header & trailer: these are sentinels node, they don't store elements of the primary sequence. When using sentinel nodes, an empty list is initialized so that the next field of the header points to the trailer, and the prev field of the trailer points to the header; the remaining fields of the sentinels are irrelevantExplanation / Answer
1) CONVERSION OF SINGLE LINKED LIST TO CIRCULAR LINKED LIST
add the following function code to the single linked list program to convert it to circular linked list
void convertToCircularLL(struct node *head){
if(head == NULL){
printf(" HEAD MUST NOT BE NULL");
return INT_MIN;
}
struct node *temp = head;
while(temp->next != NULL){
temp = temp->next;
}
temp->next = head;
}
EXPLANATION: in the above code the last noe of the list that is pointing to NULL is made to point to HEAD node of the list thus it becomes the circular linked list
2) IMPLEMENTATION OF DOUBLY LINKED LIST:
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct doublenode
{
int data;
struct node * next;
struct node * prev;
}
void dcreate(struct doublenode **s,int num)
{
struct doublenode *r, *q = *s;
if(*s==NULL)
{
*s=malloc(sizeof(struct doublenode));
(*s)->prev = NULL;
(*s)->data=num;
(*s)->next=NULL;
}
else{
while(q->next!=NULL)
q=q->next;
r=malloc(sizeof(struct doublenode));
r->data=num;
r->next=NULL;
r->prev=q;
q->next=r;
}
}
void addatbeginnning(struct doublenode **s, int num)
{
struct doublenode *q;
q= malloc(sizeof(struct doublenode));
q->prev=NULL;
q->data=num;
q->next=*s;
(*s)->prev=q;
*s=q;
}
void addafter(struct doublenode *q,int loc,int num)
{
struct dnode *temp;
int i;
for(i=0;i<loc;i++)
{
q=q->next;
if(q==NULL)
{
printf(" there are less than %d elements",loc);
retrun;
}
}
q=q->prev;
temp=malloc(sizeof(struct doublenode));
temp->data=num;
temp->prev=q;
temp->next=q->next;
temp->next->prev=temp;
q->next=temp;
}
void deletenode(struct doublenode **s,int num)
{
struct doublenode *q=*s;
while(q!=NULL)
{
if(q->data==num)
{
if(q==*s)
{
*s=(*s)->next;
(*s)->prev=NULL;
}
else
{
if(q->next==NULL)
q->prev->next=NULL;
else{
q->prev->next=q->next;
q->next->prev=q->prev;
}
free(q);
}
return;
}
q=q->next;
}
printf("%d not found",num);
}
void display(struct doublenode *q)
{
printf(" ");
while(q!=NULL)
{
printf("%2d ",q->next);
}
}
void main(){
int ch;
int num,loc;
doublenode q;
switch(ch);
{
case 1: dcreate(q,num);
break;
case 2: addatbeginning(q,num);
break;
case 3:addafter(q,loc,num);
break;
case 4:delete(q,num);
break;
case 5:display(q,num);
break;
}
getch();
}
void convertToCircularLL(struct node *head){
if(head == NULL){
printf(" HEAD MUST NOT BE NULL");
return INT_MIN;
}
struct node *temp = head;
while(temp->next != NULL){
temp = temp->next;
}
temp->next = head;
}
EXPLANATION: in the above code the last noe of the list that is pointing to NULL is made to point to HEAD node of the list thus it becomes the circular linked list
2) IMPLEMENTATION OF DOUBLY LINKED LIST:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.