C++ Linked List I really need help implementing those codes below by implementin

Question

C++ Linked List

I really need help implementing those codes below by implementing an ordered linked list either ascending or descending. In addition to the usual insert() and delete() methods, please also implement union(), intersection() and reverse() methods. Ordered linked lists are great for getting max or min values in O(1) time (based on the ordering). Hence, you will also write print_topk() and print_bottomk() methods. And also, please create a main file to test these methods.

//node.h

//node.cpp

//order_linkedlist.h

//ordered_linkedlist.cpp

Explanation / Answer

Hi

Here are all the required functions that need to be implemented :

Code:

/* Program to insert in a sorted list */
#include<stdio.h>
#include<stdlib.h>

/* Link list node */
struct Node
{
int data;
struct Node* next;
};

/* function to insert a new_node in a list. Note that this
function expects a pointer to head_ref as this can modify the
head of the input linked list (similar to push())*/
void sortedInsert(struct Node** head_ref, struct Node* new_node)
{
struct Node* current;
/* Special case for the head end */
if (*head_ref == NULL || (*head_ref)->data >= new_node->data)
{
new_node->next = *head_ref;
*head_ref = new_node;
}
else
{
/* Locate the node before the point of insertion */
current = *head_ref;
while (current->next!=NULL &&
current->next->data < new_node->data)
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}

void deleteList(struct Node** head_ref)
{
/* deref head_ref to get the real head */
struct Node* current = *head_ref;
struct Node* next;

while (current != NULL)
{
next = current->next;
free(current);
current = next;
}

/* deref head_ref to affect the real head back
in the caller. */
*head_ref = NULL;
}

struct Node *getUnion(struct Node *head1, struct Node *head2)
{
struct Node *result = NULL;
struct Node *t1 = head1, *t2 = head2;

// Insert all elements of list1 to the result list
while (t1 != NULL)
{
push(&result, t1->data);
t1 = t1->next;
}

// Insert those elements of list2 which are not
// present in result list
while (t2 != NULL)
{
if (!isPresent(result, t2->data))
push(&result, t2->data);
t2 = t2->next;
}

return result;
}

/* Function to get intersection of two linked lists
head1 and head2 */
struct Node *getIntersection(struct Node *head1,
struct Node *head2)
{
struct Node *result = NULL;
struct Node *t1 = head1;

// Traverse list1 and search each element of it in
// list2. If the element is present in list 2, then
// insert the element to result
while (t1 != NULL)
{
if (isPresent(head2, t1->data))
push (&result, t1->data);
t1 = t1->next;
}

return result;
}

/* Function to reverse the linked list */
static void reverse(struct Node** head_ref)
{
struct Node* prev = NULL;
struct Node* current = *head_ref;
struct Node* next;
while (current != NULL)
{
next = current->next;  
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}

/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert */

/* A utility function to create a new node */
struct Node *newNode(int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));

/* put in the data */
new_node->data = new_data;
new_node->next = NULL;

return new_node;
}

/* Function to print linked list */
void printList(struct Node *head)
{
struct Node *temp = head;
while(temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
}

/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
struct Node *new_node = newNode(5);
sortedInsert(&head, new_node);
new_node = newNode(10);
sortedInsert(&head, new_node);
new_node = newNode(7);
sortedInsert(&head, new_node);
new_node = newNode(3);
sortedInsert(&head, new_node);
new_node = newNode(1);
sortedInsert(&head, new_node);
new_node = newNode(9);
sortedInsert(&head, new_node);
printf(" Created Linked List ");
printList(head);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.