LINK LISTS C++ PROGRAMMING

Question

Write down a C++ program to implement the link list in the following way.

a) Create an array taking 10 values from the user.

b) Create a link list and fill it (insert nodes) with the array values.

c) Display the link list

d) Run the 9 commands given in the table on slide 9.

e) Create functions for the following and implement these in order

(i) Insert a new node in front of the list and display the list.

(ii) Insert a new node at the end of the list and display the list

(iii) Delete first node from the list and display the list.

(iv) Search for a value in the list (user entered).

Note: The program must be well structured and properly commented.

Answer 1

using namespace std;

#include <iostream>

#include <stdlib.h>

#define POSITION_FIRST (1)

#define POSITION_LAST (0)

typedef struct _TListNode

{

int key;

struct _TListNode * next;

} * TListNode;

#define LIST_NODE_SIZE ( sizeof(struct _TListNode))

typedef struct _TLinkedList

{

TListNode head;

TListNode tail;

int count;

} * TLinkedList;

// creates empty list

void LinkedList_Init(TLinkedList linkedList)

{

linkedList-> head= linkedList->tail=NULL;

linkedList->count=0;

}

//returns -1 if malloc fails

int LinkedList_Push( TLinkedList linkedList, int n, bool posFlag=true)

{

int iReturn=0;

TListNode newListNode = (TListNode) malloc(LIST_NODE_SIZE);

if (newListNode != NULL) //good malloc

{

newListNode->key = n; //copies the data

newListNode->next=NULL;

if (linkedList->count==0) //list is empty

{

linkedList->head= linkedList->tail = newListNode;

linkedList->count=1;

}

else if (linkedList->count==1) //only one node

{

if (posFlag) //inserts at head

{

linkedList->head=newListNode;

linkedList->head->next=linkedList->tail;

}

else //inserts at tail

{

linkedList->tail = newListNode;

linkedList->head->next=linkedList->tail;

}

linkedList->count=2;

}

else //there are 3 or more nodes

{

if (posFlag)

{

//inserts at head

newListNode->next = linkedList->head;

linkedList->head = newListNode;

}

else

{

//inserts at tail

linkedList->tail->next = newListNode;

linkedList->tail = linkedList->tail->next;

}

linkedList->count++;

}

//newListNode=NULL;

}

else

{

iReturn=-1;

}

return(iReturn);

}

//displays the list in order

void LinkedList_Display( TLinkedList linkedList, char * strMsg=NULL)

{

TListNode cur = linkedList->head;

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

if (strMsg!=NULL)

{

cout << strMsg << endl;

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

}

for (int iLoop=0; iLoop<linkedList->count; iLoop++)

{

cout << cur->key << endl;

cur = cur->next;

}

}

//removes node from head or tail based on posFlag; returns the integer data of the deleted node

// or -1 if the list is empty

int LinkedList_Pop( TLinkedList linkedList, bool posFlag=true)

{

int iReturn=-1;

if (linkedList->count>0) //not allowed to pop an empty list

{

if (linkedList->count==1) //removes the one and only node

{

iReturn = linkedList->head->key;

free(linkedList->head);

linkedList->head = linkedList->tail = NULL;

linkedList->count=0;

}

else if (linkedList->count==2) // there are 2 nodes

{

if (posFlag) // removes the head node

{

iReturn=linkedList->head->key;

free(linkedList->head);

linkedList->head = linkedList->tail;

}

else //removes the tail node

{

iReturn = linkedList->tail->key;

free(linkedList->tail);

linkedList->tail = linkedList->head;

}

linkedList->count=1;

}

else // there are 3 or more nodes

{

if (posFlag) //removes from head

{

iReturn = linkedList->head->key;

TListNode tempPtr = linkedList-> head;

linkedList->head = linkedList->head->next;

free(tempPtr);

}

else //removes from tail

{

//linear searches for the node PRIOR to the tail

TListNode tempPtr = linkedList->head;

while (tempPtr->next != linkedList->tail) { tempPtr= tempPtr->next; }

//removes from tail

iReturn = linkedList->tail->key;

free(linkedList->tail);

linkedList->tail = tempPtr;

linkedList->tail->next=NULL;

}

linkedList->count--;

}

}

return(iReturn);

}

//returns the position of the node containing the integer key, or -1 if not found

int LinkedList_LinearSearch (TLinkedList linkedList, int nKey)

{

int iReturn=-1;

TListNode cur =linkedList-> head;

for (int iLoop=0; iLoop<linkedList->count; iLoop++)

{

if ((cur->key)==nKey)

{

iReturn = iLoop;

break;

}

cur = cur->next;

}

return(iReturn);

}

int LinkedList_IndexerGetIndexAt( TLinkedList linkedList, int iIndexPos)

{

int iReturn=-1;

TListNode cur = linkedList->head;

if ((iIndexPos>=0) && (iIndexPos<linkedList->count))

{

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

{

cur=cur->next;

}

iReturn = cur->key;

}

}

void LinkedList_Destroy(TLinkedList linkedList)

{

int N=linkedList->count;

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

{

LinkedList_Pop(linkedList,POSITION_LAST);

}

LinkedList_Init(linkedList);

}

int main()

{

struct _TLinkedList linkedList;

LinkedList_Init(&linkedList);

int A[10];

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

{

cout << " Input the value :>";

cin >> A[iLoop];

LinkedList_Push(&linkedList,A[iLoop],POSITION_LAST);

}

LinkedList_Display(&linkedList);

struct _TLinkedList linkedListRev;

LinkedList_Init(&linkedListRev);

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

{

LinkedList_Push(&linkedListRev,A[iLoop]);

}

LinkedList_Display(&linkedListRev,(char *)"Backwards");

cout << " Popped : " << LinkedList_Pop(&linkedList) << endl;

cout << " Popped : " << LinkedList_Pop(&linkedList,POSITION_LAST) << endl;

cout << " Popped : " << LinkedList_Pop(&linkedListRev,POSITION_FIRST) << endl;

cout << " Popped : " << LinkedList_Pop(&linkedListRev,POSITION_LAST) << endl;

LinkedList_Display(&linkedList,(char*)" List after 2 pops ");

LinkedList_Display(&linkedListRev,(char*)" Rev List after 2 pops ");

cout << "Linear Search results:" << endl;

cout << LinkedList_LinearSearch(&linkedList,12) << endl; //3

cout << LinkedList_LinearSearch(&linkedList,10) << endl; //-1

cout << LinkedList_LinearSearch(&linkedList,4) << endl; //0

cout << LinkedList_LinearSearch(&linkedList,28) << endl; //7

LinkedList_Destroy(&linkedList);

LinkedList_Destroy(&linkedListRev);

}