Prerequisite: LinkedList in java
LinkedList is a linear data structure where the elements are not stored in contiguous memory locations. Every element is a separate object known as a node with a data part and an address part. The elements are linked using pointers or references. Linked Lists are preferred over arrays in case of deletions and insertions as they take O(1) time for the respective operations.
Advantages of Linked List:
- Insertions and deletions take O(1) time.
- Dynamic in nature.
- Memory is not contiguous.
Syntax:
LinkedList<ClassName> variableName = new LinkedList<>(); Example: LinkedList<Integer> ll = new LinkedList<>();
Task:
Search for an element in a linked list.
Approach:
When the linked list is provided to us directly, we can use a for loop to traverse through the list and find the element. In case, if we are not allowed to use pre-built libraries, we need to create our very own linked list and search for the element.
Examples:
Input: ll1 = [10, 20, 30, -12, 0, 23, -2, 12]
element = 23
Output: 5
Input: ll2 = [1, 2, 3, 4, 5]
element = 3
Output: 2
The following are the two methods with which we can search for an element in a Linked List.
Method 1: When we are allowed to use in-built libraries
- First, a Linked list is initialized.
- A for loop is used to traverse through the elements present in the Linked List.
Below is the implementation of the above approach:
Java
// Java Program to find an element in a Linked List// Importing the Linked List classimport java.util.LinkedList;class SearchInALinkedList { public static void main(String[] args) { // Initializing the Linked List LinkedList<Integer> ll = new LinkedList<>(); // Adding elements to the Linked List ll.add(1); ll.add(2); ll.add(3); ll.add(4); ll.add(5); ll.add(6); ll.add(7); // Element to be searched int element = 4; // Initializing the answer to the index -1 int ans = -1; // Traversing through the Linked List for (int i = 0; i < ll.size(); i++) { // Eztracting each element in // the Linked List int llElement = ll.get(i); // Checking if the extracted element is equal to // the element to be searched if (llElement == element) { // Assigning the index of the // element to answer ans = i; break; } } // Checking if the element is present in the Linked // List if (ans == -1) { System.out.println("Element not found"); } else { System.out.println( "Element found in Linked List at " + ans); } }} |
Element found in Linked List at 3
Time Complexity: O(n) where n is the number of elements present in the linked list.
Auxiliary Space: O(1)
Method 2: When we are not allowed to use in-built libraries
- First, create a generic node class.
- Create a LinkedList class and initialize the head node to null.
- Create the required add and search functions.
- Initialize the LinkedList in the main method.
- Use the search method to find the element.
Below is the implementation of the above approach:
Java
// A Generic Node class is used to create a Linked Listclass Node<E> { // Data Stored in each Node of the Linked List E data; // Pointer to the next node in the Linked List Node<E> next; // Node class constructor used to initializes the data // in each Node Node(E data) { this.data = data; }}class LinkedList<E> { // Points to the head of the Linked // List i.e the first element Node<E> head = null; int size = 0; // Addition of elements to the tail of the Linked List public void add(E element) { // Checks whether the head is created else creates a // new one if (head == null) { head = new Node<>(element); size++; return; } // The Node which needs to be added at // the tail of the Linked List Node<E> add = new Node<>(element); // Storing the instance of the // head pointer Node<E> temp = head; // The while loop takes us to the tail of the Linked // List while (temp.next != null) { temp = temp.next; } // New Node is added at the tail of // the Linked List temp.next = add; // Size of the Linked List is incremented as // the elements are added size++; } // Searches the Linked List for the given element and // returns it's particular index if found else returns // -1 public int search(E element) { if (head == null) { return -1; } int index = 0; Node<E> temp = head; // While loop is used to search the entire Linked // List starting from the tail while (temp != null) { // Returns the index of that particular element, // if found. if (temp.data == element) { return index; } // Gradually increases index while // traversing through the Linked List index++; temp = temp.next; } // Returns -1 if the element is not found return -1; }}public class GFG { public static void main(String[] args) throws Exception { // Initializing the Linked List LinkedList<Integer> ll = new LinkedList<>(); // Adding elements to the Linked List ll.add(1); ll.add(10); ll.add(12); ll.add(-1); ll.add(0); ll.add(-19); ll.add(34); // Element to be searched int element = -1; // Searching the Linked // List for the element int ans = ll.search(-1); if (ans == -1) { System.out.println( "Element not found in the Linked List"); } else System.out.println( "Element found in the Linked List at " + ans); }} |
Element found in the Linked List at 3
Time Complexity: O(n) where n is the number of elements present in the linked list.
Auxiliary Space: O(1)
