Develop a C++ code, which performs the following operations on a doubly link list:

Question

Function 1: Delete the middle node if the length of the list is odd.

Function 2: Delete the middle 2 nodes if the length of the list is even.

Function 3: Update the value of 2nd node

Function 4: Insert a new node at 2nd position

Answer 1

using namespace std;

#include <iostream>

#include <string.h>

#include <stdlib.h>

typedef struct _ListNode

{

int x;

struct _ListNode * next;

struct _ListNode * prev;

} * TListNode;

#define LIST_NODE_SIZE (sizeof(struct _ListNode))

typedef struct _List

{

TListNode first;

TListNode last;

TListNode mid;

int count;

} * TList;

void List_Init(TList list)

{

list->first = list->last = list->mid = NULL;

list->count=0;

}

int List_Push(TList list, int num)

{

TListNode newNode = (TListNode) malloc(LIST_NODE_SIZE);

newNode->x = num;

int iReturn=0;

if (newNode!=NULL)

{

if (list->count==0)

{

list->first = list->last = list->mid = newNode;

list->count=1;

list->last->next = list->first;

list->last->prev= list->first;

list->first->next = list->last;

list->first->prev= list->last;

list->mid->next = list->last;

list->mid->prev = list->first;

}

else

{

newNode->next = list->first;

newNode->prev = list->last;

list->last->next = newNode;

list->last = list->last->next;

list->last->next = list->first;

list->first->prev = list->last;

list->count++;

if (list->count%2==0)

{

list->mid = list->mid->next;

}

}

}

else

{

iReturn=-1;

}

return(iReturn);

}

List_Dump(TList list, char * strMsg)

{

if (strMsg!=NULL)

{

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

cout << strMsg << endl;

}

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

TListNode cur = list->first;

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

{

cout << cur->x << endl;

cur=cur->next;

}

}

List_DumpBackwards(TList list, char * strMsg)

{

if (strMsg!=NULL)

{

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

cout << strMsg << endl;

}

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

TListNode cur = list->last;

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

{

cout << cur->x << endl;

cur=cur->prev;

}

}

int List_Push2nd(TList list, int num)

{

int iReturn=0;

if (list->count<2)

{

List_Push(list,num);

}

else

{

TListNode newNode = (TListNode) malloc(LIST_NODE_SIZE);

newNode->x = num;

if (newNode!=NULL)

{

TListNode cur = list->first->next;

newNode->next = list->first->next;

newNode->prev = list->first;

list->first->next = newNode;

cur->prev = newNode;

list->count++;

}

}

return(iReturn);

}

List_Update(TList list, int num, int iIndexPos)

{

TListNode cur = list->first;

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

{

cur = cur->next;

}

cur->x = num;

}

double List_Median(TList list)

{

double dblMedianReturn;

if (list->count%2==0)

{

dblMedianReturn = (list->mid->x*1.0f + list->mid->prev->x * 1.0f)/2;

}

else

{

dblMedianReturn = list->mid->prev->x;

}

return(dblMedianReturn);

}

void List_RemoveMedian(TList list)

{

TListNode beforePtr;

TListNode afterPtr;

TListNode killPtr1;

TListNode killPtr2;

TListNode killPtr;

//We'll ASSUME the list has enough nodes to do this sp that mid is set

if (list->count>1)

{

if (list->count%2==0)

{

beforePtr = list->mid->prev->prev;

killPtr1 = list->mid->prev;

killPtr2 = list->mid;

afterPtr = list->mid->next;

free(killPtr1);

free(killPtr2);

beforePtr->next = afterPtr;

afterPtr->prev = beforePtr;

list->count -=2;

list->mid = beforePtr;

}

else

{

beforePtr = list->mid->prev->prev;

killPtr = list->mid->prev;

afterPtr = list->mid;

free(killPtr);

beforePtr->next = afterPtr;

afterPtr->prev = beforePtr;

list->count--;

list->mid = (list->count%2==0) ? afterPtr : beforePtr;

}

}

}

int main()

{

struct _List myList;

List_Init(&myList);

List_Push(&myList,10);

List_Push(&myList,12);

List_Push(&myList,15);

List_Push(&myList,18);

List_Push(&myList,21);

List_Push(&myList,24);

List_Push(&myList,27);

List_Push(&myList,30);

List_Push(&myList,32);

List_Push(&myList,33);

List_Dump(&myList,(char*)"Original");

cout << "mid = " << myList.mid->x << endl;

cout << List_Median(&myList) << endl;

List_DumpBackwards(&myList,(char*)"Backwards");

cout << "mid = " << myList.mid->x << endl;

cout << List_Median(&myList) << endl;

List_Push2nd(&myList,11);

List_Dump(&myList,(char*)"Push 2nd");

cout << "mid = " << myList.mid->x << endl;

cout << List_Median(&myList) << endl;

List_Update(&myList,12,1);

List_Dump(&myList,(char*)"Update 2nd");

cout << "mid = " << myList.mid->x << endl;

cout << List_Median(&myList) << endl;

List_Push(&myList,35);

List_Push(&myList,36);

List_Dump(&myList,(char*)"couple more pushes");

cout << "mid = " << myList.mid->x << endl;

cout << List_Median(&myList) << endl;

List_RemoveMedian(&myList);

List_Dump(&myList,(char*)"disembowelment");

cout << "mid = " << myList.mid->x << endl;

cout << List_Median(&myList) << endl;

List_Push(&myList,37);

List_Push(&myList,38);

List_Push(&myList,39);

List_Push(&myList,40);

List_RemoveMedian(&myList);

List_Dump(&myList,(char*)"few more pushed & disembowelment #2");

cout << "mid = " << myList.mid->x << endl;

cout << List_Median(&myList) << endl;

}