Basic Operations on Linked List

1. Traversing the linked list
2. Inserting an element in the linked list
   1. In the beginning
   2. At the end
3. Deleting an element from the linked list

Traversing Linked List

See printLinkedList() method in below code snippets.

Inserting an element in the beginning

Suppose we have a below linked list.

Now, we want to add another node in the beginning of the linked list.

Remember, adding a node in the beginning will lead us to update head as well. Because, head always points to the first node in the linked list.

Now, suppose if we create a node, therefore head should be pointing to this new node. So, can we directly do head = node as shown below?

The answer is No. If we do so, we will lose the access to remaining linked list.

Correct Approach

Step 1: First connect newly added node to the current head node. See code snippet below.

node.next = head;

Step 2: Now update head pointing to new node.

head = node;

Code

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

public class InsertInBeginning {

    static Node head = null;

    public static void insertInBeginning(int data) {
        Node node = new Node(data);
        node.next = head;
        head = node;
    }

    public static void printLinkedList() {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " -> ");
            curr = curr.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        insertInBeginning(70);
        insertInBeginning(10);
        insertInBeginning(20);
        insertInBeginning(30);
        insertInBeginning(40);
        printLinkedList();
    }
}

Output

40 -> 30 -> 20 -> 10 -> 70 -> null

Inserting an element at the end

Let's say we don't have any node yet in our linked list. Therefore, let's create a node and try to add it to the linked list.

Node node = new Node(35);
if(head == null) {
    head = node;
}

So, if the node that you're trying to add, is the first node (which means head is not pointing to anything) then you might need to update the head as well. For further nodes, you won't need to update head because we are adding nodes to the end.

But would that be sufficient? Let's see.

Node node = new Node(67);

So, now we have created another node. Because it should come next to the head node because currently we have only one node i.e. head. So may be, we can directly do head.next = node. But is that correct? May be not. Let's see another addition of node to the end.

Node node = new Node(56);

Now 🤔, what do I do here? Should I do head.next.next = node? Wouldn't it be wrong?

If we do like this, then we might end up doing head.next.next.next.......next = node

The problem here is we are not keeping track of the current end node. If we keep track of current end node, then we might just need to create a node and do end.next = node.

Correct approach to insert at the end.

Let's see from the beginning.

If we are adding the very first node to the linked list, make sure to update the head and make newly added node as end node.

Node node = new Node(35);
if(head == null) {
    head = node;
}
end = node;

Now, let's add another node.

This time head is not null, which means we don't need to worry about head. We just need to do end.next = node as shown below. But because a new node is added at the end, so end should also be updated. See step 2.

Step 1:

Node node = new Node(65);
if(head == null) {
    head = node;
} else {
    end.next = node;
}

Step 2:

Now, update end = node.

Node node = new Node(65);
if(head == null) {
    head = node;
} else {
    end.next = node;
}
end = node;

And similarly, you can try for new nodes as well.

Code

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

public class InsertAtEnd {

    static Node head = null;
    static Node end = null;

    public static void insertAtEnd(int data) {
        Node node = new Node(data);
        if (head == null) {
            head = node;
        } else {
            end.next = node;
        }
        end = node;
    }

    public static void printLinkedList() {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " -> ");
            curr = curr.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        insertAtEnd(70);
        insertAtEnd(10);
        insertAtEnd(20);
        insertAtEnd(30);
        insertAtEnd(40);
        printLinkedList();
    }
}

Output

70 -> 10 -> 20 -> 30 -> 40 -> null

Deletion in Linked List

Read from Data Structures Made Easy by Narasimha Karumanchi.