Question

To class DoublyLinkedList, add method search(E e) that receives an element e and returns the node number that has the element (assume first node is number 1), if there is no node has that element , it returns -1

java language

Answer 1

Steps to make a Doubly Linked List:

1. First we will define a class node which will consist of a node and two pointers that is next and previous.

2.Once our class is made we can insert any number of nodes, this inserting can easily be done at previous, next of a certain position and in a normal straight pattern too.

3.As Doubly Linked List can traverse in both the forward and backward directions, many operations like insertion, deletion though the search operation takes place in the same time for both the list.

4. As a disadvantage, here each node has a heigher amount of memory space.

Algorithm of Search Operation:

Brute Force :

1. Taken a bool variable f which will currently be false.

2. A pointer Current will initially point to head.

3. Iterate through each element, and check if the node data is equal to the required element.

4.If yes then make f = true.

5. If f is true, return the node number else return -1.

Code:

public class SearchList {
  
    class Node{

        // three pointers for the doubly linked list

        int data;
        Node previous;
        Node next;

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

    //Initialise the head and tail of doubly linked list to be formed
    Node head, tail = null;

    //This function will add a node to the list
    public void add_data(int data) {
        Node newNode = new Node(data);

        if(head == null) {

            head = tail = newNode;
            head.previous = null;
            tail.next = null;
        }
        else {
            tail.next = newNode;
            newNode.previous = tail;
            tail = newNode;
            tail.next = null;
        }
    }

    //searchNode() will search a given node in the list
    public void searchNode(int key) {

        //starting with the 1st node
        int i = 1;
        boolean f = false;

        //current Node will point to head
        Node current = head;

        if(head == null) {
            System.out.println("List empty");
            return;
        }

        while(current != null) {

            //Compare the key each Node in the doubly linked list
            if(current.data == key) {
                f = true;
                break;
            }
            current = current.next;
            i++;
        }
        if(f)
             System.out.println("Node is present at: " + i);
        else
             System.out.println("-1");
    }

    public static void main(String[] args) {

        SearchList dBLL = new SearchList();
        dBLL.add_data(20);
        dBLL.add_data(50);
        dBLL.add_data(87);
        dBLL.add_data(64);
        dBLL.add_data(32);

        //Case when Node will be found
        dBLL.searchNode(50);

        //Case when Node will not be found
        dBLL.searchNode(2);
    }
}

NOTE: Save the file as SearchList.java.

Attaching the screenshot of code and output for the sake of reference. If any doubts can comment in the thread.