Linked lists (without classes)

Here we will review the basics of linked lists, implemented using structs, pointers, and functions.

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