Here's an old Doubly-Linked List class I wrote for a class nigh on 3 years back. I haven't really provided it the much needed "old once over" for which it desperately aches, for I leave that chore to act as your method of coherency allocation.
Code:
#ifndef _DOUBLYLINKEDLIST_H_
#define _DOUBLYLINKEDLIST_H_
#include <string>
using namespace std;
class ListException {
string _msg;
public:
ListException(const char *msg=NULL) {
_msg = (*msg == NULL) ? "Unknown list error" : msg;
}
const string& getMessage() const { return _msg; }
};
template <typename T>
class DoublyLinkedList {
template <typename T>
struct DoubleNode {
T data;
DoubleNode *next;
DoubleNode *prev;
DoubleNode() : next(NULL), prev(NULL), data() { }
};
typedef DoubleNode<T> Node;
Node *_head;
Node *_tail;
Node *_cur;
int _length;
void* locateItem(const T &item, int *counter);
public:
DoublyLinkedList();
virtual ~DoublyLinkedList();
bool isFull() const;
bool isEmpty() const;
void clear();
void insertItem(const T &item);
bool findItem(const T &item);
void deleteItem(const T &item);
void resetList();
T getNextItem();
};
//////////////////////////////////////////////////////////
// Implementation
template <typename T>
DoublyLinkedList<T>::DoublyLinkedList()
: _head(NULL), _tail(NULL), _cur(NULL), _length(0)
{
}
template <typename T>
DoublyLinkedList<T>::~DoublyLinkedList() {
clear();
}
///////////////////////////////////////////////////////////////
// name: locateItem
// params: item - the item to locate
//
// desc: searches list for item
// returns: pointer to node where item was located or NULL
//
template <typename T>
void* DoublyLinkedList<T>::locateItem(const T &item) {
//work our way in from both sides
Node *left = _head;
Node *right = _tail;
int leftIndex = 0;
int rightIndex = _length - 1;
while (leftIndex <= rightIndex) {
if (left->data == item)
return left;
if (right->data == item)
return right;
++leftIndex;
--rightIndex;
left = left->next;
right = right->prev;
}
return NULL;
}
/////////////////////////////////////////////
// name: isFull
// params: none
//
// desc: checks if memory is available for
// dynamic allocation of an item
// returns: true if full. false otherwise.
//
template <typename T>
bool DoublyLinkedList<T>::isFull() const {
try {//check if room exists for another node
Node *node = new Node;
delete node;
return false;
}
catch (bad_alloc exc) {
return true;
}
}
///////////////////////////////////////////
// name: isEmpty
// params: none
//
// desc: checks if list is empty
// returns: true if empty. false otherwise.
//
template <typename T>
bool DoublyLinkedList<T>::isEmpty() const {
return _head == NULL;
}
//////////////////////////////////////////
// name: clear
// params: none
//
// desc: clears all items from the list
// returns: nothing
//
template <typename T>
void DoublyLinkedList<T>::clear() {
//work our way in from both sides (faster)
Node *left = _head;
Node *right = _tail;
int leftIndex = 0;
int rightIndex = _length - 1;
//only while left is < right
while (leftIndex < rightIndex) {
_length -= 2;
Node *next = left->next;
Node *prev = right->prev;
delete left;
delete right;
++leftIndex;
--rightIndex;
left = next;
right = prev;
}
//if left and right point at the same node (center)
//make sure we only delete it once
if (leftIndex == rightIndex) {
--_length;
delete left;
}
_head = _tail = _cur = NULL;
}
//////////////////////////////////////////////////
// name: insertItem
// params: item - the item to insert
//
// desc: inserts an item at the end of the list
// returns: nothing
//
template <typename T>
void DoublyLinkedList<T>::insertItem(const T &item) {
if (isFull())
throw ListException("Insert into full list");
Node *newNode = new Node;
newNode->data = item;
if (_tail != NULL) {//if tail is pointing to a valid node
_tail->next = newNode;//set it's next ptr to the new node
newNode->prev = _tail;//set it's prev ptr to the previous tail
}
_tail = newNode;//now the new node IS the tail
if (_head == NULL) {//if the list is empty
_head = _tail;//point the head at the tail
_cur = _head;
}
++_length;
++_insCounter;//update stat counter
}
///////////////////////////////////////////
// name: findItem
// params: item - the item to find
//
// desc: searches list for item
// returns: true if found. false otherwise.
//
template <typename T>
bool DoublyLinkedList<T>::findItem(const T &item) {
return locateItem(item, &_srcCounter) != NULL;
}
//////////////////////////////////////
// name: deleteItem
// params: item - item to delete
//
// desc: deletes item from the list
// returns: nothing
//
template <typename T>
void DoublyLinkedList<T>::deleteItem(const T &item) {
if (isEmpty())
return;
//work our way in from both sides
Node *left = _head;
Node *right = _tail;
int leftIndex = 0;
int rightIndex = _length - 1;
while (leftIndex <= rightIndex) {
++_delCounter;//update stat counter
//update our pointer indices
++leftIndex;
--rightIndex;
if (left->data == item) {
--_length;
if (left == _head) {//if at head, repoint it to our next node
_head = left->next;
_head->prev = NULL;
}
if (left == _cur)//don't let _cur point at invalid memory
_cur = _cur->next;
if (left->prev != NULL)//point prev node's next to our node's next
left->prev->next = left->next;
if (left->next != NULL)//point next node's prev to our node's prev
left->next->prev = left->prev;
Node *next = left->next;//get next node before deleting
delete left;//now dealloc
left = next;//continue
}
else
left = left->next;
if (right->data == item) {
--_length;
if (right == _tail) {//if at tail, repoint at our prev node
_tail = right->prev;
_tail->next = NULL;
}
if (right == _cur)//don't let _cur point at invalid memory
_cur = _cur->prev;
if (right->next != NULL)//point next node's prev to our node's prev
right->next->prev = right->prev;
if (right->prev != NULL)//point prev node's next to our node's next
right->prev->next = right->next;
Node *prev = right->prev;//get prev node before deleting
delete right;//now dealloc
right = prev;//continue
}
else
right = right->prev;
}
}
/////////////////////////////////////////////
// name: resetList
// params: none
//
// desc: resets internal pointer to head
// returns: nothing
//
template <typename T>
void DoublyLinkedList<T>::resetList() {
_cur = _head;
}
/////////////////////////////////////////////
// name: getNextItem
// params: none
//
// desc: gets item internal pointer refers
// to then increments to the next
// returns: item internal pointer refers to
//
template <typename T>
T DoublyLinkedList<T>::getNextItem() {
if (_cur == NULL)//either empty list or resetList wasn't called
throw ListException("Retrieve next without reset");
T item = _cur->data;//get the data
_cur = _cur->next;//move to the next node
return item;
}
#endif //_DOUBLYLINKEDLIST_H_
(If any of the implementation seems odd or generally unusual, recall that it was written as defined by the instructor's direction.)
