C++ noob reporting. I'm working on implementing a doubly linked list using two separate classes: one class, called node
, containing your standard doubly linked list parameters, and another class, called dList
, that contains functions to alter my doubly linked list. Here is my node
class:
class node {
public:
node *prev;
node *next;
int key;
char type;
};
and here is my dList
class:
class dList {
private:
node *head; // dummy head
node *tail; // dummy tail
public:
dList() { // default constructor, creates empty list
cout << "in default constructor" << endl; // to debug
head = nullptr;
tail = nullptr;
}
// destructor
~dList() {
cout << "in destructor" << endl; // to debug
node *ptr = head;
while (ptr != nullptr) {
delete ptr;
ptr = ptr->next;
}
tail = nullptr;
}
// searches list for occurence of int parameter and returns pointer to node containing key
node *search(int k);
// outputs all keys that have type equal to character parameter, front to back
void find(char t);
// parametrized constructor, initialize list w/ contents of arrays
dList(int arrayNums[], char arrayChars[], int size);
// creates new node at front of list
void addFront(int k, char t);
// creates new node at back of list
void addBack(int k, char t);
// moves node pointed to by parameter to front of list
void moveFront(node* ptr);
// moves node pointed to by parameter to back of list
void moveBack(node* ptr);
// outputs first int elements of list, starting at front or back depending on char parameter
void out(int num, char = 'f');
// splits list in two
node *split(node* headRef);
// merges two linked lists
node *mergeLists(node* first, node* second);
// performs mergeSort on linked list
node *mergeSort(node* headRef);
// peforms an O(NlogN) sort on list; list should be in increasing order based on integer key
void sort();
};
I have all of my functions figured out, besides the sort()
function and all of the functions related to it (split, mergeLists, mergeSort
). I'm mainly looking for critiques and improvements. If y'all could look over my code and help me optimize it (condensing and deleting unnecessary lines), as well as help me make sure I'm using pointers correctly, it'd be much appreciated!
Below are my declared functions (excluding any sort
related ones):
// parametrized constructor, initialize list w/ contents of arrays
dList::dList(int arrayNums[], char arrayChars[], int size) {
node *newNode = nullptr;
//cout << "parametrized constructor called" << endl;
for (int i = 0; i < size; i++) {
//cout << "in for loop" << endl;
if (head == nullptr) {
//cout << "in first if statement" << endl;
newNode = new node;
newNode->key = arrayNums[i];
newNode->type = arrayChars[i];
newNode->prev = nullptr;
newNode->next = nullptr;
head = newNode;
tail = head;
}
else {
//cout << "in else statement" << endl;
newNode = new node;
newNode->key = arrayNums[i];
newNode->type = arrayChars[i];
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}
}
}
void dList::addFront(int k, char t) { // creates new node at front of list
node *newNode = new node;
newNode->key = k;
newNode->type = t;
if (head != nullptr) {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
else {
newNode->prev = nullptr;
newNode->next = nullptr;
head = newNode;
tail = nullptr;
}
}
void dList::addBack(int k, char t) { // creates new node at back of list
node *newNode = new node;
newNode->key = k;
newNode->type = t;
node *ptr = head;
if (ptr != nullptr) {
while (ptr->next != nullptr) {
ptr = ptr->next;
}
ptr->next = newNode;
newNode->next = nullptr;
newNode->prev = ptr;
}
else {
newNode->next = nullptr;
newNode->prev = nullptr;
ptr = newNode;
tail = ptr;
}
}
void dList::moveFront(node *ptr) { // moves node pointed to by parameter to front of list
//node *tempHead = head;
//node *tempTail = tail;
if (ptr == head) {
return;
}
else if (ptr == tail) {
ptr->prev->next = nullptr;
tail = ptr->prev;
}
else {
ptr->prev->next = ptr->next;
ptr->next->prev = ptr->prev;
}
head->prev = ptr;
ptr->next = head;
ptr->prev = nullptr;
head = ptr;
}
void dList::moveBack(node *ptr) { // moves node pointed to by parameter to back of list
//node *tempHead = head;
//node *tempTail = tail;
if (ptr == tail) {
return;
}
else if (ptr == head) {
head = ptr->next;
tail->next = ptr;
ptr->prev = tail;
ptr->next = nullptr;
tail = ptr;
}
else {
ptr->prev->next = ptr->next;
ptr->next->prev = ptr->prev;
tail->next = ptr;
ptr->prev = tail;
tail = ptr;
}
}
// searches list for occurence of int parameter and returns pointer to node containing key
node *dList::search(int k) {
node *ptr = head;
while (ptr->next != nullptr) {
if (ptr->key == k) {
return ptr;
}
else {
ptr = ptr->next;
}
}
return nullptr;
}
// outputs all keys that have type equal to character parameter, front to back
void dList::find(char t) {
node *ptr = head;
while (ptr->next != nullptr) {
if (ptr->type == t) {
cout << ptr->key << " " << ptr->type << " ";
ptr = ptr->next;
}
else {
ptr = ptr->next;
}
}
}
// outputs first num elements of list, starting at front or back depending on char parameter
void dList::out(int num, char side) {
cout << "out() called" << endl;
if (side == 'b') {
node *ptr = tail;
for (int i = 0; i < num; i++) {
cout << ptr->key << " " << ptr->type << " ";
ptr = ptr->prev;
}
}
else {
node *ptr = head;
for (int i = 0; i < num; i++) {
cout << ptr->key << " " << ptr->type << " ";
ptr = ptr->next;
}
}
}
And here is my main.cpp file I've been using to test:
#include <iostream>
using namespace std;
#include "dList.cpp"
#define SMALL 200
#define MAX 100000
#define ROUNDS 100
int main(){
int i, x[MAX];
char ch[MAX];
for(i=0;i<SMALL;i++) {
x[i] = (2*SMALL)-i;
ch[i] = 'a' + (i % 26);
}
dList A(x,ch,SMALL), B;
A.out(10);
node *tmp = A.search(2*SMALL-8);
A.moveFront(tmp);
A.out(10);
A.moveBack(tmp);
A.out(10);
A.find('b');
A.sort();
A.out(10);
A.out(10,'b');
A.addBack(500,'d');
A.addFront(501,'z');
A.out(10);
A.out(10,'b');
B.addFront(1,'a');
B.addBack(2,'b');
B.out(2);
for(int j=0; j<ROUNDS; j++){
cout << endl << "round " << j << endl;
for(i=0;i<MAX;i++) {x[i] = 2*MAX-i; ch[i] = 'a'+ (i%26);}
dList A(x,ch,MAX);
node *tmp = A.search(2*MAX-8);
A.moveFront(tmp);
A.moveBack(tmp);
A.sort();
A.out(10);
A.out(10,'b');
}
}
(As a bonus, if y'all could give me tips on how to implement mergesort for a doubly linked list, I would LOVE it!)
Thanks y'all!