# C++: Data Structures: Lists - Example 2

Here is another implementation of a classical linked list. `struct` has been replaced by `class` with some constructors. This is not similar to the STL `<list>` class, which is an object containining pointers to the front (head) and back (tail) elements.

      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
     63
     64
     65
     66
     67
     68
     69
     70
     71
     72
     73
     74
     75
     76
     77
     78
     79
     80
     81
     82
     83
     84
     85
     86
     87
     88
     89
     90
     91
     92
     93
     94
     95
     96
     97
     98
     99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    // linked-list-2.cpp - Fred Swartz 2000-12-05, ...
    //   Singly linked list with node defined as class.
    //   Functions are not class members because apply to,
    //   entire list, individual elements.
    //   This is a classical implementation, not like STL.

    #include <iostream>
    using namespace std;

    class NodeType {
      public:
        NodeType();
        NodeType(int v);
        NodeType(int v, NodeType* ptr);
        int info;
        NodeType* next;
      private:
    }; //end constructor

    //=================================== NodeType constructor
    NodeType::NodeType() {
        info = 0;
        next = NULL;
    }//end constructor

    //=================================== NodeType constructor
    NodeType::NodeType(int v) {
        info = v;
        next = NULL;
    }//end constructor

    //=================================== NodeType constructor
    NodeType::NodeType(int v, NodeType* ptr) {
        info = v;
        next = ptr;
    }//end  constructor

    //================================================ prototypes
    NodeType* readListLIFO();
    NodeType* readList();
    NodeType* readSortedList();
    void printList(NodeType* aList);
    NodeType* insertSorted(NodeType* list, int val);

    //====================================================== main
    int main() {
        NodeType* myList;

        myList = readSortedList();

        cout << "Sorted list" << endl;
        printList(myList);

        cin.clear(); char xx; cin >> xx; // keep window
        return 0;
    }//end main

    //============================================== readListLIFO
       // Reads ints from cin into a list,
       // but in reverse order!
    NodeType* readListLIFO() {
        NodeType* head = NULL;
        int x;
        while (cin >> x) {
           head = new NodeType(x, head);
        }
        return head;
    }//end readListLIFO

    //================================================== readList
       // Reads ints from cin into list
    NodeType* readList() {
        NodeType* head = NULL;
        NodeType* tail = NULL;
        int x;
        while (cin >> x) {
            NodeType* newNode = new NodeType(x, NULL);
            if (head == NULL) {
                // This is the first element
                head = newNode; // this is start of list
                tail = head;    // and also the end
            } else {
                // Insert after tail
                tail->next = newNode; // add to end
                tail = newNode;       // it's the new end
            }
        }
        return head;
    }//end readList

    //=========================================== readSortedList
    NodeType* readSortedList() {
        NodeType* head = NULL;
        int x;
        while (cin >> x) {
           head = insertSorted(head, x);
        }
        return head;
    }//end readSorted

    //============================================ insertSorted
       // Makes new node and inserts it in sorted order.
    NodeType* insertSorted(NodeType* list, int val) {
        NodeType* item = new NodeType(val);

        if (list == NULL) {
            // list is empty, new item becomes new list
            return item;

        } else {
            // go thru list looking for the right spot
            NodeType* prev = NULL;
            for (NodeType* p = list; p != NULL; p = p->next) {
                if (val < p->info) {
                    if (prev == NULL) {
                        // this is the head of the list
                        return new NodeType(val, list);
                    } else {
                        // insert in middle
                        prev->next = new NodeType(val, p);
                        return list;
                    }
                }
                prev = p; // make this the previous element
            }
            // must belong on the end
            prev->next = new NodeType(val, NULL);
        }
        return list;
    }//end insertSorted

    //=============================================== printList
    void printList(NodeType* aList) {
        for (NodeType* p = aList; p != NULL; p = p->next) {
            cout << p->info << endl;
        }
    }//end printList