This assignment you will be implementing a fancy linked list, called a doubly linked list. 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.

Implement the linked list and test the functionality of it using tests. Remember, you need to implement all of the functions supported by the class, including the `sort` function.

As you are writing your functions, read the instructions and think of how you would test that functions while you are writing it. Write your Test first and then implement your functions. Try running your test and then fixing your issues.

`doubly_linked_list::sort()` will sort the items in a linked list using insertion sort. 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.

### Lab Functions that you haven't seen before `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.

NOTE - Keep track of your edge cases: empty, 1 item, 2+ items - You need to update 3 nodes every time you insert or remove: the previous node, the selected node, and the next node.

header file

#ifndef CMPE126S18_LABS_DOUBLY_LINKED_LIST_H #define CMPE126S18_LABS_DOUBLY_LINKED_LIST_H #include "node.h" #include #include

namespace lab6{ class doubly_linked_list{ lab6::node *head; lab6::node *tail; public: doubly_linked_list(); doubly_linked_list(int input); doubly_linked_list(std::vector vector_input); doubly_linked_list(const doubly_linked_list &original); ~doubly_linked_list();

int get_data(unsigned position); std::vector 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); }; }

#endif //CMPE126S18_LABS_DOUBLY_LINKED_LIST_H

cpp file

#include "../inc/doubly_linked_list.h"

namespace lab6{ doubly_linked_list::doubly_linked_list() { }

doubly_linked_list::doubly_linked_list(int input) { }

doubly_linked_list::doubly_linked_list(std::vector vector_input) { }

doubly_linked_list::doubly_linked_list(const doubly_linked_list &original) { }

doubly_linked_list::~doubly_linked_list() { }

int doubly_linked_list::get_data(unsigned position) { }

std::vector doubly_linked_list::get_set(unsigned position_from, unsigned position_to) { }

unsigned doubly_linked_list::size() { }

bool doubly_linked_list::is_empty() { }

void doubly_linked_list::append(int input) { }

void doubly_linked_list::insert(int input, unsigned int location) { }

void doubly_linked_list::remove(unsigned location) { }

doubly_linked_list doubly_linked_list::split(unsigned position) { }

doubly_linked_list doubly_linked_list::split_set(unsigned position_1, unsigned position_2) { }

void doubly_linked_list::swap(unsigned position_1, unsigned position_2) { }

void doubly_linked_list::swap_set(unsigned location_1_start, unsigned location_1_end, unsigned location_2_start, unsigned location_2_end) {

}

void doubly_linked_list::sort() { // Implement Insertion Sort }

doubly_linked_list doubly_linked_list::operator+(const doubly_linked_list &rhs) const { }

doubly_linked_list& doubly_linked_list::operator=(const doubly_linked_list &rhs) { }

doubly_linked_list& doubly_linked_list::operator+=(const doubly_linked_list &rhs) { }

bool doubly_linked_list::operator==(const doubly_linked_list &rhs) { }

std::ostream &operator<<(std::ostream &stream, doubly_linked_list &RHS) { }

std::istream &operator>>(std::istream &stream, doubly_linked_list &RHS) { }

}