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; } } |