1.
Introduction
2.
Delete Alternate Nodes of a Linked List
2.1.
C++ Implementation
2.1.1.
Output
2.1.2.
Time complexity
2.1.3.
Space complexity
3.
FAQs
3.1.
3.2.
How is a Linked list different from an array?
3.3.
Is random access possible on the Linked list?
3.4.
What are the different types of Linked lists available?
3.5.
What is a struct data type in C++?
4.
Conclusion
Last Updated: Mar 27, 2024

# Delete Alternate Nodes of a Linked List

Teesha Goyal
0 upvote

## Introduction

A Linked List is a container called a data structure that stores the elements at non-contiguous memory locations. It works with the help of the next pointer. Each node has a next pointer that holds the address of the next node. To understand Linked List, visit our site, Linked List | Learn & Practice from Coding Ninjas Studio

## Delete Alternate Nodes of a Linked List

The problem is removing or deleting the alternate occurring nodes of a Linked List. Suppose you are given a linked list 7->5->3->1, then after removing the alternate nodes from the second node, you would get 7 -> 3. Also, if you are given 1->2->3->4->5->6->7, then the output after removing alternate nodes would be 1->3->5->7.

The steps of implementation to solve the above problem are:

1. Create a struct variable node that has data and a next pointer.

2. Initialize the linked list by setting the head variable to NULL, indicating an empty list.

3. Write an insert method to insert elements or nodes in the list. ‘

4. Write a delete function to remove alternate elements from the list. This function will iterate through the list and skips one item, and delete every other alternating item from the list.

5. Write a function to display the elements of the list at any time to print output and verify results.

### C++ Implementation

``````#include<iostream>
using namespace std;

/* Declaring Struct variable Node to represent a node in the Linked List. */
struct Node {
int data;
Node *next;
};

/* A function to delete alternative nodes from the Linked List */
/* Check for empty List*/
return;

/* Loop to iterate over the complete list*/
while(next_node != NULL && current_node != NULL){
current_node ->next = next_node->next;

/* Removing the alternative node*/
free(next_node);

/*Updating current_node*/
current_node  = current_node ->next;
if (current_node  != NULL) {
next_node = current_node ->next;
}
}
}

/* A function to display the given linekd list*/

/* Loop to iterate over the list and printing each element*/
while (node != NULL) {
cout << node->data;
node = node->next;

if(node != NULL)
cout<<" -> ";
}
}

/* An insert function to insert an item with value temp_data in the Linked list*/
void NodeInsert(Node** head_ref, int temp_data) {
Node* temp_node = new Node();
temp_node->data = temp_data;
}

/* Driver function*/
int main() {

/* Initializing an empty Linked List*/

/* Inserting Sample elements*/

/* Displaying nodes before deletion*/
cout << "Before Deletion:\n";

/* Displaying nodes after deletion*/
cout << "\nAfter Deletion:\n";

return 0;
}``````

#### Output

``````Before Deletion:
1 -> 2 -> 3 -> 4 -> 5
After Deletion:
1 -> 3 -> 5``````

#### Time complexity

O(n), where n denotes the number of nodes in the linked list.

Reason: To remove the alternate nodes of a Linked list, we must iterate through the entire list. Hence, the complexity of O(n) for n nodes.

#### Space complexity

O(n), where n denotes the number of nodes in the linked list.

Reason: To store the list elements, we require O(n) space complexity. Other than the list itself, the space required is constant.

## FAQs

#### What is a Linked List?

A Linked List is a container called a data structure that stores the elements at non-contiguous memory locations. It works with the help of the next pointer. Each node has a next pointer that holds the address of the next node.

#### How is a Linked list different from an array?

A Linked list has elements stored at non-contiguous memory locations and uses the next pointer to determine the address of the next element. Whereas the array stores the elements in contiguous memory locations.

#### Is random access possible on the Linked list?

Unlike an array, the random access of elements is not possible in a Linked list in O(1). We have to iterate through the list to access the elements as the elements are not continuously stored.

#### What is a struct data type in C++?

Struct is a data type present in C++. A struct is a collection of different nodes wrapped into a single unit. A user can define a struct variable as their choice and store different data types under a single struct variable.