DEV Community

Cover image for Singly linked List Data Structure and implementation in C++
Kauress
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

Singly Linked List

Alt Text

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;
};

Enter fullscreen mode Exit fullscreen mode

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;
}

Enter fullscreen mode Exit fullscreen mode

Discussion (0)