C++ Notes: Linked Lists - Example Using Nodes

This is an example of a singly linked linear list. It is in three files, list_node.h, main.cpp, and list_node.cpp. This illustrates the general idea of linked lists done in the classical, procedural style, characterized by struct for a node. Any node can be treated as the beginning of linked list.

The OOP approach is different, as characterized by the STL list type - the user sees only a single list object and iterators. The use of the pointers is completely hidden from the user.

The header file

  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 

//--- list1/list_node.h -- Fred Swartz 2001-12-13
// There should really be a list class with member functions.
// But that is for a later example.

#ifndef LIST_NODE_H
#define LIST_NODE_H

#include <iostream>
using namespace std;

struct ListNode {
    ListNode* next;
    int       data;
};
     

//=============================================== prototypes
void      clear(ListNode* somelist);
void      printList(ListNode* start);
ListNode* readList(istream& input); 
ListNode* readListLIFO(istream& input);

#endif

A simple main program

This main program simply reads, writes, and deletes a list.

  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 

//--- list1/main.cpp - Linked List example -- Fred Swartz 2001-12-13

#include <iostream>  
using namespace std;

#include "list_node.h"

//=============================================== main
int main() {

    ListNode* list1;

    list1 = readList(cin); // Read list elements
    cout << endl;
    printList(list1);      // Print list elements
    clear(list1);          // Delete list elements

    system("PAUSE");       // Keep console window open
    return 0;
}//end main
.

The implementation file

  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 62 

//--- list1/list_node.cpp  -- Fred Swartz 2001-12-13
#include <iostream>
using namespace std;

#include "list_node.h"

//=============================================== printList
void printList(ListNode* start) {
    for (; start!=NULL; start=start->next) {
        cout << start->data << " ";
    }
    cout << endl;
}//end printList


//============================================ readListLIFO
ListNode* readListLIFO(istream& input) {  
    ListNode* front = NULL;  // first element
    int x;

    while (input >> x) {
        ListNode* newnode = new ListNode();
        newnode->data = x;
        newnode->next = front;  // Points to rest of list

        front = newnode;        // Make this new head
    }
    return front;
}//end readListLIFO


//=============================================== readList
ListNode* readList(istream& input) {
    ListNode* front = NULL;  // first element
    ListNode* back  = NULL;  // last element
    int x;

    while (input >> x) {
        ListNode* newnode = new ListNode();
        newnode->data = x;
        newnode->next = NULL;   // this is the end

        if (front == NULL) {
            front = newnode;    // if this is the first node
            back  = newnode;    // it's both the front and back.
        }else{
            back->next = newnode; // prev end points to newnode
        }
        back = newnode;         // new end of list
    }
    return front;
}//end readList


//=============================================== clear
void clear(ListNode* somelist) {
    ListNode* temp;  // stores next pointer before delete
    for (ListNode* p = somelist; p != NULL; p = temp) {
        temp = p->next;  // must save before delete
        delete p;
    }
}//end clear

Extensions

To practice using this approach, here are some possible extensions to this code.

  1. Write a function to add all the elements of a list. Use the prototype 
       int sum(ListNode* someList);
  2. Change this into a doubly-linked list. This is a list where each node has two pointers, one to the previous element, and one to the next element. This is probably the most common kind of linked list because it permits easy deletion, something which is hard in a singly linked list.
  3. How would you implement functions like the STL functions push_front and push_back?