Singly Linked List | Data Structure

Mahmudul Hasan July 23, 2021 0

Singly Linked List- Code on PasteBin

image source: javapoint.com

***Table of contents***

1. Single Linked List Structure.

2. Creating a Linked List with the given size.

3. Printing the linked list.

4. Length of the Linked list.

5. Determining the Sum of the elements of the linked list.

6. Finding the min element of LL.

7. Finding the max element of LL.

8. Searching a data/value of a node in the LL.

9. Searching a node with its data in the Linked List and 

   making it the head/root node.

10. Insertion of a node at Linked List.

11. Deletion of a node from Linked List.

12. Reversing the Linked List.

CODE in C/C++:

#include<bits/stdc++.h>
using namespace std;


/*1. Single Linked List Structure*/
typedef struct Node{
    int data;
    Node* next;
}Node;


/*2. Creates a Linked List with the given size*/
Node* Create_SingleLL(int n){
    int data;
    Node *head=nullptr,*tail=nullptr;
    while(n--){
        cin>>data;
        if(!head){
            head = (Node*)malloc(sizeof(Node));
            head->data = data;
            head->next = nullptr;
            tail = head;
            continue;
        }
        Node* t = (Node*) malloc(sizeof(Node));
        t->data = data;
        t->next = nullptr;
        tail->next = t;
        tail = t;
    }
    return head;
}


/*3. Prints the linked list*/
void Display(Node* head){
    Node* curr = head;
    while(curr){
        cout<<curr->data<<" ";
        curr = curr->next;
    }
    cout<<endl;
}


/*4. Length of the LL*/
int Length_SLL(Node* head){
    Node* x = head;
    int l = 0;
    while (x)
    {
        ++l;
        x = x->next;
    }
    return l;
}


//***5***
/**
 * @brief Sum of the elements of the linked list
 * 
 * @param head - the root node
 * @return long 
 */

long Sum(Node* head){
    if(!head) return 0LL;
    return head->data*1LL+Sum(head->next);
}


//***6*** 
/**
 * @brief Returns the min element of LL
 * 
 * @param p - the root node
 * @return minmum value
 */

int Minimum(Node* p){
    int mn = INT_MAX;
    while (p){
        if(p->data <mn) mn = p->data;
        p = p->next;
    }
    return mn;
}


//***7***
/**
 * @brief Returns the max element of LL
 * 
 * @param p - the root node
 * @return maximum value
 */

int Maximum(Node* p){
    int mx = INT_MIN;
    while (p){
        if(p->data>mx) mx = p->data;
        p = p->next;
    }
    return mx;
}


//***8***
/**
 * @brief Searches a data in the LL
 * If found, returns the node, else nullptr
 * 
 * @param p - the root node
 * @param data - the value that we want to search
 * @return Node* - the node that we're searching for
 */

Node* Search(Node* p, int data){
    if(!p) return NULL;
    else if(p->data == data) return p;
    return Search(p->next, data);
}


//***9***
/**
 * @brief Search a node in the Linked List and makes it as Head/root node
 * 
 * @param head - the root node
 * @param data 
 * @return Node* 
 */

Node* SearchAndMakeAsHead(Node* head, int data){
    Node* q=nullptr;
    Node* p = (Node*)malloc(sizeof(Node));
    p = head;
    while(p){
        if(p->data==data){
            q->next = p->next;
            p->next = head;
            head = p;
            return p;
        }
        q = p;
        p = p->next;
    }
    return head;
}
/*10. Inserts a node at Linked List*/
/**
 * @brief here we're considering the linked list as 0 base, 
 * means the starting position of the linked list is 0.
 * 
 * @param head - the root node
 * @param data - the value of the node
 * @param pos - where the node will be inserted
 */

Node* InsertNodeAtSLL(Node* head, int data, int pos){
    Node* t,*p;
    t = (Node*)malloc(sizeof(Node));
    if(pos==0){
        t->data = data;
        t->next = head;
        head = t;
    }
    else if(pos>0 && pos<=Length_SLL(head)){
        p = head;
        for(int i=1; i<pos; ++i){
            p = p->next;
        }
        if(p){
            t->data = data;
            t->next = p->next;
            p->next = t;
        }
    }
    return head;
}

//***11***

/**
 * @brief Deletes a node from the given position of a Linked List
 * Assume that the starting position of the linked list is 0
 * 
 * @param head - the root node
 * @param pos - the position of the node that we want to delete
 * @return Node* 
 */
Node* DeleteNodeFromSLL(Node* head, int pos){
    
    if(pos==0){
        head = head->next;
        return head;
    }
    else if(pos>0 && pos<Length_SLL(head)){
        Node* p,*q;
        p = head;
        for(int i=0; i<pos; ++i){
            q = p;
            p = p->next;
        }
        if(p){
            q->next = p->next;
        }
    }
    return head;
}


//***12***
/**
 * @brief Reverses the Single linkedlist
 * 
 * @param head - the root node
 * @return Node* 
 */

Node* ReverseSLL(Node* head){
    if(!head->next) return head;
    Node* t = ReverseSLL(head->next);
    head->next->next = head;
    head->next = nullptr;
    return t;
}


int main(){

    int n, x, y;
    cin>>n;
    Node* head = Create_SingleLL(n);
    Display(head);
    cout<<"Length: "<<Length_SLL(head)<<endl;
    cout<<"Sum: "<<Sum(head)<<endl;
    cout<<"Max element: "<<Maximum(head)<<endl;
    cout<<"Min Element: "<<Minimum(head)<<endl;
    

    cout<<"Enter the value you that want to search: ";
    cin>>x;
    Node* src = Search(head, x);
    if(src)cout<<"Found!\n";
    else cout<<"Not Found!\n";

    head = SearchAndMakeAsHead(head, x);
    Display(head);
    

    cout<<"Enter the position of assertion: ";
    cin>>y;
    cout<<"Enter the value of the Node that you want to Insert: ";
    cin>>x;
    head = InsertNodeAtSLL(head, x, y);
    Display(head);

    cout<<"Enter the position of deletion: ";
    cin>>x;
    head = DeleteNodeFromSLL(head, x);
    Display(head);


    head = ReverseSLL(head);
    Display(head);



    free(head);
    return 0;
}

No comments

Subscribe to: Post Comments ( Atom )