Question

Can you please do this in C asap. Promise to leave a awesome rating! Thank you in advance. Question and template below

Instructions-

LINKED LIST

In C
'objects' => structs
(struct - collection of data, not methods)
Linked List

Collection of objects which are all connected to each other

Each Object 'points' to the next item in the list

Node (struct) ' O '
- data
- nextNode

Our linked list will store data(structs containing integers) in order from smallest to largest

Generate one node for each data point
each node will point to the next node in the list
each node data point will be less than (or equal to) the 'next' node that it points to
Truths:
nothing points to HEAD
each node points to node of equal or larger value
HEAD smallest data point
last largest data point
last points to NULL

HEAD

'O'
3
-> 'O'
5
-> 'O'
8
-> 'O'
9
-> NULL

& = ADDRESS
// * creates Pointer variable
struct node* nodePtr;
// * also dereferences Pointer
*nodePtr
// look familiar?
obj.field

// put it all together
(*nodePtr).field

// allocating memory

malloc( sizeof(struct node) )
free( ptr )

TEMPLATE for assignment-

#include

#include

struct node

{

// data field

int data;

// nextNode field

struct node* nextNode;

};

/*

struct node myNode;

printf("%d", myNode.data);

printf("%p", myNode.nextNode);

*/

// FUNCTION - allocate and create a new Node

// Precondition - data exists

// Postcondition - Node allocated, and ptr returned

struct node* createNode(int newData)

{

// must allocate memory for each node

// because each nodes lifetime is longer than this function

// *note must manually deallocate (free) each node when program is complete

// memory for these nodes

// must outlive this function call

// myObj() => malloc()

// ~myObj() => free()

struct node* np = malloc(sizeof(struct node));

// set the fields

(*np).data = newData;

(*np).nextNode = NULL;

// return the pointer to this new Node

return np;

}

// FUNCTION - insert new Node into our linked List

// New Node inserted ahead of larger nodes

// Precondition - ptr to list containing 0 or more nodes

// Postcondition - after insertion list is always sorted

struct node* insertNode(struct node* list, int data)

{

// defining our reference data

// new node to be inserted

struct node* np;

// previous node

struct node* prev = NULL;

// current beginning of LL

struct node* head = list;

// current node

struct node* lp = list;

// create a new Node

...

//check if this is our first node

if(...)

{

//start the list with this node since it's empty

...

...

//return new head pointer, since list was empty now head is np

return ...;

}

// MOVE TO WHILE LOOP

// while list pointer isn't at the end

while( ... )

{

// if our current node data is larger than the new node data

// insert into list before current node

if( ... )

{

// insert new node into list by settings it's next node to current node

...

// check if this is NOT the beginning of the list

if(...)

{

// it's not, so remember to set last node to point to new node

...

}

else

{

// it is! cool, set head to new node

...

}

// send back the beginning of the list

return ...;

}

// what's the case for this 'else'?

// ...

else

{

// current node was smaller than new node

// lets check if we're at the end yet

if( ... )

{

// add new node to end of the list

...

// head didn't change, but return it anyway because we're done here

return ...;

}

// move the loop along becaue we aren't at the end of the list yet

...

...

}

}

// list ended for some reason...

// probably shouldn't ever reach this code...

// if we inserted the new node into the list, we would have returned head already...

// hmm...

fprintf(stderr, "ERROR: WE DIDN'T INSERT OUR NEW NODE FOR SOME REASON...");

return head;

}

// FUNCTION - call free on every node in our list from back to front

// Precondition - ptr to list containing 0 or more nodes

// Postcondition - return 0 on all nodes mem freed

// FREE EACH POINTER FROM END OF LIST TO FRONT

int freeListMemory(struct node* list)

{

// COMPLETE THIS ENTIRE FUNCTION

// *hint hint*

// free()

//

//

//on success

return 0;

}

//

// COMPLETE

// DO NOT EDIT

//

int main()

{

// insert create 7 data points

int data1 = 6;

int data2 = 4;

int data3 = 3;

int data4 = 1;

int data5 = 5;

int data6 = 7;

int data7 = 2;

// create POINTER to front of list

struct node *ptrHead;

ptrHead = NULL;

// insert each data point into the list

ptrHead = insertNode(ptrHead, data1);

ptrHead = insertNode(ptrHead, data2);

ptrHead = insertNode(ptrHead, data3);

ptrHead = insertNode(ptrHead, data4);

ptrHead = insertNode(ptrHead, data5);

ptrHead = insertNode(ptrHead, data6);

ptrHead = insertNode(ptrHead, data7);

// create list pointer for our loop

struct node *lp = ptrHead;

// Here we ASSUME list is non-empty

while( lp != NULL)

{

// print out the data for this node

printf("%d\n", (*lp).data);

// set the list pointer to the next node in the list

lp = (*lp).nextNode;

}

// REMEMBER TO FREE ALL LIST POINTERS

// FREE EACH POINTER FROM END OF LIST TO FRONT (reverse order)

// CALL freeListMemory()

int freed = freeListMemory(ptrHead);

return freed;

}

