Algorithm

A linked list is a fundamental data structure in computer science used to organize and store data. It consists of a sequence of elements, called nodes, where each node contains a data field and a reference (link or pointer) to the next node in the sequence. Linked lists offer dynamic memory allocation, efficient insertion and deletion of elements, and are particularly useful when the size of the data is not known in advance.

Here's a comprehensive overview of linked lists:

Basic Components of a Linked List:

  1. Node:

    • A basic building block of a linked list.
    • Contains data (payload) and a reference to the next node.

  2. Head:

    • The first node in a linked list.
    • Serves as the entry point for accessing the list.

  3. Tail:

    • The last node in a linked list.
    • Points to null or an indication that it is the end of the list.

Types of Linked Lists:

  1. Singly Linked List:

    • Each node points to the next node in the sequence.
    • Simple and memory-efficient.

  2. Doubly Linked List:

    • Each node points to both the next and the previous node.
    • Supports bidirectional traversal.

  3. Circular Linked List:

    • The last node points back to the first node, forming a circle.
    • Useful in applications where the list needs to be traversed endlessly.

Operations on Linked Lists:

  1. Insertion:

    • Adding a new node to the list.
    • Three main types:
      • Insertion at the beginning.
      • Insertion at the end.
      • Insertion at a specific position.

  2. Deletion:

    • Removing a node from the list.
    • Three main types:
      • Deletion at the beginning.
      • Deletion at the end.
      • Deletion at a specific position.

  3. Traversal:

    • Visiting each node in the list to perform a specific operation.

  4. Searching:

    • Locating a node with a specific value.

  5. Merging:

    • Combining two linked lists into one.

Advantages of Linked Lists:

  1. Dynamic Size:

    • Easily accommodates varying amounts of data.

  2. Efficient Insertion and Deletion:

    • Adding or removing elements doesn't require moving other elements.

  3. No Wasted Memory:

    • Allocates memory as needed.

Disadvantages of Linked Lists:

  1. Random Access:

    • Accessing elements by index is slower compared to arrays.

  2. Extra Memory:

    • Requires extra memory for storing the pointers

 

Code Examples

#1 Linked List Operations: Traverse, Insert and Delete implement in java

Code - Java Programming

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    // Traverse the linked list and print each element
    public void traverse() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    // Insert a new node at the end of the linked list
    public void insert(int data) {
        Node newNode = new Node(data);

        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // Delete a node with a given data value from the linked list
    public void delete(int data) {
        if (head == null) {
            System.out.println("List is empty. Nothing to delete.");
            return;
        }

        if (head.data == data) {
            head = head.next;
            return;
        }

        Node current = head;
        Node prev = null;

        while (current != null && current.data != data) {
            prev = current;
            current = current.next;
        }

        if (current == null) {
            System.out.println("Element not found in the list.");
        } else {
            prev.next = current.next;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();

        // Insert elements
        linkedList.insert(1);
        linkedList.insert(2);
        linkedList.insert(3);

        // Traverse and print elements
        System.out.println("Linked List:");
        linkedList.traverse();

        // Delete an element
        linkedList.delete(2);

        // Traverse and print elements after deletion
        System.out.println("Linked List after deletion:");
        linkedList.traverse();
    }
}
Copy The Code & Try With Live Editor

#2 Linked List Operations: Traverse, Insert and Delete implement in Python

Code - Python Programming

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

    def insert(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def delete(self, data):
        current = self.head

        # Case: Deleting the head node
        if current and current.data == data:
            self.head = current.next
            del current
            return

        # Case: Deleting a node in the middle or at the end
        prev = None
        while current and current.data != data:
            prev = current
            current = current.next

        if current is None:
            print(f"{data} not found in the list.")
            return

        prev.next = current.next
        del current


# Example usage:
linked_list = LinkedList()

# Inserting nodes
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)

# Traversing the list
print("Linked List:")
linked_list.traverse()

# Deleting a node
linked_list.delete(2)

# Traversing again after deletion
print("\nLinked List after deletion:")
linked_list.traverse()
Copy The Code & Try With Live Editor

#3 Linked List Operations: Traverse, Insert and Delete implement in C

Code - C Programming

#include <stdio.h>
#include <stdlib.h>

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

// Function to traverse the linked list
void traverse(struct Node* head) {
    printf("Linked List: ");
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

// Function to insert a new node at the end of the linked list
void insert(struct Node** head, int newData) {
    // Allocate memory for the new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = NULL;

    // If the linked list is empty, make the new node the head
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    // Traverse to the end of the linked list
    struct Node* last = *head;
    while (last->next != NULL) {
        last = last->next;
    }

    // Insert the new node at the end
    last->next = newNode;
}

// Function to delete a node with a given key from the linked list
void deleteNode(struct Node** head, int key) {
    // If the linked list is empty, return
    if (*head == NULL) {
        return;
    }

    // If the key is in the head node
    if ((*head)->data == key) {
        struct Node* temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }

    // Traverse the linked list to find the node with the key
    struct Node* current = *head;
    struct Node* prev = NULL;
    while (current != NULL && current->data != key) {
        prev = current;
        current = current->next;
    }

    // If the key is not present
    if (current == NULL) {
        printf("Key %d not found in the linked list.\n", key);
        return;
    }

    // Unlink the node from the linked list
    prev->next = current->next;

    // Free the memory of the deleted node
    free(current);
}

// Main function for testing
int main() {
    struct Node* head = NULL;

    // Insert some nodes
    insert(&head, 1);
    insert(&head, 2);
    insert(&head, 3);

    // Traverse and print the linked list
    traverse(head);

    // Delete a node with key 2
    deleteNode(&head, 2);

    // Traverse and print the linked list after deletion
    traverse(head);

    return 0;
}
Copy The Code & Try With Live Editor

#4 Linked List Operations: Traverse, Insert and Delete implement in C++

Code - C++ Programming

#include <iostream>

// Node structure for the linked list
struct Node {
    int data;
    Node* next;
    
    // Constructor to initialize a new node
    Node(int value) : data(value), next(nullptr) {}
};

// Linked List class
class LinkedList {
private:
    Node* head;

public:
    // Constructor to initialize an empty linked list
    LinkedList() : head(nullptr) {}

    // Function to traverse and print the elements of the linked list
    void traverse() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }

    // Function to insert a new node at the end of the linked list
    void insert(int value) {
        Node* newNode = new Node(value);

        if (head == nullptr) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    // Function to delete a node with a specific value from the linked list
    void deleteNode(int value) {
        Node* current = head;
        Node* prev = nullptr;

        // Traverse the list to find the node with the given value
        while (current != nullptr && current->data != value) {
            prev = current;
            current = current->next;
        }

        // If the value is not found, do nothing
        if (current == nullptr) {
            std::cout << "Node with value " << value << " not found." << std::endl;
            return;
        }

        // If the node to be deleted is the head
        if (prev == nullptr) {
            head = current->next;
        } else {
            prev->next = current->next;
        }

        delete current; // Free the memory of the deleted node
    }
};

// Example usage
int main() {
    LinkedList myList;

    // Inserting elements
    myList.insert(1);
    myList.insert(2);
    myList.insert(3);

    // Traversing and printing elements
    std::cout << "Linked List: ";
    myList.traverse();

    // Deleting a node
    myList.deleteNode(2);

    // Traversing and printing elements after deletion
    std::cout << "Linked List after deletion: ";
    myList.traverse();

    return 0;
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration

Linked List Operations: Traverse, Insert and Delete-DevsEnv