DEV Community

Ankit Kumar
Ankit Kumar

Posted on

Insertion and Deletion on Linked List

`

include

using namespace std;

// Linked list definition
struct ListNode
{
// ListNode comprises data(any) and next(pointer point to next ListNode)
int data;
ListNode *next;

// Constructor for data initialization for different argument
ListNode() : data(0), next(nullptr) {}
ListNode(int x) : data(x), next(nullptr) {}
ListNode(int x, ListNode *next) : data(x), next(next) {}
Enter fullscreen mode Exit fullscreen mode

};

class Solution
{
private:
// Head of ListNode
ListNode *head;

public:
// Constructor to initialize head ListNode as nullptr
Solution() : head(nullptr) {}

// Insertion at beginning
void InsertAtBegining(int data)
{
    ListNode *newNode = new ListNode(data); // New ListNode creation via ListNode structure constructor(Dynamically)
    newNode->next = head; // Since head contain the address of first ListNode, put that address in newNode->next
    head = newNode;       // Now head is pointing to newNode , i.e. newNode is the new head of ListNode
}

// Insertion at end
void InsertionAtEnd(int data)
{
    ListNode *newNode = new ListNode(data);

    // If list is empty, add newNode
    if (head == nullptr)
    {
        head = newNode;
        return;
    }

    // Traverse to the end of list
    ListNode *current = head;
    while (current->next != nullptr)
    {
        current = current->next;
    }
    // Now Add to the list 
    current->next = newNode;
}

// Insertion at any position
void InsertAtPosition(int data, int pos)
{
    // If pos is less than 0 or equals, insert at beginning
    if (pos <= 0)
    {
        InsertAtBegining(data);
        return;
    }
    // Traverse to the ListNode before the specified position
    ListNode *current = head;
    for (int i = 0; i < pos - 1 && current != nullptr; i++) {
        current = current->next;
    }
    // If pos is greater than the length of linked list, insert at end
    if(current == nullptr) {
        InsertionAtEnd(data);
        return;
    }
    // Insert newNode at specified position
    ListNode *newNode = new ListNode(data);
    newNode->next = current->next;
    current->next = newNode;
}

// Deletion at beginning
void DeletionAtBeginning() {
    if(head != nullptr) {
        ListNode *temp = head;
        head = temp->next;
        delete temp;
    }
    else {
        cout << "List is empty, Can't delete anything";
    }
}

// Deletion at End
void DeletionAtEnd() {
    // List is empty
    if(head == nullptr) {
        cout << "List is empty, Can't delete anything";
        return;
    }
    // If there is only one ListNode, make head equals nullptr
    if(head->next == nullptr) {
        delete head;
        head = nullptr;
        return;
    }
    // Traverse from second ListNode to last ListNode
    ListNode *temp = head;
    while(temp->next->next != nullptr) {
        temp = temp->next;
    }
    delete temp->next;
    temp->next = nullptr;
}

// Deletion at any position
void DeleteAtPosition(int pos) {
    // Invalid position or list is empty
    if(pos < 0 || head == nullptr) {
        cout << "List is empty or invalid position";
        return;
    }

    // First position
    if(pos == 0) {
        DeletionAtBeginning();
        return;
    }

    // Traverse till specified position
    ListNode *current = head;
    for (int i = 0; i < pos - 1 && current != nullptr; i++) {
        current = current->next;
    }
    // Specified position is beyond the ListNode length
    if(current == nullptr || current->next == nullptr) {
        cout << "Given position is beyond ListNode length";
        return;
    }
    // Delition at specified position
    ListNode *temp = current->next;
    current->next = current->next->next;
    delete temp;
}

void printList()
{
    while (head != nullptr)
    {
        cout << head->data << " ";
        head = head->next;
    }
}
Enter fullscreen mode Exit fullscreen mode

};

int main()
{
Solution s;
s.InsertAtBegining(1);
s.InsertAtBegining(2);
s.InsertAtPosition(3,1);
s.InsertAtPosition(4,2);
s.InsertionAtEnd(1);
s.InsertionAtEnd(2);
s.InsertionAtEnd(3);
s.InsertionAtEnd(4);
s.DeletionAtBeginning();

s.DeletionAtEnd();

s.DeleteAtPosition(3);

s.printList();
}`

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

Billboard image

Create up to 10 Postgres Databases on Neon's free plan.

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Try Neon for Free →

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay