Doubly Linked List without deque please help!

[acorea20]

I used a pointer to a vector to create a list of elements to insert into a doubly linked list, however, I cannot get the add_back and add_front functions in Blist to implements the same operations a deque push_front/push_back would.

#include "exceptions.h"
#include <vector>

const int B_NODE_CAPACITY = 16;

// TODO: create a template class called BNode that represents a
// doubly-linked node holding a fixed-capacity array of
// B_NODE_CAPACITY elements.

template <typename ELEMENT>
class BNode {
public:
BNode(BNode<ELEMENT>* prev, const ELEMENT e, BNode<ELEMENT>* next) {
_prev = prev;
_next = next;
Node_list = new vector<ELEMENT>(B_NODE_CAPACITY);
Node_list->insert(Node_list->begin(), e);
}

~BNode() {
delete Node_list;
}

ELEMENT get_frontElement() {
return Node_list->front();
}

ELEMENT get_backElement() {
return Node_list->back();
}

ELEMENT get_element(int index) {
return Node_list->at(index);
}

int get_size() {
return Node_list->size();
}

BNode<ELEMENT>* prev() {
return _prev;
}

BNode<ELEMENT>* next() {
return _next;
}

void set_prev(BNode<ELEMENT>* prev) {
_prev = prev;
}

void set_next(BNode<ELEMENT>* next) {
_next = next;
}

void set_element( int index, ELEMENT e) {
Node_list->insert(Node_list->begin() + index, e);
}

private:
std::vector<ELEMENT> *Node_list;
BNode<ELEMENT> *_prev, *_next;

void check_index(int i) {
if ((i < 0) || (i >= B_NODE_CAPACITY))
throw IndexException(B_NODE_CAPACITY, i);
}
};

template <typename ELEMENT>
class BList {
public:
BList() {
_header = new BNode<ELEMENT>(NULL, ELEMENT(), NULL);
_trailer = new BNode<ELEMENT>(_header, ELEMENT(), NULL);
_header->set_next(_trailer);
_size = 0;
}

~BList() {
clear();
delete _header;
delete _trailer;
}

bool is_empty() {
return (_header->next() == _trailer);
}

int size() {
// TODO: re-implement this function to operate on BNode objects
// instead of just using std::deque
return _size;
//return _deque.size();
}

ELEMENT front() throw(UnderflowException) {
check_nonempty();
return _header->next()->get_frontElement();
}

ELEMENT back() throw(UnderflowException) {
if (is_empty())
throw UnderflowException();
return _trailer->prev()->get_backElement();
}

void add_front(ELEMENT e) {
if ((_size == B_NODE_CAPACITY) || (_size == 0)) {
add_before(_header->next(), e);
}
else
{
for (int i = 0; i < B_NODE_CAPACITY; i++) {
if (_header->next()->get_element(i) == 0)
{
_header->next()->set_element(i, e);
}
}
}
_size++;
}

void add_back(ELEMENT e) {
if ((_size == B_NODE_CAPACITY) || (_size == 0)) {
add_before(_trailer, e);
}
else {
for (int i = 0; i < B_NODE_CAPACITY; i++) {
if (_trailer->prev()->get_element(i) == 0)
{
_trailer->prev()->set_element( i, e);
}
}
}
_size++;
}

void remove_front() throw(UnderflowException) {
if (is_empty())
throw UnderflowException();
remove(_header->next());
_size--;
}

void remove_back() throw(UnderflowException) {
if (is_empty())
throw UnderflowException();
remove(_trailer->prev());
_size--;
}

ELEMENT get(int index) throw(IndexException) {
// TODO: re-implement this function to operate on BNode objects
// instead of just using std::deque
check_index(index);
return _elements->get_element(index);
}

void set(int index, ELEMENT e) throw(IndexException) {
// TODO: re-implement this function to operate on BNode objects
// instead of just using std::deque
check_index(index);
_elements->set_element(index, e);
}

void clear() {
while (!is_empty())
remove_front();
}

private:
// TODO: change this from a std::deque to head and tail pointers
// into a doubly-linked list of BNode objects.

BNode<ELEMENT> *_header, *_trailer;
BNode<ELEMENT> *_elements;
int _size;

void add_before(BNode<ELEMENT>* where, const ELEMENT e) {
BNode<ELEMENT>* new_node = new BNode<ELEMENT>(where->prev(), e, where);
where->prev()->set_next(new_node);
where->set_prev(new_node);
}

void remove(BNode<ELEMENT>* where) {
where->prev()->set_next(where->next());
where->next()->set_prev(where->prev());
delete where;
}

void check_nonempty() throw(UnderflowException) {
if (is_empty())
throw UnderflowException();
}

void check_index(int index) throw(IndexException) {
if (!((index >= 0) && (index < size())))
throw IndexException(size(), index);
}

};

[kbw]

however, I cannot get the add_back and add_front functions in Blist to implements the same operations a deque push_front/push_back would.

I don't really understand what this means. But I do have some comments on your code.

First of all, DLL stuff is Windows specific, you should post the question there. But it's no big deal, we can take a look at it here.

When writing a DLL header file, don't use inline functions in the way you have done. Allocations will be done in the client code, not in the DLL, so you used to run into problems of using the wrong heap. Microsoft started using a common heap for such things, but the problem still exists, memory isn't the only resource, that's why garbage collection is not helpful in general.

You're passing objects by value, causing unnecessary and possibly expensive copies.

Don't use exception specifications. They're more trouble than they're worth as C++ code can be used in mixed language environments where the specification cannot be enforced.

Please format your code using the code format tags.

[acorea20]

I'm trying to create functions that have the same effect that a deque.push_back and deque.push_front would without using a deque. I'm using a doubly linked list and storing a vector of elements into each node.

[kbw]

Cool. You've worked out that you need to use a queue data structure, but for some reason you are allowed to use STL vector and list but not deque. Is that correct?

A STL list is a double threaded linked list. But before I go any futher, are you allowed to use std::list?

[acorea20]

Yeah that's right.

[kbw]

Sorry about all this, sort of. Let's look at fixing your code.

First of all, you need a linked list of anything, not a a vector of anything. That's an unnecessary restriction. It's normal to treat it as a struct rather than a class with all those members. It'll only be accessible by the wrapper class.

So that becomes:

template <typename ELEMENT>
struct BNode {
	ELEMENT> *data;
	BNode<ELEMENT> *_prev, *_next;

	BNode(const ELEMENT& in) :
		data(in), prev(nullptr), next(nullptr) {
	}
};

BList constructor should just initialise header, trailer and size to nullptr/zero. They shouldn't allocate stuff. Also, the class has a pointer used for traversing the list. That means that only one thing can iterate the class at a time.

If you step back and think, you'll recall that all you need is a queue. You don't need a doublely theaded linked list, you don't need all those members, you don't need a linked list; just implement a queue.

So it'll just like your list, but just implement what you need:
constructors/destructor
push_back()
pop_front()
empty()

Change the node class to just have one pointer, rather than two.

I think that's about it.