Kauress

Posted on

# 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

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

//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
*/
void insertNode(int n){
struct Node *newNode=new Node;
newNode->num=n;
}

//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

//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
*/
void insertNode(int n){
struct Node *newNode =new Node;
newNode->num=n;
}

//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(){
cout<<"List is empty!"<<endl;
return;
}
while(temp!=NULL){
cout<<temp->num<<" ";
temp=temp->next;
}
cout<<endl;
}

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

``````