Introduction to Linked Lists

Linked lists are an important data structure in computer science. They are used to store and manipulate a collection of elements. Unlike arrays, linked lists do not require contiguous memory allocation.

Each element in a linked list contains a value and a reference to the next element in the list. This means that the elements are connected in a chain-like structure, where each element points to the next element.

Here is an example of a simple linked list implementation in Java:

1{...code}

In the above code, we define a Node class that represents an element in the linked list. Each node has a data field to store the value and a next field to point to the next node in the list.

The LinkedList class is used to manage the linked list. It has a head field that points to the first element in the list. The insert method adds a new element to the end of the list, and the display method prints the elements of the list.

Linked lists have several advantages over arrays. First, they allow for efficient insertion and deletion operations, as the elements do not need to be shifted. Second, they can dynamically grow and shrink in size, as memory is allocated only when new elements are added. Lastly, linked lists can easily be extended to implement other data structures, such as stacks and queues.

To summarize, linked lists are a flexible and efficient data structure that provides advantages over arrays. They are widely used in various algorithms and data manipulation tasks.

xxxxxxxxxx

}

class Node {

  int data;

  Node next;

​

  public Node(int data) {

    this.data = data;

    this.next = null;

  }

}

​

public class LinkedList {

  Node head;

​

  public LinkedList() {

    this.head = null;

  }

​

  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;

    }

  }

Creating a Linked List

To create a linked list, we first need to define the Node class, which represents an element in the list. Each Node object contains a data field to store the value of the element and a next field to point to the next element in the list.

In Java, the Node class can be defined as follows:

1class Node {
2    int data;
3    Node next;
4
5    public Node(int data) {
6        this.data = data;
7        this.next = null;
8    }
9}

Once the Node class is defined, we can create the LinkedList class to manage the linked list. The LinkedList class has a head field to point to the first element in the list.

To create a new linked list, we can initialize the head to null, indicating an empty list.

1LinkedList ll = new LinkedList();

To add elements to the linked list, we create a new Node object with the desired value and set its next field to null. If the list is empty, we set the head to the new node. Otherwise, we traverse the list until we reach the last node and set its next field to the new node.

Here's an example of adding elements to the linked list:

1ll.add(10);
2ll.add(20);
3ll.add(30);

To display the elements of the linked list, we start at the head and traverse the list, printing the value of each node.

1ll.display();

The output of the above code would be:

110
220
330

xxxxxxxxxx

}

public class Main {

    public static void main(String[] args) {

        // Creating an empty linked list

        LinkedList ll = new LinkedList();

​

        // Adding elements to the list

        ll.add(10);

        ll.add(20);

        ll.add(30);

​

        // Displaying the list

        ll.display();

    }

}

​

class Node {

    int data;

    Node next;

​

    public Node(int data) {

        this.data = data;

        this.next = null;

    }

}

​

class LinkedList {

    Node head;

​

