C++ Singly Linked Lists

What is a singly linked list? How to implement singly linked lists in C++?

This article explains the concept of singly linked list data structure and provides a sample implementation in C++.
  • Linked lists are building blocks for many other data structures like stacks and queues.
  • Linked lists are a sequence of nodes containing data fields and pointers to the next node (or) next node and previous nodes based on its type.
  • Linked lists permit addition/ removal of node in constant time.
  • Unlike arrays the order of linked list elements need not be contiguous in memory.
  • Unlike arrays there is no upper limit on the amount of memory reserved.
  • A singly linked list is the simplest of linked lists.
  • Each node of a singly linked list has data elements and a single link (pointer) that points to the next node of the list (or) NULL if it is the last node of the list.
  • Addition/ Deletion of a node to the singly linked list involves the creation/ deletion of the node and adjusting the node pointers accordingly.
  • A singly linked list could be represented as below:-

    C++ Singly Linked Lists

Demonstrate the implementation of a singly linked list

#include <iostream>using namespace std;// Node classclass Node {int data;Node* next;public:Node() {};void SetData(int aData) { data = aData; };void SetNext(Node* aNext) { next = aNext; };int Data() { return data; };Node* Next() { return next; };};// List classclass List {Node *head;public:List() { head = NULL; };void Print();void Append(int data);void Delete(int data);};/*** Print the contents of the list*/void List::Print() {// Temp pointerNode *tmp = head;// No nodesif ( tmp == NULL ) {cout << "EMPTY" << endl;return;}// One node in the listif ( tmp->Next() == NULL ) {cout << tmp->Data();cout << " --> ";cout << "NULL" << endl;}else {// Parse and print the listdo {cout << tmp->Data();cout << " --> ";tmp = tmp->Next();}while ( tmp != NULL );cout << "NULL" << endl;}}/*** Append a node to the linked list*/void List::Append(int data) {// Create a new nodeNode* newNode = new Node();newNode->SetData(data);newNode->SetNext(NULL);// Create a temp pointerNode *tmp = head;if ( tmp != NULL ) {// Nodes already present in the list// Parse to end of listwhile ( tmp->Next() != NULL ) {tmp = tmp->Next();}// Point the last node to the new nodetmp->SetNext(newNode);}else {// First node in the listhead = newNode;}}/*** Delete a node from the list*/void List::Delete(int data) {// Create a temp pointerNode *tmp = head;// No nodesif ( tmp == NULL )return;// Last node of the listif ( tmp->Next() == NULL ) {delete tmp;head = NULL;}else {// Parse thru the nodesNode *prev;do {if ( tmp->Data() == data ) break;prev = tmp;tmp = tmp->Next();} while ( tmp != NULL );// Adjust the pointersprev->SetNext(tmp->Next());// Delete the current nodedelete tmp;}}int main(){// New listList list;// Append nodes to the listlist.Append(100);list.Print();list.Append(200);list.Print();list.Append(300);list.Print();list.Append(400);list.Print();list.Append(500);list.Print();// Delete nodes from the listlist.Delete(400);list.Print();list.Delete(300);list.Print();list.Delete(200);list.Print();list.Delete(500);list.Print();list.Delete(100);list.Print();}

OUTPUT:-

100 --> NULL100 --> 200 --> NULL100 --> 200 --> 300 --> NULL100 --> 200 --> 300 --> 400 --> NULL100 --> 200 --> 300 --> 400 --> 500 --> NULL100 --> 200 --> 300 --> 500 --> NULL100 --> 200 --> 500 --> NULL100 --> 500 --> NULL100 --> NULLEMPTY