जावा में लिंक्डलिस्ट क्यों एक वास्तविक लिंक्ड सूची नहीं है?

Question

परिभाषा लिंक्ड सूची से जावा LinkedList में, एक सूची है कि यह के प्रत्येक तत्व अगले तत्व को संदर्भित करता है (और पिछले तत्व अगर हम डबल लिंक्ड सूची के बारे में बात कर रहे हैं।) http://en.wikipedia.org/wiki/Linked_list

हालांकि सूची लागू कर रहा है, कतार, डेक और अधिक। http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html

आप LinkedList में एक विधि है कि आप सूची में अगले या पिछले वस्तु देता है, सबसे अच्छा आप कर सकते हैं नहीं मिल सकता है एक इटरेटर हो और वस्तुओं को पाने के लिए है। मेरा सवाल यह है कि जावा ने इस डेटा स्ट्रक्चर लिंक्डलिस्ट को क्यों कहा है, जबकि यह वास्तव में एक लिंक्ड सूची नहीं है? एक लिंक्ड सूची इस तरह जावा में लागू किया जा सकता:

Public class MyLinkedList{ 
public int value; 
public MyLinkedList next; 
} 

Answer 1

मेरा प्रश्न यह सही मायने में किसी लिंक किए गए सूची नहीं है, जबकि, क्यों जावा इस डेटा संरचना LinkedList आह्वान किया है?

क्योंकि कार्यान्वयन इसमें एक लिंक की गई सूची है। the documentation से:

List और Deque इंटरफेस के दोगुना से जुड़े सूची कार्यान्वयन। सभी वैकल्पिक सूची संचालन लागू करता है, और सभी तत्वों को अनुमति देता है (null सहित)।

LinkedListArrayList एक List एक सरणी का उपयोग कर कार्यान्वित किया, आदि आप कौन-सी क्रम विशेषताओं के मामले में कोई फर्क कर सकते हैं चुनें एक List किसी लिंक किए गए सूची के माध्यम से लागू किया है। उदाहरण के लिए, LinkedList डॉक्स से:

आपरेशन के सभी प्रदर्शन के रूप में एक दोगुना से जुड़े सूची के लिए उम्मीद की जा सकती। सूची में अनुक्रमित ऑपरेशंस सूची या अंत से सूची को पार करेगा, जो भी निर्दिष्ट इंडेक्स के करीब है।

तो तुम उदाहरण के लिए पता है, यह है कि nextIterator ट्रेवर्सल आप iterator या listIterator से काफी कुशल हो जाएगा मिलता है, लेकिन है कि get सूचकांक द्वारा शामिल होगी पर।

Answer 2

चाहे संग्रह एक लिंक्ड सूची है या सरणी सूची उसके अनुबंध के बारे में नहीं है, बल्कि इसके कार्यान्वयन के बारे में है। LinkedList वास्तव में कार्यान्वयन द्वारा एक लिंक्ड सूची है, और अनुबंध द्वारा java.util.List है।

जहां यह दिखाता है कि यह एपीआई नहीं है, लेकिन इसकी स्पेस/टाइम जटिलता विशेषताओं, जो किसी भी लिंक्ड सूची से परिचित हैं, आसानी से अनुमान लगा सकते हैं।

संदर्भ के लिए, यह एक LinkedList नोड के वास्तविक क्रियान्वयन है आपकी अपेक्षाओं को काफी अच्छा मैच:

957 privatestaticclass Node<E> {
958  E item;
959  Node <E> next;
960  Node <E> prev;
962  Node(Node <E> prev, E element, Node <E> next) {
963   this.item = element;
964   this.next = next;
965   this.prev = prev;
966  }
967 }

Answer 3

आप LinkedList में एक विधि कि आप अगले या पिछले वस्तु देता है नहीं मिल सकता है सूची

