Linked List & its Types

What is a Node?

 

 A Node is a linked list holds the data value and the pointer which points to the location of the next node in the linked list.

• Each node has at least two parts:
• 1) Data
• 2) Pointer (Or Reference) to the next node

Linked List

• Linked List is a very commonly used linear data structure.
• It is group of nodes in a sequence.
• Example:

• Each node holds its own data and the address of the next node.
• Each data node is connected to the next data node via a pointer, hence forming a chain.
• Linked Lists are used to create trees and graphs.
• For Example (In C Language):

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

Advantages of Linked Lists

• They are dynamic in nature which allocates the memory when required.
• Insertion and deletion operations can be easily implemented.
• Stacks and queues can be easily executed.
• Linked List reduces the access time.

Disadvantages of Linked Lists

• The memory is wasted as pointers require extra memory for storage.
• No element can be accessed randomly; it has to access each node sequentially.
• Reverse Traversing is difficult in a linked list.

Applications of Linked Lists

• Linked lists are used to implement stacks, queues, graphs, etc.
• Linked lists let you insert elements at the beginning and end of the list.
• In Linked Lists we don't need to know the size in advance.

Types of Linked Lists

• There are 3 different types:
• Singly Linked List:

• Singly-linked lists contain nodes which have a data part as well as an address part i.e. next, which points to the next node in the sequence of nodes.
• The operations we can perform on singly-linked lists are insertion, deletion, and traversal.
• Doubly Linked List:

• In a doubly-linked list, each node contains a data part and two addresses, one for the previous node and one for the next node.
• Circular Linked List
• In a circular linked list the last node of the list holds the address of the first node hence forming a circular chain.
• Two Types:

Basic Operations

• Insertion − Adds an element at the beginning of the list.
• Deletion − Deletes an element at the beginning of the list.
• Display − Displays the complete list.
• Search − Searches an element using the given key.
• Delete − Deletes an element using the given key.

Full Example (In C Language):

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

void printList(struct Node* n)
{
    while (n != NULL) {
        printf(" %d ", n->data);
        n = n->next;
    }
}

void main()
{
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    // allocate 3 nodes in the heap
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    head->data = 1; // assign data in first node
    head->next = second; // Link first node with second node

    second->data = 2; // assign data to second node
    second->next = third; // Link second node with the third node

    third->data = 3; // assign data to third node
    third->next = NULL; //no next node

    printList(head); //display nodes
}

Note: Header files as per editor.