Answer 1

#include<stdio.h>
#include<malloc.h>

struct node

{

// data field

int data;

// nextNode field

struct node* nextNode;

};

/*

struct node myNode;

printf("%d", myNode.data);

printf("%p", myNode.nextNode);

*/

// FUNCTION - allocate and create a new Node

// Precondition - data exists

// Postcondition - Node allocated, and ptr returned

struct node* createNode(int newData)

{

// must allocate memory for each node

// because each nodes lifetime is longer than this function

// *note must manually deallocate (free) each node when program is complete

// memory for these nodes

// must outlive this function call

// myObj() => malloc()

// ~myObj() => free()

struct node* np = malloc(sizeof(struct node));

// set the fields

(*np).data = newData;

(*np).nextNode = NULL;

// return the pointer to this new Node

return np;

}

// FUNCTION - insert new Node into our linked List

// New Node inserted ahead of larger nodes

// Precondition - ptr to list containing 0 or more nodes

// Postcondition - after insertion list is always sorted

struct node* insertNode(struct node* list, int data)

{

// defining our reference data

// new node to be inserted

struct node* np;

// previous node

struct node* prev = NULL;

// current beginning of LL

struct node* head = list;

// current node

struct node* lp = list;

// create a new Node

np=createNode(data);

//check if this is our first node

if(head==NULL)

{

//start the list with this node since it's empty

head=np;

//return new head pointer, since list was empty now head is np

return head;

}

// MOVE TO WHILE LOOP

// while list pointer isn't at the end

while( lp!=NULL )

{

// if our current node data is larger than the new node data

// insert into list before current node

if( lp->data > np->data )

{

// insert new node into list by settings it's next node to current node

np->nextNode=lp;

// check if this is NOT the beginning of the list

if(head!=lp)

{

// it's not, so remember to set last node to point to new node

prev->nextNode=np;

}

else

{

// it is! cool, set head to new node

head=np;

}

// send back the beginning of the list

return head;

}

// what's the case for this 'else'?

//  ////if our current node data is smaller than the new node data

else

{

// current node was smaller than new node

// lets check if we're at the end yet

if( lp->nextNode==NULL )

{

// add new node to end of the list

lp->nextNode=np;

// head didn't change, but return it anyway because we're done here

return head;

}

// move the loop along becaue we aren't at the end of the list yet

prev=lp;

lp=lp->nextNode;

}

}

// list ended for some reason...

// probably shouldn't ever reach this code...

// if we inserted the new node into the list, we would have returned head already...

// hmm...

fprintf(stderr, "ERROR: WE DIDN'T INSERT OUR NEW NODE FOR SOME REASON...");

return head;

}

// FUNCTION - call free on every node in our list from back to front

// Precondition - ptr to list containing 0 or more nodes

// Postcondition - return 0 on all nodes mem freed

// FREE EACH POINTER FROM END OF LIST TO FRONT

int freeListMemory(struct node* list)

{

// COMPLETE THIS ENTIRE FUNCTION

// *hint hint*

// free()

//

//

//on success
free(list);

return 0;

}

//

// COMPLETE

// DO NOT EDIT

//

int main()

{

// insert create 7 data points

int data1 = 6;

int data2 = 4;

int data3 = 3;

int data4 = 1;

int data5 = 5;

int data6 = 7;

int data7 = 2;

// create POINTER to front of list

struct node *ptrHead;

ptrHead = NULL;

// insert each data point into the list

ptrHead = insertNode(ptrHead, data1);

ptrHead = insertNode(ptrHead, data2);

ptrHead = insertNode(ptrHead, data3);

ptrHead = insertNode(ptrHead, data4);

ptrHead = insertNode(ptrHead, data5);

ptrHead = insertNode(ptrHead, data6);

ptrHead = insertNode(ptrHead, data7);



// create list pointer for our loop

struct node *lp = ptrHead;

// Here we ASSUME list is non-empty

while( lp != NULL)

{

// print out the data for this node

printf("%d\n", (*lp).data);

// set the list pointer to the next node in the list

lp = (*lp).nextNode;

}

// REMEMBER TO FREE ALL LIST POINTERS

// FREE EACH POINTER FROM END OF LIST TO FRONT (reverse order)

// CALL freeListMemory()

int freed = freeListMemory(ptrHead);

return freed;

}