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.
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 |
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 |
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 |
To practice using this approach, here are some possible extensions to this code.
int sum(ListNode* someList);
push_front
and push_back
?