This assignment you will be implementing a fancy linked list, called a doubly li
ID: 3741423 • Letter: T
Question
This assignment you will be implementing a fancy linked list, called a doubly linked list. The only difference between this linked list, and the linked list that you created last lab is that the nodes have pointers to both next and prev. This means that you can now traverse the list in either direction.
Lab Instructions
Implement each of the functions to perform the necessary actions outlined in the .h files or here.
You will implementing some supplementary functions for this class that will help you manipulate this linked list in interesting ways.
doubly_linked_list::sort() will sort the items in a linked list using insertion sort. Refer to the wikipedia article on insertion sort for more information on how this sorting algorithm works. Remember, you will be implementing this in a linked list and not an array. Get creative, because the Wikipedia article talks specifically about performing this sort on an array. You will need to understand how to translate this algorithm to use a linked list instead.
You may need to create auxiliary functions to complete tasks, or to avoid copy and pasting repetitive code. Do not make these class functions. These should only appear in the .cpp file
Don't move data in the node from private to public. We placed this here deliberately. For all of the functions and classes, don't change anything.
void swap(unsigned position_1, unsigned position_2): Swap the node located at position 1 with the node located at position 2.
void swap_set(unsigned location_1_start, unsigned location_1_end, unsigned location_2_start, unsigned location_2_end): Swap the subset of nodes starting at position_1_start and ending at position_1_end with the nodes starting at position_2_start to position_2_end. These locations are inclusive.
doubly_linked_list doubly_linked_list::split(unsigned position): Split the doubly linked list at position, with position being the head of the second linked list. Truncate the original linked list and return the split off linked list.
void doubly_linked_list::insert(int input, unsigned int location = 0): This inserts a node at the location provided. Note that if you don't give it a location to insert the node, it will insert it at the beginning of the linked_list.
doubly_linked_list operator+(const doubly_linked_list rhs) const: Append the right doubly linked list to the right doubly linked list and return that new doubly linked list object.
doubly_linked_list operator=(const doubly_linked_list rhs): Copy the right doubly linked list into left doubly linked list
doubly_linked_list operator+=(const doubly_linked_list rhs): Append an entire doubly linked list to the end of an existing doubly linked list
bool operator==(const doubly_linked_list rhs): Checks to see if two doubly linked lists have the same values in the same positions.
node.h
doubly_linked_list.h
Explanation / Answer
node.h
class node{
int data;
public:
node* next;
node* prev;
explicit node(int input_data) : data(input_data), next(), prev(){};
int get_data(){return data;};
};
doubly_linked_list.h
class doubly_linked_list{
lab6::node *head;
lab6::node *tail;
public:
doubly_linked_list();
doubly_linked_list(int input);
doubly_linked_list(std::vector<int> vector_input);
doubly_linked_list(const doubly_linked_list &original);
~doubly_linked_list();
int get_data(unsigned position);
std::vector<int> get_set(unsigned position_from, unsigned position_to);
unsigned size();
bool is_empty();
void append(int input);
void insert(int input, unsigned location = 0);
void remove(unsigned location);
doubly_linked_list split(unsigned position);
doubly_linked_list split_set(unsigned position_1, unsigned position_2);
void swap(unsigned position_1, unsigned position_2);
void swap_set(unsigned location_1_start, unsigned location_1_end, unsigned location_2_start, unsigned location_2_end);
void sort();
doubly_linked_list operator+(const doubly_linked_list &rhs) const;
doubly_linked_list& operator=(const doubly_linked_list &rhs);
doubly_linked_list& operator+=(const doubly_linked_list &rhs);
bool operator==(const doubly_linked_list &rhs);
friend std::ostream& operator<<(std::ostream& stream, doubly_linked_list& RHS);
friend std::istream& operator>>(std::istream& stream, doubly_linked_list& RHS);
};
#include<stdio.h>
#include<stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
struct Node* head; // global variable - pointer to head node.
//Creates a new Node and returns pointer to it.
struct Node* GetNewNode(int x) {
struct Node* newNode
= (struct Node*)malloc(sizeof(struct Node));
newNode->data = x;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
//Inserts a Node at head of doubly linked list
void InsertAtHead(int x) {
struct Node* newNode = GetNewNode(x);
if(head == NULL) {
head = newNode;
return;
}
head->prev = newNode;
newNode->next = head;
head = newNode;
}
//Inserts a Node at tail of Doubly linked list
void InsertAtTail(int x) {
struct Node* temp = head;
struct Node* newNode = GetNewNode(x);
if(head == NULL) {
head = newNode;
return;
}
while(temp->next != NULL) temp = temp->next; // Go To last Node
temp->next = newNode;
newNode->prev = temp;
}
//Prints all the elements in linked list in forward traversal order
void Print() {
struct Node* temp = head;
printf("Forward: ");
while(temp != NULL) {
printf("%d ",temp->data);
temp = temp->next;
}
printf(" ");
}
//Prints all elements in linked list in reverse traversal order.
void ReversePrint() {
struct Node* temp = head;
if(temp == NULL) return; // empty list, exit
// Going to last Node
while(temp->next != NULL) {
temp = temp->next;
}
// Traversing backward using prev pointer
printf("Reverse: ");
while(temp != NULL) {
printf("%d ",temp->data);
temp = temp->prev;
}
printf(" ");
}
int main() {
/*Driver code to test the implementation*/
head = NULL; // empty list. set head as NULL.
// Calling an Insert and printing list both in forward as well as reverse direction.
InsertAtTail(2); Print(); ReversePrint();
InsertAtTail(4); Print(); ReversePrint();
InsertAtHead(6); Print(); ReversePrint();
InsertAtTail(8); Print(); ReversePrint();
}