Basic Implementation of Singly Linked List

Various implementation using singly linked list like insertion, deletion etc.

Node Structure

struct node
{
    int data;
    struct node *next;
};
node *head = NULL;

Finding the length of the linked list

int getLen()
{
    node *p = head;
    int s = 0;
    while (p != NULL)
    {
        s = s + 1;
        p = p->next;
        /* code */
    }
    return s;
}

Insertion in a Linked List

Insertion in a linked list takes O(1) time.

// Insertion in the beginning of the linked list
void insertAtBegin(int val)
{
    node *temp = new node;
    temp->data = val;

    if (head == NULL)
    {
        head = temp;
        temp->next = NULL;
    }
    else if (head != NULL)
    {
        temp->next = head;
        head = temp;
    }
}

// Insertion in the end of the Linked List
void insertAtEnd(int val)
{
    node *temp = new node;
    temp->data = val;
    temp->next = NULL;
    if (head == NULL)
    {
        head = temp;
    }
    else if (head != NULL)
    {
        node *p = head;
        while (p->next != NULL)
        {
            p = p->next;
        }
        p->next = temp;
    }
}

Insertion at any random position of a Linked list

void insertAtPos(int pos, int val)
{
    if (pos < 0 || pos>getLen() )
    {
        return; // If postion does not exits return
    }
    node *temp = new node;
    temp->data = val;

    node *p = head;
    int i = 0;
    while (p != NULL && i < pos - 1)
    {
        p = p->next;
        i++;
    }

    temp->next = p->next;
    p->next = temp;
}

Deletion in a Linked list

// Deletion at front
void delAtHead()
{
    node *p = head;
    if (head == NULL)
    {
        return;
    }

    p = p->next;
    head = p;
}

// Deletion at end
void delAtTail()
{
    if (head == NULL)
    {
        return;
    }
    node *p = head;
    node *q = NULL;
    while (p->next != NULL)
    {
        q = p;
        p = p->next;
    }
    q->next = p->next;

Deletion at any random position of a Linked list

void delAtPos(int pos)
{
    if (pos > getLen() || pos < 0)
    {
        return; // return if the position is not valid
    }
    node *p = head;
    node *q = NULL;
    int i = 0;
    while (i < pos)
    {
        q = p;
        p = p->next;
        i++;
    }
    q->next = p->next;
}

Displaying elements of the Linked List

void display()
{
    if (head == NULL)
    {
        cout << "Linked List empty";
    }
    else
    {
        node *p = head;
        while (p != NULL)
        {
            /* code */
            cout << p->data;
            cout << " --> ";
            p = p->next;
        }
        cout << "NULL";
    }
}