# Program to implement Singly Linked List in C++ using class

The linked list stores data in sequential storage, like arrays. Though the data are stored sequentially, the memory locations are not contiguous.

Unlike an array, the linked list can store data of different data types.

The below diagram represents the linked-list structure.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

In C++ the linked list can be represented with a class and a **Node** class separately, which has two members, namely data and a **next** pointer which points to the next node.

** InsertNode**: In this article, insertion is done at the end of the list. Follow the steps to insert a node in the linked list.

- Let’s say,
**4**is to be inserted on the existing linked list, i.e.,**1 -> 2 -> 3**.The resultant linked list will be**1 -> 2 -> 3 -> 4.** - To insert a new node traverse till the end of the list until NULL node is found.
- Create a new Node, and link the new node to the last node of the linked list.

** DeleteNode**: In this article, deletion is done using the

**index**of the node. Follow the steps to delete a node:

- If the node to be deleted is the head node, store the
**head**in**temp**variable. Then update**head**as**head->next**. Delete**temp**. - If the index of the node to be deleted is greater than the length of the list then return from the function.
- Traverse till the node to be deleted. Delete the node, and link the previous node to the next node of the deleted node.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach ` `#include <iostream> ` `using` `namespace` `std; ` ` ` `// Node class to represent ` `// a node of the linked list. ` `class` `Node { ` `public` `: ` ` ` `int` `data; ` ` ` `Node* next; ` ` ` ` ` `// Default constructor ` ` ` `Node() ` ` ` `{ ` ` ` `data = 0; ` ` ` `next = NULL; ` ` ` `} ` ` ` ` ` `// Parameterised Constructor ` ` ` `Node(` `int` `data) ` ` ` `{ ` ` ` `this` `->data = data; ` ` ` `this` `->next = NULL; ` ` ` `} ` `}; ` ` ` `// Linked list class to ` `// implement a linked list. ` `class` `Linkedlist { ` ` ` `Node* head; ` ` ` `public` `: ` ` ` `// Default constructor ` ` ` `Linkedlist() { head = NULL; } ` ` ` ` ` `// Function to insert a ` ` ` `// node at the end of the ` ` ` `// linked list. ` ` ` `void` `insertNode(` `int` `); ` ` ` ` ` `// Function to print the ` ` ` `// linked list. ` ` ` `void` `printList(); ` ` ` ` ` `// Function to delete the ` ` ` `// node at given position ` ` ` `void` `deleteNode(` `int` `); ` `}; ` ` ` `// Function to delete the ` `// node at given position ` `void` `Linkedlist::deleteNode(` `int` `nodeOffset) ` `{ ` ` ` `Node *temp1 = head, *temp2 = NULL; ` ` ` `int` `ListLen = 0; ` ` ` ` ` `if` `(head == NULL) { ` ` ` `cout << ` `"List empty."` `<< endl; ` ` ` `return` `; ` ` ` `} ` ` ` ` ` `// Find length of the linked-list. ` ` ` `while` `(temp1 != NULL) { ` ` ` `temp1 = temp1->next; ` ` ` `ListLen++; ` ` ` `} ` ` ` ` ` `// Check if the position to be ` ` ` `// deleted is less than the length ` ` ` `// of the linked list. ` ` ` `if` `(ListLen < nodeOffset) { ` ` ` `cout << ` `"Index out of range"` ` ` `<< endl; ` ` ` `return` `; ` ` ` `} ` ` ` ` ` `// Declare temp1 ` ` ` `temp1 = head; ` ` ` ` ` `// Deleting the head. ` ` ` `if` `(nodeOffset == 1) { ` ` ` ` ` `// Update head ` ` ` `head = head->next; ` ` ` `delete` `temp1; ` ` ` `return` `; ` ` ` `} ` ` ` ` ` `// Traverse the list to ` ` ` `// find the node to be deleted. ` ` ` `while` `(nodeOffset-- > 1) { ` ` ` ` ` `// Update temp2 ` ` ` `temp2 = temp1; ` ` ` ` ` `// Update temp1 ` ` ` `temp1 = temp1->next; ` ` ` `} ` ` ` ` ` `// Change the next pointer ` ` ` `// of the previous node. ` ` ` `temp2->next = temp1->next; ` ` ` ` ` `// Delete the node ` ` ` `delete` `temp1; ` `} ` ` ` `// Function to insert a new node. ` `void` `Linkedlist::insertNode(` `int` `data) ` `{ ` ` ` `// Create the new Node. ` ` ` `Node* newNode = ` `new` `Node(data); ` ` ` ` ` `// Assign to head ` ` ` `if` `(head == NULL) { ` ` ` `head = newNode; ` ` ` `return` `; ` ` ` `} ` ` ` ` ` `// Traverse till end of list ` ` ` `Node* temp = head; ` ` ` `while` `(temp->next != NULL) { ` ` ` ` ` `// Update temp ` ` ` `temp = temp->next; ` ` ` `} ` ` ` ` ` `// Insert at the last. ` ` ` `temp->next = newNode; ` `} ` ` ` `// Function to print the ` `// nodes of the linked list. ` `void` `Linkedlist::printList() ` `{ ` ` ` `Node* temp = head; ` ` ` ` ` `// Check for empty list. ` ` ` `if` `(head == NULL) { ` ` ` `cout << ` `"List empty"` `<< endl; ` ` ` `return` `; ` ` ` `} ` ` ` ` ` `// Traverse the list. ` ` ` `while` `(temp != NULL) { ` ` ` `cout << temp->data << ` `" "` `; ` ` ` `temp = temp->next; ` ` ` `} ` `} ` ` ` `// Driver Code ` `int` `main() ` `{ ` ` ` `Linkedlist list; ` ` ` ` ` `// Inserting nodes ` ` ` `list.insertNode(1); ` ` ` `list.insertNode(2); ` ` ` `list.insertNode(3); ` ` ` `list.insertNode(4); ` ` ` ` ` `cout << ` `"Elements of the list are: "` `; ` ` ` ` ` `// Print the list ` ` ` `list.printList(); ` ` ` `cout << endl; ` ` ` ` ` `// Delete node at position 2. ` ` ` `list.deleteNode(2); ` ` ` ` ` `cout << ` `"Elements of the list are: "` `; ` ` ` `list.printList(); ` ` ` `cout << endl; ` ` ` `return` `0; ` `}` |

**Output**

Elements of the list are: 1 2 3 4 Elements of the list are: 1 3 4

**Time Complexity:** O(N)**Auxiliary Space:** O(N)