इस लेख में, हम समझेंगे कि सिंगल इटरेशन में लिंक्ड लिस्ट का मध्य एलिमेंट कैसे प्राप्त करें। java.util.LinkedList क्लास ऑपरेशन्स वे परफॉर्म करते हैं जो हम डबल-लिंक्ड लिस्ट के लिए उम्मीद कर सकते हैं। ऑपरेशन्स जो लिस्ट में इंडेक्स करते हैं, लिस्ट को शुरुआत या अंत से ट्रैवर्स करेंगे, जो भी निर्दिष्ट इंडेक्स के करीब हो।
नीचे इसका प्रदर्शन है:
मान लीजिए हमारा इनपुट है:
इनपुट लिंक्ड लिस्ट: 100 200 330
वांछित आउटपुट होगा:
लिस्ट का मध्य एलिमेंट है: 200
एल्गोरिदम
चरण 1 - शुरू चरण 2 - एक LinkedList घोषित करें जिसका नाम input_list हो। पांच नोड ऑब्जेक्ट्स घोषित करें: head, first_node, second_node, pointer_1, pointer_2। चरण 3 - मान परिभाषित करें चरण 4 - व्हाइल लूप का उपयोग करके लिंक्ड लिस्ट पर इटरेट करें, pointer_1 और pointer_2 का उपयोग करके लिस्ट को ट्रैवर्स करके मध्य एलिमेंट प्राप्त करें जब तक pointer_1.next null न हो। चरण 5 - pointer_2 मान को परिणाम के रूप में प्रदर्शित करें चरण 6 - रुकें
उदाहरण 1
यहाँ, हम सभी ऑपरेशन्स को 'main' फंक्शन के तहत बांधते हैं।
public class LinkedList {
Node head;
static class Node {
int value;
Node next;
Node(int d) {
value = d;
next = null;
}
}
public static void main(String[] args) {
LinkedList input_list = new LinkedList();
input_list.head = new Node(100);
Node second_node = new Node(200);
Node third_node = new Node(330);
input_list.head.next = second_node;
second_node.next = third_node;
Node current_node = input_list.head;
System.out.print("लिंक्ड लिस्ट परिभाषित है: ");
while (current_node != null) {
System.out.print(current_node.value + " ");
current_node = current_node.next;
}
Node pointer_1 = input_list.head;
Node pointer_2 = input_list.head;
while (pointer_1.next != null) {
pointer_1 = pointer_1.next;
if (pointer_1.next != null) {
pointer_1 = pointer_1.next;
pointer_2 = pointer_2.next;
}
}
System.out.println("\nलिस्ट का मध्य एलिमेंट है: " + pointer_2.value);
}
}
आउटपुट
लिंक्ड लिस्ट परिभाषित है: 100 200 330 लिस्ट का मध्य एलिमेंट है: 200
उदाहरण 2
यहाँ, हम ऑपरेशन्स को फंक्शन्स में एनकैप्सुलेट करते हैं जो ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग प्रदर्शित करते हैं।
public class LinkedList {
Node head;
static class Node {
int value;
Node next;
Node(int d) {
value = d;
next = null;
}
}
static void get_middle_item(LinkedList input_list) {
Node pointer_1 = input_list.head;
Node pointer_2 = input_list.head;
while (pointer_1.next != null) {
pointer_1 = pointer_1.next;
if (pointer_1.next != null) {
pointer_1 = pointer_1.next;
pointer_2 = pointer_2.next;
}
}
System.out.println("\nलिस्ट का मध्य एलिमेंट है: " + pointer_2.value);
}
public static void main(String[] args) {
LinkedList input_list = new LinkedList();
input_list.head = new Node(100);
Node second_node = new Node(200);
Node third_node = new Node(330);
input_list.head.next = second_node;
second_node.next = third_node;
Node current_node = input_list.head;
System.out.print("लिंक्ड लिस्ट परिभाषित है: ");
while (current_node != null) {
System.out.print(current_node.value + " ");
current_node = current_node.next;
}
get_middle_item(input_list);
}
}
आउटपुट
लिंक्ड लिस्ट परिभाषित है: 100 200 330 लिस्ट का मध्य एलिमेंट है: 200
एल्गोरिदम व्याख्या: टॉर्टॉइज़ और हेयर (फ्लॉयड का एल्गोरिदम)
- धीमा पॉइंटर (pointer_2): एक बार में 1 कदम आगे बढ़ता है
- तेज़ पॉइंटर (pointer_1): एक बार में 2 कदम आगे बढ़ता है
- जब तेज़ पॉइंटर अंत तक पहुंचता है: धीमा पॉइंटर मध्य पर होगा
- समय जटिलता: O(n) - सिंगल पास
- स्पेस जटिलता: O(1) - केवल दो पॉइंटर्स
विविधताएं
| लिस्ट लंबाई | मध्य (धीमा पॉइंटर) | नोट |
|---|---|---|
| विषम (3, 5, 7...) | सटीक मध्य | pointer_2 मध्य नोड पर |
| सम (2, 4, 6...) | पहला मध्य | pointer_2 दो मध्य नोड्स में से पहले पर |