Singly linked List Data Structure and implementation in C++

A linked list will store a collection of "nodes".
A linked list data structure is represented as a chain of nodes chained/connected to each other. Each node has it's own data and a reference to the next node, which in turn has it's own data.

Implementation

Linked lists are used to represent:

1. Stacks
2. Queues
3. Graphs

The 3 types of Linked Lists

Singly Linked List

A Single Linked List Data Structure will have nodes that have:

1. Data
2. Address which points to the next node

The last node will point to "null".

Operations on a linked list include:

1. Insertion
2. Deletion
3. Traversal

You can implement a Linked List in C++ through structures and pointers:

//create a singly linked list
//use keyword struct
//The structure of the 1st node will be:
//the first data member/ will be an integer
// the second member of the node will be a node pointer called next

struct Node {
  int data;
  struct Node *next;
};

So if you have access to the first node, which contains the address to the 2nd node, which in turn contains the address of the 3rd node and so on - you have access to all the nodes in a singly linked list.

Let's have a look at the implementation of a singly linked list in C++

#include <iostream>

using namespace std;

//Declare Node structure template/blueprint
//a node consists of an integer variable called num
// and the 2nd part of the node is a pointer called *next
struct Node{
    int num;
    Node *next;
};

//Declare starting (Head) node pointer to be NULL
struct Node *head=NULL;

//Insert node at start
/*
function insertNode takes an integer "n" as an arugment/paramter
using struct Node create a newNode pointer which is = a new Node
the newNode's data part (num ) is = the "n" parameter
the newNode's next pointer points to Head
and HEAD not is not null but instead the newNode
*/
void insertNode(int n){
    struct Node *newNode=new Node;
    newNode->num=n;
    newNode->next=head;
    head=newNode;
}

//Traverse the list and cout all nodes 
/*
#include <iostream>

using namespace std;

/*Declare Node structure template/blueprint
a node consists of an integer variable called num
 and the 2nd part of the node is a pointer called *next which points to the 
next NODE
*/
struct Node{
    int num;
    Node *next;
};

//Declare starting (Head) node pointer to be NULL
struct Node *head=NULL;

//Insert node at start
/*
function insertNode takes an integer "n" as an arugment/paramter
using struct Node create a newNode pointer which is = a new Node using the "new" keyword
the arrow operator -> allows you to access elements in a structure
the newNode's data part (num ) is pointing to the num part of the node which is = the "n" parameter
Access the next part of a Node and assign it to be the head of the newNode
and HEAD not is not null but instead the newNode
*/
void insertNode(int n){
    struct Node *newNode =new Node;
    newNode->num=n;
    newNode->next=head;
    head=newNode;
}

//Traverse the list and cout all nodes 
/*
If the head is === Null then let the user know that the list is empty and exit function
else the *temp pointer = head
and while the *temp pointer is not == NULL
cout the data part of temp pointer
and then temp is now = to the next temp pointer
*/

void display(){
    if(head==NULL){
        cout<<"List is empty!"<<endl;
        return;
    }
    struct Node *temp=head;
    while(temp!=NULL){
        cout<<temp->num<<" ";
        temp=temp->next;
    }
    cout<<endl;
}

//delete node from start
void deleteItem(){
    if(head==NULL){
        cout<<"List is empty!"<<endl;
        return;
    }
    cout<<head->num<<" is removed."<<endl;
    head=head->next;
}
int main(){
    cout<<"<---- Singly Linked List ----->" <<endl; 
    insertNode(1);
    insertNode(2);
    insertNode(3);
    deleteItem();
    display();
    return 0;
}