Implementing Basic Operations on Linked Lists (Insertion, Deletion, Traversal)

In this article, we will explore how to implement basic operations on linked lists using Java. Linked lists are a fundamental data structure that consists of a sequence of nodes, where each node contains a value and a reference to the next node in the sequence. We will cover three main operations: insertion, deletion, and traversal.

Insertion

Insertion is the process of adding a new node to the linked list. There are three possible scenarios for insertion:

1. Insertion at the beginning: In this case, the new node becomes the new head of the linked list. We need to update the reference of the new node to point to the current head, and then update the head to point to the new node.

2. Insertion at the end: If the linked list is empty, we simply add the new node as the head. Otherwise, we traverse the list until we reach the last node, and update its reference to point to the new node.

3. Insertion at a specific position: To insert a node at a specific position, we traverse the list until we reach the node before the desired position. Then, we update the references to insert the new node into the list.

Here is the Java code for the insertion operation:

public void insert(int data) {
    Node newNode = new Node(data); // create a new node
    if (head == null) { // if the list is empty
        head = newNode; // set the new node as the head
    } else {
        Node current = head;
        while (current.next != null) {
            current = current.next; // traverse the list until the last node
        }
        current.next = newNode; // update the reference of the last node
    }
}

Deletion

Deletion is the process of removing a node from the linked list. Similar to insertion, there are three possible scenarios for deletion:

1. Deletion at the beginning: In this case, we simply update the head to point to the next node.

2. Deletion at the end: If the linked list has only one node, we set the head to null. Otherwise, we traverse the list until we reach the second-to-last node, and update its reference to null.

3. Deletion at a specific position: To delete a node at a specific position, we traverse the list until we reach the node before the desired position. Then, we update the references to remove the node from the list.

Here is the Java code for the deletion operation:

public void delete(int data) {
    if (head == null) { // if the list is empty
        return;
    } else if (head.data == data) { // if the node to delete is the head
        head = head.next; // update the head to the next node
    } else {
        Node current = head;
        while (current.next != null && current.next.data != data) {
            current = current.next; // traverse the list until we find the node to delete
        }
        if (current.next != null) { // if the node is found
            current.next = current.next.next; // update the references to remove the node
        }
    }
}

Traversal

Traversal is the process of visiting each node of the linked list. We can simply traverse the list starting from the head and print or manipulate the values of each node.

Here is the Java code for the traversal operation:

public void traverse() {
    Node current = head;
    while (current != null) {
        System.out.print(current.data + " "); // print the value of the current node
        current = current.next; // move to the next node
    }
}

Conclusion

In this article, we have learned how to implement basic operations on linked lists using Java. Linked lists are a versatile data structure and understanding these operations is crucial for working with them effectively. By implementing insertion, deletion, and traversal, we can build a solid foundation for more complex linked list operations and algorithms.