Linked List - DSA | Part-4 |

A Linked List 🔗 is a linear data structure that inlcudes a series of connected node. Here, each node stores the data and the address of the next node.

We have to start somewhere, so we give the address of the first node a special name called HEAD. Also, the last node in the linked list can be identified because its next portion points to NULL.

🔗Types of Linked List

There are three types of Linked List - Singly, Doubly & Circular

Singly Linked List

Singly Linked List can be defines as the collection of ordered set of elements. The number of elements may very according to need of the program.

A node in the singly linked list consist of two parts - Data part & Link part. Data part of the node stores actual information that is to be represented by the node while the link part of the node stores the address of its immediate successor.

Singly linked list can be traversed only in one direction. In other words, we can say that each node contains only next pointer, therefore we can not traverse the list in the reverse direction.

Representation of Linked List

#include<iostream>
using namespace std;

struct Node{
    int data;
    struct Node *next;
};


void display(struct Node *ptr)
{
    while(ptr!=NULL){
        cout<<ptr->data<<", ";
        ptr = ptr->next;
    }
}
struct Node *head;
void delete_first(){
    struct Node *ptr;
    if(ptr==NULL){
        cout<<"List is empty";
    }
    else{
        ptr = head;
        head = ptr->next;
    }
}

int main()
{

    struct Node *first;
    struct Node *second;


    head = (struct Node*)(malloc(sizeof(struct Node)));
    first = (struct Node*)(malloc(sizeof(struct Node)));
    second = (struct Node*)(malloc(sizeof(struct Node)));

    head->data = 1;
    head->next = first;

    first->data = 12;
    first->next = second;

    second->data = 10;
    second->next = NULL;

    display(head);

    delete_first();
    cout<<endl;
    display(head);

    return 0;

---

Doubly Linked List

Doubly linked list is a complex typee of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. A node consists of three parts: Node Data, Pointer to the next node in sequence (next pointer), Pointer to the previous node (previous pointer).

Representation of Linked List

#include<iostream>
using namespace std;

struct Node{
    int data;
    struct Node *prev;
    struct Node *next;
};

struct Node *head;
struct Node *second;
struct Node *third;


void display(struct Node *ptr){
    ptr = head;
    cout<<"Forward list: ";
    while(ptr!=NULL){

        cout<<ptr->data<<", ";
        ptr = ptr->next;
    }
}

void display_reverse(struct Node *last_ptr){
    last_ptr=third;
    cout<<"Backward List: ";
    while(last_ptr!=NULL){

        cout<<last_ptr->data<<", ";
        last_ptr=last_ptr->prev;
    }
}


int main(){

    head = (struct Node*)(malloc(sizeof(struct Node)));
    second = (struct Node*)(malloc(sizeof(struct Node)));
    third = (struct Node*)(malloc(sizeof(struct Node)));

    head->data = 1;
    head->prev = NULL;
    head->next = second;

    second->data = 10;
    second->prev = head;
    second->next = third;

    third->data = 11;
    third->prev = second;
    third->next = NULL;

    display(head);
    cout<<endl;
    display_reverse(head);

    return 0;
}

---

Circular Linked List

A circular linked list is a type of linked list in which the first and the last nodes are also connected to each other to form a circle.

Representation of Circular Linked List

#include<iostream>
using namespace std;

struct Node{
    int data;
    struct Node *next;
};
struct Node *head;
struct Node *second;
struct Node *third;
struct Node *fourth;
struct Node *fifth;

void display(struct Node *ptr){
    ptr = head;

    do
    {
        cout<<ptr->data<<", ";
        ptr = ptr->next;
    } while (ptr!=head);

}

int main(){


    head = (struct Node*)(malloc(sizeof(struct Node)));
    second = (struct Node*)(malloc(sizeof(struct Node)));
    third = (struct Node*)(malloc(sizeof(struct Node)));
    fourth = (struct Node*)(malloc(sizeof(struct Node)));
    fifth = (struct Node*)(malloc(sizeof(struct Node)));

    head->data = 31;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 54;
    third->next = fourth;

    fourth->data = 546;
    fourth->next = fifth;

    fifth->data = 4;
    fifth->next = head;

    display(head);

    return 0;
}

---