Data Structure- Linked List Question C++ (Computer Science)

Question

Q1. Write the C++ code to implement the List class. You need to write only Insert( ), delete( ), display() and search( ) functions of the list class.

Q2. In the List class created in Q1, create a function named “Reverse” that reverse all the elements in the list.

Answer 1

using namespace std;

#include <iostream>

#include <string.h>

#include <stdlib.h>

#include <stdio.h>

#define MAX_BUFF_SIZE (1024)

typedef struct _TListNode

{

char * data;

struct _TListNode * next;

} * TListNode;

#define LIST_NODE_SIZE (sizeof(struct _TListNode))

typedef

class List

{

protected:

TListNode first;

TListNode last;

int count;

public:

List() { first=last=NULL; count=0; }

int GetCount() { return(count); }

Push(char * newDataStr)

{

//allocates and copies the data

TListNode newListNode = (TListNode) malloc(LIST_NODE_SIZE);

int N = strlen(newDataStr)+1;

newListNode->data = (char*)malloc(N);

memset(newListNode->data,0,N);

memcpy(newListNode->data,newDataStr,N);

newListNode->next = NULL;

if (count==0)

{

first=last=newListNode;

}

else

{

last->next = newListNode;

last = last->next;

}

count++;

}

int LinearSearchFind(char * strTarget)

{

int iReturn=-1;

TListNode cur = first;

for (int iLoop=0; iLoop<count; iLoop++)

{

if (strcmp(cur->data,strTarget)==0)

{

iReturn=iLoop;

break;

}

cur=cur->next;

}

return(iReturn);

}

int RemoveDelete(char*strTarget)

{

strcpy(strTarget,first->data);

TListNode tempPtr = first;

first = first->next;

free(tempPtr->data);

free(tempPtr);

tempPtr=NULL;

count--;

}

Output( char * strMsg=NULL)

{

TListNode cur = first;

if (strMsg!=NULL)

{

cout << "**********************************" << endl;

cout << strMsg << endl;

}

cout << "**********************************" << endl;

for (int iLoop=0; iLoop<count; iLoop++)

{

cout << cur->data << endl;

cur = cur->next;

}

}

List(const List & list)

{

TListNode cur = list.first;

first=last=NULL; count=0;

for (int iLoop=0; iLoop<list.count; iLoop++)

{

this->Push(cur->data);

cur=cur->next;

}

}

~List()

{

TListNode tempPtr=first;

for (int iLoop=0; iLoop<count; iLoop++)

{

tempPtr=first;

first=first->next;

if (tempPtr->data!=NULL)

{

free(tempPtr->data);

tempPtr->data = NULL;

}

free(tempPtr);

}

first=last=NULL;

count=0;

}

int IndexerGetAtIndex(char * dataBuff,int iIndexPos, int n)

{

int iReturn=0;

if (iIndexPos>-1 && iIndexPos<count)

{

TListNode cur = first;

for (int iLoop=0; iLoop<iIndexPos; iLoop++)

{

cur = cur->next;

}

strncpy(dataBuff,cur->data,n);

}

else

{

iReturn=-1;

}

return(iReturn);

}

Reverse(List *reverseList)

{

char dataBuff[MAX_BUFF_SIZE];

for (int iLoop=count-1; iLoop>=0; iLoop--)

{

memset(dataBuff,0,MAX_BUFF_SIZE);

IndexerGetAtIndex(dataBuff,iLoop,MAX_BUFF_SIZE);

reverseList->Push(dataBuff);

}

}

//swaps the data at first position with that at iIndexPos

int Swap(int iIndexPos)

{

int iReturn=0;

if (iIndexPos>0 && iIndexPos<count)

{

//points at the element at position iIndexPos

TListNode cur = first;

for (int iLoop=0; iLoop<iIndexPos; iLoop++) { cur=cur->next; }

//creates temp buffer with sufficient size

int N = max(

strlen(first->data),

strlen(cur->data)

);

char * tempBuff = (char*)malloc(N);

//swap occurs here

strcpy(tempBuff,cur->data); //stores the element at iIndexPos in temp buffer

//copies the first element to iIndexPos

free(cur->data);

cur->data = (char*)malloc(strlen(first->data)+1);

strcpy(cur->data,first->data);

//copies element in temp buffer (which was at iIndexPos) to first

free(first->data);

first->data = (char*)malloc(N);

strcpy(first->data,tempBuff);

//cleans up

free(tempBuff);

}

else

{

iReturn=-1;

}

return(iReturn);

}

/* NOTE: You can then remove the Kth element in the list by calling:

Swap(k);

RemoveDelete();

*******************************/

} * TList;

main()

{

char str[25];

List list;

strcpy(str,"CANTELOUPE"); list.Push(str);

strcpy(str,"GRAPES"); list.Push(str);

strcpy(str,"WATERMELON"); list.Push(str);

strcpy(str,"STRAWBERRY"); list.Push(str);

strcpy(str,"PINEAPPLE"); list.Push(str);

strcpy(str,"GRAPES");

int iIndexPos = list.LinearSearchFind(str);

cout << iIndexPos << endl;

list.RemoveDelete(str); cout << str << " deleted..." << endl;

list.Swap(3);

list.Output();

List reverseList;

list.Reverse(&reverseList);

reverseList.Output((char*)"REVERSE");

}