Let us look at some fundamental data structures which are just a collection of primitive data types. For example, an array of integers is a collection of integers, a string is a collection of characters, etc.

Here, we are interested in Linked Lists which are just a collection (list) made by linking together some data-types (node). The data-types themselves could be any primitive or a data-type formed of primitive types. For simplicity, we will discuss linked lists of integer nodes. The building block of the linked list is a node and nodes are chained (linked) together using pointers, just a data-type that stores the address of the next node. The following sketch would explain it better.


Linked List

Here is how you would describe a node and a linked list as C++ classes:

class Node {
  public:
    int data;
    Node *next;
  public: 
    Node (int item);
};

We denote the fist node of the list as “head” node which will come handy when we have operations that traverse the list. The next pointer just stores the address of the next node, as shown in the image below.

class LinkedList {
  private:
    Node *head;
    int length;
  // constructors and member functions
  ...


Linked List