# 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`?