fork download
copy 
  1. /**
  2.  * A sample code of Creating C++ linked lists,
  3.  * Including definitions the list node class and linked list class,
  4.  * and how to create a blank linked list and a one-node linked list.
  5.  *
  6.  * Outline: understand the definition and structure of the linked
  7.  * list and build a linked list based on it.
  8.  */
  9.  
  10. #include <iostream>
  11. #include <cstddef>
  12.  
  13. using std::cout;
  14. using std::endl;
  15.  
  16. /*
  17.  A linked list is a list constructed using pointers. It is not fixed in
  18.  size and could grow and shrink while the program is running.
  19.  
  20.  A typical defination of list nodes contains at least two parts, both the
  21.  content or date of each element and the pointer to the next element,
  22.  which is shown in the figure below.
  23.  
  24.  +---------+
  25.  |  Data   | -----> holds the data of this element in the list.
  26.  +---------+
  27.  | pointer | -----> is a pointer to the next element in the list.
  28.  +---------+
  29.  
  30.  ***Attention***:
  31.  The pointer holds the address of the next element, not the address of the
  32.  data in the next element, even though they are the same in value sometimes.
  33.  And It should be set to NULL while acting as the last node of the list.
  34.  
  35.  
  36.  Implementation of the single linked list:
  37.  +---------+    --->+---------+    --->+---------+
  38.  |  Data   |    |   |  Data   |    |   |  Data   |
  39.  +---------+    |   +---------+    |   +---------+
  40.  | pointer |-----   | pointer |-----   | pointer |
  41.  +---------+        +---------+        +---------+
  42.  */
  43.  
  44.  
  45. /* definition of the list node class */
  46. class Node
  47. {
  48.     friend class LinkedList;
  49. private:
  50.     int _value; /* data, can be any data type, but use integer for easiness */
  51.     Node *_pNext; /* pointer to the next node */
  52.  
  53. public:
  54.     /* Constructors with No Arguments */
  55.     Node(void)
  56.     : _pNext(NULL)
  57.     { }
  58.  
  59.     /* Constructors with a given value */
  60.     Node(int val)
  61.     : _value(val), _pNext(NULL)
  62.     { }
  63.  
  64.     /* Constructors with a given value and a link of the next node */
  65.     Node(int val, Node* next)
  66.     : _value(val), _pNext(next)
  67.     {}
  68.  
  69.     /* Getters */
  70.     int getValue(void)
  71.     { return _value; }
  72.  
  73.     Node* getNext(void)
  74.     { return _pNext; }
  75. };
  76.  
  77. /* definition of the linked list class */
  78. class LinkedList
  79. {
  80. private:
  81.     /* pointer of head node */
  82.     Node *_pHead;
  83.     /* pointer of tail node */
  84.     Node *_pTail;
  85.  
  86. public:
  87.     /* Constructors with No Arguments */
  88.     LinkedList(void);
  89.     /* Constructors with a given value of a list node */
  90.     LinkedList(int val);
  91.     /* Destructor */
  92.     ~LinkedList(void);
  93.  
  94.     /* Traversing the list and printing the value of each node */
  95.     void traverse_and_print();
  96. };
  97.  
  98. LinkedList::LinkedList()
  99. {
  100.     /* Initialize the head and tail node */
  101.     _pHead = _pTail = NULL;
  102. }
  103.  
  104. LinkedList::LinkedList(int val)
  105. {
  106.     /* Create a new node, acting as both the head and tail node */
  107.     _pHead = new Node(val);
  108.     _pTail = _pHead;
  109. }
  110.  
  111. LinkedList::~LinkedList()
  112. {
  113.     /*
  114.      * Leave it empty temporarily.
  115.      * It will be described in detail in the example "How to delete a linkedlist".
  116.      */
  117. }
  118.  
  119. void LinkedList::traverse_and_print()
  120. {
  121.     Node *p = _pHead;
  122.  
  123.     /* The list is empty? */
  124.     if (_pHead == NULL) {
  125.         cout << "The list is empty" << endl;
  126.         return;
  127.     }
  128.  
  129.     cout << "LinkedList: ";
  130.     /* A basic way of traversing a linked list */
  131.     while (p != NULL) { /* while there are some more nodes left */
  132.         /* output the value */
  133.         cout << p->_value;
  134.         /* The pointer moves along to the next one */
  135.         p = p->_pNext;
  136.     }
  137.     cout << endl;
  138. }
  139.  
  140. int main(int argc, const char * argv[])
  141. {
  142.     /* Create an empty list */
  143.     LinkedList list1;
  144.     cout << "Created an empty list named list1." << endl;
  145.     /* output the result */
  146.     cout << "list1:" << endl;
  147.     list1.traverse_and_print();
  148.  
  149.     /* Create a list with only one node */
  150.     LinkedList list2(10);
  151.     cout << "Created a list named list2 with only one node." << endl;
  152.     /* output the result */
  153.     cout << "list2:" << endl;
  154.     list2.traverse_and_print();
  155.  
  156.     return 0;
  157. }
  158.  
Compilation error #stdin compilation error #stdout 0s 3272KB
comments (?)
stdin
copy 
link list
compilation info 
In file included from /usr/include/c++/4.9/cstddef:45:0,
                 from prog.cpp:11:
prog.cpp:55:17: error: expected identifier before '__null'
     Node _pNext(NULL){ };
                 ^
prog.cpp:55:17: error: expected ',' or '...' before '__null'
prog.cpp:55:24: error: 'Node Node::_pNext(int)' conflicts with a previous declaration
     Node _pNext(NULL){ };
                        ^
prog.cpp:51:11: note: previous declaration 'Node* Node::_pNext'
     Node *_pNext; /* pointer to the next node */
           ^
prog.cpp: In constructor 'Node::Node(int)':
prog.cpp:59:20: error: class 'Node' does not have any field named '_pNext'
     : _value(val), _pNext(NULL)
                    ^
prog.cpp: In constructor 'Node::Node(int, Node*)':
prog.cpp:64:20: error: class 'Node' does not have any field named '_pNext'
     : _value(val), _pNext(next)
                    ^
prog.cpp: In member function 'Node* Node::getNext()':
prog.cpp:72:14: error: cannot convert 'Node::_pNext' from type 'Node (Node::)(int)' to type 'Node*'
     { return _pNext; }
              ^
prog.cpp: In member function 'void LinkedList::traverse_and_print()':
prog.cpp:133:11: error: cannot convert 'Node::_pNext' from type 'Node (Node::)(int)' to type 'Node*'
         p = p->_pNext;
           ^
stdout
copy 
Standard output is empty
https://ideone.com/D9IPri
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!