नहीं, और यह पूरी तरह से उपयुक्त है।"सूची में अगली वस्तु" का विचार को सूची में समझ में नहीं आता है। यह एक सूची में नोड के लिए सही मायने रखता है, लेकिन ऐसा कुछ ऐसा नहीं है जो जावा एपीआई द्वारा खुलासा किया गया हो। यह आंतरिक रूप से मौजूद है, ज़ाहिर है - बस खुलासा नहीं हुआ। यदि आप सूची में पुन: प्रयास करना चाहते हैं, तो आप एक इटरेटर का उपयोग करते हैं। आप अभी भी प्रारंभ या अंत में जोड़ सकते हैं, प्रारंभ या अंत से हटा सकते हैं, और इटरेटर से जोड़/हटा सकते हैं।

जबकि आप निश्चित रूप से अपने सुझाए गए नमूना कोड के रूप में "नोड" और "सूची" की अवधारणाओं को भंग कर सकते हैं, मुझे नहीं लगता कि यह आमतौर पर एक अच्छा विचार है।

इसे एक और तरीका देने के लिए: प्राप्त करने का प्रयास कर रहे हैं जो आपको समस्याएं पैदा कर रहा है? मेरा मानना ​​है कि आप सार्वजनिक एपीआई का उपयोग करके जो करना चाहते हैं उसे करने में सक्षम होना चाहिए - आपने इसे सब कुछ नहीं देखा होगा।

Answer 4

दूसरों के सही उत्तरों के अलावा, यदि इंटरफ़ेस का अंतर्निहित कार्यान्वयन एक लिंक्ड सूची है, तो कार्यान्वयन ऑब्जेक्ट में सूची में अगला आइटम प्राप्त करने का एक तरीका होगा। उस विधि को अनुबंध के हिस्से के रूप में अभी खुलासा नहीं किया गया है।

तथ्य यह है कि कार्यान्वयन एक लिंक्ड सूची सूची अनुबंध के विभिन्न तरीकों के बिग-ओ प्रदर्शन को प्रभावित करती है।

Answer 5

हालांकि, जावा लिंक्डलिस्ट में सूची, कतार, डेक और अधिक लागू किया जा रहा है।

एपीआई के मुताबिक, लिंक्डलिस्ट उन इंटरफेस को लागू करता है ताकि इसे किसी भी संरचना का उपयोग किया जा सके।

Answer 6

जैसा कि मैंने आपके प्रश्न के माध्यम से पढ़ा है, मुझे एहसास हुआ कि आपने लिंक की गई सूची की अवधारणा और लिंक्ड सूची के कार्यान्वयन के बीच अंतर नहीं किया है।

आपका नमूना कोड लिंक की गई सूची की अवधारणा को बहुत अच्छी तरह प्रदर्शित करता है, लेकिन इसका मतलब यह नहीं है कि यह एकमात्र तरीका है या लिंक की गई सूची को लागू करने का सबसे अच्छा तरीका है। मेरा मानना ​​है कि आप किसी भी ऑपरेशन कर सकते हैं जो एक मानक लिंक्ड सूची अंतर्निहित LinkedList कक्षा का उपयोग करने में शामिल है, हालांकि आप अपने डेटा संरचना वर्ग या पाठ्यपुस्तक में देखे गए एपीआई का एक अपरिचित सेट देख सकते हैं।

तो बुनियादी तौर पर, यह एक लिंक्ड सूची जब तक आप, O(1) समय में डालने आपरेशन हासिल कर सकते हैं O(n) समय में तलाशी अभियान O(1) समय में हटाने की कार्रवाई, आदि, अन्य डेटा संरचना इस तरह की समय जटिलता के विपरीत है सरणी के रूप में

अंतर्निहित LinkedList ने next ऑपरेशन सीधे प्रदान नहीं किया लेकिन इसके पुनरावर्तक के माध्यम से। यह जावा भाषा का सिर्फ एक डिज़ाइन निर्णय था क्योंकि आपको Iterator pattern से लाभ हो सकता है।

और जावा एक सामान्य ऑब्जेक्ट उन्मुख भाषा है, जिसमें से मुख्य विशेषताएं Abstraction है।