    public void add(int data) {

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.

Deletion is an important operation in a linked list that involves removing nodes from the list. There are various approaches to deleting elements from a linked list, depending on the position of the node to be deleted and the desired behavior of the list.

1. Deleting at the beginning

To delete the first node of a linked list, we simply update the head to point to the next node.

1public void deleteAtBeginning() {
2    if (head != null) {
3        head = head.next;
4    }
5}

2. Deleting at the end

To delete the last node of a linked list, we need to traverse the list until we reach the second-to-last node. Then, we update the next field of the second-to-last node to null.

1public void deleteAtEnd() {
2    if (head == null || head.next == null) {
3        head = null;
4    } else {
5        Node current = head;
6        while (current.next.next != null) {
7            current = current.next;
8        }
9        current.next = null;
10    }
11}

3. Deleting at a specific position

To delete a node at a specific position within a linked list, we need to traverse the list until we reach the position-1. Then, we update the next field of the previous node to skip the node to be deleted.

1public void deleteAtPosition(int position) {
2    if (position == 0) {
3        deleteAtBeginning();
4    } else {
5        Node current = head;
6        for (int i = 0; i < position - 1 && current != null; i++) {
7            current = current.next;
8        }
9        if (current != null && current.next != null) {
10            current.next = current.next.next;
11        }
12    }
13}

These are some basic methods for deleting elements from a linked list. Depending on the situation and requirements, additional logic may be needed to handle special cases, such as deleting multiple occurrences of a value or deleting nodes based on specific conditions.

By using these methods, you can effectively delete elements from a linked list and maintain the structure as needed. It's important to consider the time and space complexity of each method when performing deletions, especially in scenarios involving large lists or performance-critical applications.

xxxxxxxxxx

}

public void deleteAtBeginning() {

    if (head != null) {

        head = head.next;

    }

}

​

public void deleteAtEnd() {

    if (head == null || head.next == null) {

        head = null;

    } else {

        Node current = head;

        while (current.next.next != null) {

            current = current.next;

        }

        current.next = null;

    }

}

​

public void deleteAtPosition(int position) {

    if (position == 0) {

        deleteAtBeginning();

    } else {

        Node current = head;

        for (int i = 0; i < position - 1 && current != null; i++) {

            current = current.next;

        }

        if (current != null && current.next != null) {

            current.next = current.next.next;

        }

Searching is a fundamental operation in data structures that allows us to find a specific element in a collection. In a linked list, searching for an element involves traversing through the list and comparing each node's value with the target value.

To implement the search functionality in a linked list, we can start from the head node and traverse the list until we find the desired element or reach the end.

Here's an example of a method that performs a search for a given value in a singly linked list:

1search(int value) {
2    Node current = head;
3    while (current != null) {
4        if (current.data == value) {
5            return true;
6        }
7        current = current.next;
8    }
9    return false;
10}

In the above code, we initialize a current variable with the head node and iterate through the list by updating the current to its next node. We compare the data value of each node with the target value. If we find a match, we return true. If we reach the end of the list without finding a match, we return false.

The time complexity of the search operation in a linked list is O(n), where n is the number of nodes in the list. In the worst case, we need to traverse the entire list to find the target element.

Now that you understand how to implement the search functionality in a linked list, you can use this knowledge to find specific elements within your linked list and perform various operations based on the search result.

xxxxxxxxxx

public boolean search(int value) {

    Node current = head;

    while (current != null) {

        if (current.data == value) {

            return true;

        }

        current = current.next;

    }

    return false;

}

To reverse a linked list, we need to change the direction of the pointers of each node. We can achieve this by traversing the list and updating the next pointer of each node to point to its previous node. We also need to keep track of the previous, current, and next nodes while traversing.

Here's a simple algorithm to reverse a singly linked list:

1. Initialize three pointers: prev, current, and next. Set prev and next to null, and current to the head of the list.
2. Iterate through the list while the current pointer is not null:
   1. Set next to the next node of current.
   2. Change the next pointer of current to point to prev.
   3. Update prev to current.
   4. Update current to next.
3. After the iteration, update the head of the list to point to the prev node, which is now the new first node of the reversed list.

Here's an example of a Java code snippet that reverses a singly linked list:

1class Node {
2  int data;
3  Node next;
4
5  public Node(int data) {
6      this.data = data;
7      this.next = null;
8  }
9}
10
11class LinkedList {
12  Node head;
13
14  // Reverse the linked list
15  void reverse() {
16      Node prev = null;
17      Node current = head;
18      Node next = null;
19
20      while (current != null) {
21          next = current.next;
22          current.next = prev;
23          prev = current;
24          current = next;
25      }
26      head = prev;
27  }
28}

xxxxxxxxxx

class Main {

  public static void main(String[] args) {

    // replace with your Java logic here

    Node prev = null;

    Node current = head;

    Node next = null;

​

    while (current != null) {

        next = current.next;

        current.next = prev;

        prev = current;

        current = next;

    }

    head = prev;

  }

}

To detect a cycle in a linked list, we can use the "fast and slow pointers" technique. This technique involves initializing two pointers: slow and fast. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time.

If the linked list contains a cycle, the slow and fast pointers will eventually meet at the same node. To determine the starting node of the cycle, we reset the slow pointer to the head of the list and then move both pointers at a rate of one node per step. The point at which they meet again is the starting node of the cycle.

Here's an example of Java code that detects a cycle in a linked list:

1public class LinkedList {
2
3    static Node head;
4
5    static class Node {
6        int data;
7        Node next;
8
9        Node(int d) {
10            data = d;
11            next = null;
12        }
13    }
14
15    // Function to detect and return the starting node of a cycle in the linked list
16    static Node detectCycle(Node head) {
17        if (head == null || head.next == null) {
18            return null;
19        }
20
21        Node slow = head;
22        Node fast = head;
23        while (fast != null && fast.next != null) {
24            slow = slow.next;
25            fast = fast.next.next;
26
27            // If slow and fast pointers meet, there is a cycle
28            if (slow == fast) {
29
30                // Reset slow pointer to head
31                slow = head;
32
33                /* Move both slow and fast pointers one node at a time
34                   until they meet at the starting node of the cycle */
35                while (slow != fast) {
36                    slow = slow.next;
37                    fast = fast.next;
38                }
39                return slow;
40            }
41        }
42
43        // If no cycle is present in the linked list
44        return null;
45    }
46
47    public static void main(String[] args) {
48        LinkedList list = new LinkedList();
49
50        // Create a linked list with a cycle
51        list.head = new Node(1);
52        list.head.next = new Node(2);
53        list.head.next.next = new Node(3);
54        list.head.next.next.next = new Node(4);
55        list.head.next.next.next.next = new Node(5);
56        list.head.next.next.next.next.next = list.head.next;
57
58        Node cycleStart = detectCycle(head);
59        if (cycleStart != null) {
60            System.out.println("Cycle found at node: " + cycleStart.data);
61        } else {
62            System.out.println("No cycle found in the linked list");
63        }
64    }
65}

xxxxxxxxxx

}

```java

public class LinkedList {

​

    static Node head;

​

    static class Node {

        int data;

        Node next;

​

        Node(int d) {

            data = d;

            next = null;

        }

    }

​

    // Function to detect and return the starting node of a cycle in the linked list

    static Node detectCycle(Node head) {

        if (head == null || head.next == null) {

            return null;

        }

​

        Node slow = head;

        Node fast = head;

        while (fast != null && fast.next != null) {

            slow = slow.next;

            fast = fast.next.next;

​

            // If slow and fast pointers meet, there is a cycle

            if (slow == fast) {