Data Structure & Algorithm in Java

⌘K
  1. Home
  2. Docs
  3. Data Structure & Alg...
  4. Linked Lists
  5. Basic Operations in Linked List

Basic Operations in Linked List

Basic Operations in Linked List
  • At the beginning: Inserting a new node at the beginning of the list.
  • At the end: Inserting a new node at the end of the list.
  • After a specific node: Inserting a new node after a given node in the list.
  • From the beginning: Deleting the first node from the list.
  • From the end: Deleting the last node from the list.
  • A specific node: Deleting a node with a given value or a given position in the list.
  • Forward traversal: Starting from the head node and moving towards the tail node.
  • Reverse traversal: Starting from the tail node and moving towards the head node.
  • head points to the first node of the linked list
  • next pointer of the last node is NULL, so if the next current node is NULL, we have reached the end of the linked list.

a. Method to insert data at the beginning of the linked list:

// Method to insert data at the beginning of the linked list
    void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

b. Method to insert data at the end of the linked list:

// Method to insert data at the end of the linked list
    void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

c. Method to insert data after a specific node in the linked list:

 // Method to insert data after a specific node in the linked list
    void insertAfterNode(Node prevNode, int data) {
        if (prevNode == null) {
            System.out.println("Previous node cannot be null.");
            return;
        }

Here’s the syntax for insertion of data in a singly linked list in Java:

class Node {
    int data;
    Node next;

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

class LinkedList {
    Node head;

    // Method to insert data at the beginning of the linked list
    void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // Method to insert data at the end of the linked list
    void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Method to insert data after a specific node in the linked list
    void insertAfterNode(Node prevNode, int data) {
        if (prevNode == null) {
            System.out.println("Previous node cannot be null.");
            return;
        }
        Node newNode = new Node(data);
        newNode.next = prevNode.next;
        prevNode.next = newNode;
    }
}

a. Method to delete the first node from the linked list:

// Method to delete the first node from the linked list
    public void deleteFirst() {
        if (head == null)
            return;

        head = head.next;
    }

b. Method to delete the last node from the linked list:

// Method to delete the last node from the linked list
    public void deleteLast() {
        if (head == null || head.next == null) {
            head = null;
            return;
        }

        Node temp = head;
        while (temp.next.next != null) {
            temp = temp.next;
        }
        temp.next = null;
    }

c. Method to delete a node with a specific data value:

///Method to delete a node with a specific data value
    public void deleteNode(int key) {
        Node temp = head;
        Node prev = null;

        // If the node to be deleted is the head node
        if (temp != null && temp.data == key) {
            head = temp.next;
            return;
        }

Here’s a basic syntax for deletion operations in a singly linked list in Java:

class Node {
    int data;
    Node next;

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

class LinkedList {
    Node head;

    // Method to delete the first node from the linked list
    public void deleteFirst() {
        if (head == null)
            return;

        head = head.next;
    }

    // Method to delete the last node from the linked list
    public void deleteLast() {
        if (head == null || head.next == null) {
            head = null;
            return;
        }

        Node temp = head;
        while (temp.next.next != null) {
            temp = temp.next;
        }
        temp.next = null;
    }

    // Method to delete a node with a specific data value
    public void deleteNode(int key) {
        Node temp = head;
        Node prev = null;

        // If the node to be deleted is the head node
        if (temp != null && temp.data == key) {
            head = temp.next;
            return;
        }

        // Search for the node to be deleted, keeping track of the previous node
        while (temp != null && temp.data != key) {
            prev = temp;
            temp = temp.next;
        }

        // If key was not present in the linked list
        if (temp == null)
            return;

        // Unlink the node from the linked list
        prev.next = temp.next;
    }
}

a. Method to traverse the linked list forward:

// Method to traverse the linked list forward
    public void forwardTraversal() {
        Node current = head;
        System.out.print("Forward Traversal: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

b. Method to traverse the linked list in reverse:

// Method to traverse the linked list in reverse
    public void reverseTraversal() {
        Node prev = null;
        Node current = head;
        Node next = null;
        System.out.print("Reverse Traversal: ");
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head = prev;
        // Now head points to the last node
        current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

Here’s a basic syntax for traversing a singly linked list in Java, both forward and reverse:

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

class LinkedList {
    Node head;

    // Method to traverse the linked list forward
    public void forwardTraversal() {
        Node current = head;
        System.out.print("Forward Traversal: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    // Method to traverse the linked list in reverse
    public void reverseTraversal() {
        Node prev = null;
        Node current = head;
        Node next = null;
        System.out.print("Reverse Traversal: ");
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head = prev;
        // Now head points to the last node
        current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    // Method to 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;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);

        // Forward traversal
        list.forwardTraversal();

        // Reverse traversal
        list.reverseTraversal();
    }
}

How can we help?

Leave a Reply

Your email address will not be published. Required fields are marked *