Insertion in a Linked List

Inserting elements into a linked list involves adding new nodes at specific positions within the list. There are several methods for inserting elements into a linked list, depending on the desired position and the current state of the list.

1. Inserting at the beginning

To insert an element at the beginning of a linked list, we create a new node with the desired value and set its next field to the current head of the list. Then, we update the head to point to the new node.

1public void insertAtBeginning(int data) {
2    Node newNode = new Node(data);
3    newNode.next = head;
4    head = newNode;
5}

2. Inserting at the end

To insert an element at the end of a linked list, we traverse the list until we reach the last node. Then, we create a new node with the desired value and set the next field of the last node to the new node.

1public void insertAtEnd(int data) {
2    Node newNode = new Node(data);
3    if (head == null) {
4        head = newNode;
5    } else {
6        Node current = head;
7        while (current.next != null) {
8            current = current.next;
9        }
10        current.next = newNode;
11    }
12}

3. Inserting at a specific position

To insert an element at a specific position within a linked list, we need to locate the position and make the necessary connections. We traverse the list until we reach the position-1, create a new node with the desired value, and adjust the next fields to insert the new node.

1public void insertAtPosition(int data, int position) {
2    if (position == 0) {
3        insertAtBeginning(data);
4    } else {
5        Node newNode = new Node(data);
6        Node current = head;
7        for (int i = 0; i < position - 1 && current != null; i++) {
8            current = current.next;
9        }
10        if (current != null) {
11            newNode.next = current.next;
12            current.next = newNode;
13        }
14    }
15}

These are basic methods of inserting elements into a linked list. Depending on the situation and requirements, additional logic may be needed to handle specific cases, such as inserting duplicate elements or maintaining a sorted linked list. By using these methods, you can effectively insert elements into a linked list and manipulate the structure as needed.

Feel free to experiment with these methods and modify the linked list based on your requirements. Keep in mind the time and space complexity of each method when working with large datasets or performance-critical applications.