Program to search an element in a singly linked list
Explanation
In this program, we need to search a node in the given singly linked list.
To solve this problem, we will traverse through the list using a node current. Current points to head and start comparing searched node data with current node data. If they are equal, set the flag to true and print the message along with the position of the searched node.
For, eg. In the above list, a search node says 4 which can be found at the position 4.
Algorithm
- Create a class Node which has two attributes: data and next. Next is a pointer to the next node in the list.
- Create another class SearchLinkedList which has two attributes: head and tail.
- addNode[] will add a new node to the list:
- Create a new node.
- It first checks, whether the head is equal to null which means the list is empty.
- If the list is empty, both head and tail will point to a newly added node.
- If the list is not empty, the new node will be added to end of the list such that tail's next will point to a newly added node. This new node will become the new tail of the list.
- searchNode[] will search for a node in the list:
- Variable i will keep track of the position of the searched node.
- The variable flag will store boolean value false.
- Node current will point to head node.
- Iterate through the loop by incrementing current to current.next and i to i + 1.
- Compare each node's data with the searched node. If a match is found, set flag to true.
- If the flag is true, display the position of the searched node.
- Else, display the message "Element is not present in the list".
- display[] will display the nodes present in the list:
- Define a node current which will initially point to head of the list.
- Traverse through the list till current points to null.
- Display each node by making current to point to node next to it in each iteration.
Solution
Python
Output:
Element is present in the list at the position : 2 Element is not present in the list
C
Output:
Element is present in the list at the position : 2 Element is not present in the list
JAVA
Output:
Element is present in the list at the position : 2 Element is not present in the list
C#
Output:
Element is present in the list at the position : 2 Element is not present in the list
PHP
Output:
Element is present in the list at the position : 2 Element is not present in the list
Java Program to search element inside linked list
Here is our sample program to search a given node inside LinkedList in Java. We first build our linked list of numbers and insert 1003 twice to make it a duplicate number. Later we have used theindexOf[] and lastIndexOf[] method to search for a duplicate element like 1003 and a unique element 1002 inside the linked list.From the result, you can see that indexOf[] starts the search from the first element and that's why it found 1003 at the 3rd position, which is index 2. On the other hand, lastIndexOf[] starts the search from the last element and that's why it found 1003 at 6th position i.e. index 5.
Here is a sample doubly linked list data structure :
and here is our example to search duplicate and unique nodes inside LinkedList in Java.
import java.util.LinkedList; /** * Java Program to search an element inside LinkedList. * LinkedList doesn't provide random search and * time complexity of searching is O[n] * * @author java67 */ public class LinkedListSearch { public static void main[String args[]] { LinkedList ints = new LinkedList[]; ints.add[1001]; ints.add[1002]; ints.add[1003]; ints.add[1004]; ints.add[1005]; ints.add[1003]; // let's search a duplicate element in linked list // for duplicate elements indexOf[] and lastIndexOf[] will // return different indexes. System.out.println["First index of 1003 is : " + ints.indexOf[1003]]; System.out.println["Last index of 1003 is : " + ints.lastIndexOf[1003]]; // let's search an element which is not appeared twice // for unique elements both indexOf[] and lastIndexOf[] will return // same position System.out.println["First index of 1002 is : " + ints.indexOf[1002]]; System.out.println["Last index of 1002 is : " + ints.lastIndexOf[1002]]; } } Output : First index of 1003 is : 2 Last index of 1003 is : 5 First index of 1002 is : 1 Last index of 1002 is : 1
From the output, you can also see those duplicate nodes has two different positions returned by indexOf[] and lastIndexOf[] method while for unique elements both methods return the same index.
Btw, If you are good in Java but lacks data structure and algorithm skills, I strongly suggest readingData Structures and Algorithm Analysis in Javaby Mark A. Wiess. It's a great book to build your foundation on data structure and algorithms using Java programming language.
That's all about how to search an element inside LinkedList in Java. Searching an element requires traversing the list from either end, for example from head to tail or tail to head, which is what indexOf[] and lastIndexOf[] method does. You can use any of these methods to find out the index of a given element in Java, but just remember that if the element is repeated then both methods can return different indices.
If you like this tutorial and interested to learn more about linked list data structure in Java, You can also check the following Java LinkedList tutorials :
- How to add elements at the first and last position in LinkedList in Java? [example]
- The difference between LinkedList and ArrayList in Java? [answer]
- Top 5 data structures from Java Collections framework? [article]
- How to implement a linked list in Java? [solution]
- How to find the middle node of the linked list in one pass? [solution]
- How do you find the length of a singly linked list in Java? [solution]
- What is the difference between a linked list and an array in Java? [answer]
- How to find the first and last element from LinkedList in Java? [example]
- How to check if the linked list contains a loop in Java? [solution]
Java Program to search an element in a singly linked list
« Previous Next »
Java Program to search an element in a singly linked list
In this example, we will create a java program to search a node in the given singly linked list.
Program: public class Main { class Node{ int data; Node next; public Node[int data] { this.data = data; this.next = null; } } public Node head = null; public Node tail = null; public void addNode[int data] { Node newNode = new Node[data]; if[head == null] { head = newNode; tail = newNode; } else { tail.next = newNode; tail = newNode; } } public void searchNode[int data] { Node current = head; int i = 1; boolean flag = false; if[head == null] { System.out.println["List is empty"]; } else { while[current != null] { if[current.data == data] { flag = true; break; } i++; current = current.next; } } if[flag] System.out.println["Element is present in the list at the position : " + i]; else System.out.println["Element is not present in the list"]; } public static void main[String[] args] { Main sList = new Main[]; sList.addNode[1]; sList.addNode[2]; sList.addNode[3]; sList.addNode[4]; sList.searchNode[2]; sList.searchNode[7]; }}Output:-
Element is present in the list at the position : 2
Element is not present in the list
« Previous Next »
C++
// Iterative C++ program to search // an element in linked list #include using namespace std; /* Link list node */ class Node { public: int key; Node* next; }; /* Given a reference [pointer to pointer] to the head of a list and an int, push a new node on the front of the list. */ void push[Node** head_ref,int new_key] { /* allocate node */ Node* new_node =new Node[]; /* put in the key */ new_node->key = new_key; /* link the old list off the new node */ new_node->next = [*head_ref]; /* move the head to point to the new node */ [*head_ref] = new_node; } /* Checks whether the value x is present in linked list */ bool search[Node* head,int x] { Node* current = head;// Initialize current while [current != NULL] { if [current->key == x] return true; current = current->next; } return false; } /* Driver program to test count function*/ int main[] { /* Start with the empty list */ Node* head = NULL; int x = 21; /* Use push[] to construct below list 14->21->11->30->10 */ push[&head, 10]; push[&head, 30]; push[&head, 11]; push[&head, 21]; push[&head, 14]; search[head, 21]? cout Chủ Đề |