The Node data type describes the contents of individual elements within the linked list, and the list operations are provided through a small set of operations:
Node* findNode(Node* front, float key); bool insertAfter(Node* &n, int key, float val); bool insertBefore(Node* &n, int key, float val); Node* findFront(Node* n); Node* findBack(Node* n); Node* remove(Node* &n); void printFrom(Node *n); |
A more detailed description of the Node type and the supported operations is given below.
// a linked list consists of a sequence of Nodes, each
// having a searchable key and an associated data value
//
// each node has a 'prev' pointer to the node before
// it and a 'next' pointer to the node behind it
//
// (so the front node's 'prev' pointer is null,
// and the back node's 'next' pointer is null)
struct Node {
int key;
float value;
Node *next, *prev;
};
// prints from the specified node to the back of the list
void printFrom(Node *n);
// starting with front, and following 'next' pointers,
// searches for the first node containing the specified key
// and returns a pointer to it
// return null if no such key is found
Node* findNode(Node* front, float key);
// creates and inserts a new node with specified key and value
// returning true if successful, false otherwise
// if n is null makes n point at the new node,
// otherwise inserts the new node between n and n's next
bool insertAfter(Node* &n, int key, float val);
// creates and inserts a new node with specified key and value
// returning true if successful, false otherwise
// if n is null makes n point at the new node,
// otherwise inserts the new node between n and n's next
bool insertBefore(Node* &n, int key, float val);
// if n is null returns null, otherwise finds the front
// list element by following the chain of prev pointers
// starting from n
Node* findFront(Node* n);
// if n is null returns null, otherwise finds the back
// list element by following the chain of next pointers
// starting from n
Node* findBack(Node* n);
// removes n from the list it is currently in,
// deletes n, sets n to null, and returns
// a pointer to the front of the remaining list
Node* remove(Node* &n);
|
A full implementation and sample application is given below.
... implementation discussion still to come ...
#include <iostream>
using namespace std;
// ==============================================================
// CONSTANTS AND DATATYPES
// ==============================================================
// a linked list consists of a sequence of Nodes, each
// having a searchable key and an associated data value
//
// each node has a 'prev' pointer to the node before
// it and a 'next' pointer to the node behind it
//
// (so the front node's 'prev' pointer is null,
// and the back node's 'next' pointer is null)
struct Node {
int key;
float value;
Node *next, *prev;
};
// ==============================================================
// FUNCTION PROTOTYPES
// ==============================================================
// prints from the specified node to the back of the list
void printFrom(Node *n);
// starting with front, and following 'next' pointers,
// searches for the first node containing the specified key
// and returns a pointer to it
// return null if no such key is found
Node* findNode(Node* front, float key);
// creates and inserts a new node with specified key and value
// returning true if successful, false otherwise
// if n is null makes n point at the new node,
// otherwise inserts the new node between n and n's next
bool insertAfter(Node* &n, int key, float val);
// creates and inserts a new node with specified key and value
// returning true if successful, false otherwise
// if n is null makes n point at the new node,
// otherwise inserts the new node between n and n's next
bool insertBefore(Node* &n, int key, float val);
// if n is null returns null, otherwise finds the front
// list element by following the chain of prev pointers
// starting from n
Node* findFront(Node* n);
// if n is null returns null, otherwise finds the back
// list element by following the chain of next pointers
// starting from n
Node* findBack(Node* n);
// removes n from the list it is currently in,
// deletes n, sets n to null, and returns
// a pointer to the front of the remaining list
Node* remove(Node* &n);
// ==============================================================
// MAIN APPLICATION
// ==============================================================
int main()
{
// use a Node* to track the front of the list, initially empty
Node* front = NULL;
// try a bunch of insert afters
for (int i = 0; i < 10; i++) {
float v = 1.5 * i;
if (insertAfter(front, i, v)) {
cout << "Inserted " << i << "," << v << endl;
} else {
cout << "Could not insert " << i << "," << v << endl;
}
}
// display the list
printFrom(front);
// keep removing until everything is gone
do {
Node *current = front;
if (current) {
cout << "going to remove " << current->key << "," << current->value << endl;
}
front = remove(current);
} while (front != NULL);
}
// ==============================================================
// FUNCTION IMPLEMENTATIONS
// ==============================================================
// starting with front, and following 'next' pointers,
// searches for the first node containing the specified key
// and returns a pointer to it
// return null if no such key is found
Node* findNode(Node* front, float key)
{
Node *current = front;
if (!current) {
return current;
}
while (current) {
if (current->key == key) {
return current;
} else {
current = current->next;
}
}
return current;
}
// creates and inserts a new node with specified key and value
// returning true if successful, false otherwise
// if n is null makes n point at the new node,
// otherwise inserts the new node between n and n's next
bool insertAfter(Node* &n, int key, float val)
{
Node *newest = new Node;
if (!newest) {
return false;
}
newest->key = key;
newest->value = val;
if (!n) {
n = newest;
n->prev = NULL;
n->next = NULL;
} else {
newest->next = n->next;
newest->prev = n;
n->next = newest;
if (newest->next) {
newest->next->prev = newest;
}
}
return true;
}
// creates and inserts a new node with specified key and value
// returning true if successful, false otherwise
// if n is null makes n point at the new node,
// otherwise inserts the new node between n and n's next
bool insertBefore(Node* &n, int key, float val)
{
Node *newest = new Node;
if (!newest) {
return false;
}
if (!n) {
n = newest;
n->prev = NULL;
n->next = NULL;
} else {
newest->prev = n->prev;
newest->next = n;
n->prev = newest;
if (newest->prev) {
newest->prev->next = newest;
}
}
return true;
}
// if n is null returns null, otherwise finds the front
// list element by following the chain of prev pointers
// starting from n
Node* findFront(Node* n)
{
if (!n) {
return n;
}
Node *front = n;
while (front->prev) {
front = front->prev;
}
return front;
}
// if n is null returns null, otherwise finds the back
// list element by following the chain of next pointers
// starting from n
Node* findBack(Node* n)
{
if (!n) {
return n;
}
Node *back = n;
while (back->next) {
back = back->next;
}
return back;
}
// removes n from the list it is currently in,
// deletes n, sets n to null, and returns
// a pointer to the front of the remaining list
Node* remove(Node* &n)
{
Node *front = NULL;
if (!n) {
return n;
} else if (!n->prev) {
front = n->next;
if (front) {
front->prev = NULL;
}
} else {
Node *after = n->next;
Node *before = n->prev;
before->next = after;
if (after) {
after->prev = before;
}
front = before;
while (front->prev) {
front = front->prev;
}
}
delete n;
n = NULL;
return front;
}
// prints from the specified node to the back of the list
void printFrom(Node *n)
{
while (n) {
cout << n->key << "," << n->value << endl;
n = n->next;
}
}
|