I am currently in a data-structures class. The professor will be providing a singly linked list. I wanted to make a doubly linked list to "learn" how to do it. I tested it and I think it works. After making it, I did compare it to other doubly linked lists but I still want to see if there is anything I am missing. Are there any other problems with it?
LinkNode Class:
#ifndef LINKNODE_H_
#define LINKNODE_H_
#include <iostream>
template<class E>
class LinkNode {
public:
E data;
LinkNode<E> *leftNode;
LinkNode<E> *rightNode;
LinkNode() {
}
LinkNode(E e) {
this->data = e;
}
~LinkNode() {
}
E getData() {
return data;
}
void setData(E e) {
this->data = e;
}
LinkNode<E> getLeftNode() {
return leftNode;
}
void setLeftNode(LinkNode<E> node) {
this->leftNode = node;
}
LinkNode<E> getRightNode() {
return rightNode;
}
void setRightNode(LinkNode<E> node) {
this->rightNode = node;
}
};
#endif /* LINKNODE_H_ */
LinkedList Class:
#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include "LinkNode.h"
template<class T>
class LinkedList {
private:
int size;
LinkNode<T> *firstNode;
LinkNode<T> *lastNode;
public:
LinkedList() {
firstNode = new LinkNode<T>();
lastNode = firstNode;
size = 0;
}
~LinkedList() {
}
void pushFront(T t) {
if (size == 0) {
pushBack(t);
return;
}
LinkNode<T> *linkNode = new LinkNode<T>(t);
linkNode->rightNode = firstNode;
firstNode->leftNode = linkNode;
firstNode = linkNode;
size++;
}
void pushBack(T t) {
LinkNode<T> *linkNode = new LinkNode<T>(t);
linkNode->leftNode = lastNode;
lastNode->rightNode = linkNode;
lastNode = linkNode;
if (size == 0) {
firstNode = lastNode;
}
size++;
}
T pollFirst() {
T t = firstNode->data;
firstNode = firstNode->rightNode;
size--;
return t;
}
T pollLast() {
T t = lastNode->data;
lastNode = lastNode->leftNode;
size--;
return t;
}
LinkNode<T> getFirstNode() {
return firstNode;
}
LinkNode<T> getLastNode() {
return lastNode;
}
T searchNode(T t) {
return t;
}
int Size() {
return size;
}
void printLinkedList() {
LinkNode<T> *temp = firstNode;
while (temp != NULL) {
std::cout << temp->data << "\t";
temp = temp->rightNode;
}
}
};
#endif /* LINKEDLIST_H_ */
New LinkedList Class:
#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include <iostream>
template<class T>
class LinkedList {
/**
* Private inner node class
*/
//Have to use new template. Does not run if I try to use T
template<class E>
class LinkNode {
public:
E data;
LinkNode<E> *leftNode;
LinkNode<E> *rightNode;
LinkNode() {
}
LinkNode(E e) {
this->data = e;
}
~LinkNode() {
}
};
private:
int size;
LinkNode<T> *firstNode;
LinkNode<T> *lastNode;
public:
LinkedList() {
firstNode = new LinkNode<T>();
/*
* Init left and right node to null to prevent exception.
*/
firstNode->leftNode = NULL;
firstNode->rightNode = NULL;
lastNode = firstNode;
size = 0;
}
~LinkedList() {
LinkNode<T> *linkNode = firstNode->rightNode;
while (linkNode != NULL) {
delete linkNode->leftNode;
linkNode = linkNode->rightNode;
}
}
void pushFront(T t) {
//the size is zero therefore we are really justing pushing to the back of the linked list
if (size == 0) {
pushBack(t);
return;
}
LinkNode<T> *linkNode = new LinkNode<T>(t);
linkNode->rightNode = firstNode;
firstNode->leftNode = linkNode;
firstNode = linkNode;
size++;
}
void pushBack(T t) {
LinkNode<T> *linkNode = new LinkNode<T>(t);
linkNode->leftNode = lastNode;
lastNode->rightNode = linkNode;
lastNode = linkNode;
if (size == 0) {
firstNode = lastNode;
}
size++;
}
T pollFirst() {
LinkNode<T> *temp = firstNode;
T t = firstNode->data;
firstNode = firstNode->rightNode;
delete temp;
size--;
return t;
}
T pollLast() {
LinkNode<T> *temp = lastNode;
T t = lastNode->data;
lastNode = lastNode->leftNode;
delete temp;
size--;
return t;
}
LinkNode<T> getFirstNode() {
return *firstNode;
}
LinkNode<T> getLastNode() {
return *lastNode;
}
int const Size() {
return size;
}
void const printLinkedList() {
LinkNode<T> *temp = firstNode;
while (temp != NULL) {
std::cout << temp->data << "\t";
temp = temp->rightNode;
}
}
};
#endif /* LINKEDLIST_H_ */
- Xubuntu 13.10
- GCC Compiler installed with sudo apt-get install g++
