मेरा उत्तर about spatial and temporal locality देखें।
विशेष रूप से, सरणी संगत स्मृति ब्लॉक होते हैं, इसलिए उनमें से बड़े हिस्से को पहली पहुंच पर कैश में लोड किया जाएगा। यह सरणी के भविष्य के तत्वों तक पहुंचने के लिए अपेक्षाकृत तेज़ बनाता है। दूसरी ओर लिंक्ड सूचियां आवश्यक रूप से स्मृति के संगत ब्लॉक में नहीं हैं, और अधिक कैश मिस का कारण बन सकती हैं, जो उन्हें एक्सेस करने में लगने वाले समय को बढ़ाती है।
एक सरणी data
निम्नलिखित संभव स्मृति लेआउट और बड़े structs
Address Contents | Address Contents
ffff 0000 data[0] | ffff 1000 l_data
ffff 0040 data[1] | ....
ffff 0080 data[2] | ffff 3460 l_data->next
ffff 00c0 data[3] | ....
ffff 0100 data[4] | ffff 8dc0 l_data->next->next
| ffff 8e00 l_data->next->next->next
| ....
| ffff 8f00 l_data->next->next->next->next
अगर हम इस सरणी के माध्यम से लूप करना चाहता था की लिंक्ड सूची l_data
पर विचार करें, ffff 0000
तक पहली पहुँच हमें की आवश्यकता होगी करने के लिए स्मृति में जाने के लिए पुनर्प्राप्त करें (सीपीयू चक्रों में एक बहुत धीमी ऑपरेशन)। हालांकि, पहली पहुंच के बाद बाकी सरणी कैश में होगी, और बाद में पहुंच बहुत तेज होगी। लिंक्ड सूची के साथ, ffff 1000
की पहली पहुंच के लिए हमें स्मृति में जाने की भी आवश्यकता होगी। दुर्भाग्यवश, प्रोसेसर सीधे इस स्थान के आस-पास स्मृति को कैश करेगा, ffff 2000
तक सभी तरह से कहें। जैसा कि आप देख सकते हैं, यह वास्तव में सूची के किसी भी अन्य तत्व को कैप्चर नहीं करता है, जिसका अर्थ है कि जब हम l_data->next
तक पहुंचने के लिए जाते हैं, तो हमें फिर से स्मृति में जाना होगा।
यदि आप समझते हैं कि कैसे [कैश] (http://en.wikipedia.org/wiki/Locality_of_reference) काम करता है, तो आप यह भी समझेंगे 1) "संदर्भ की लोकैलिटी" एक अच्छी बात है, और 2) डेटा तक पहुंच सरणी से आमतौर पर सूची से उसी डेटा तक पहुंचने से बेहतर "इलाके" होने की अधिक संभावना होती है। – paulsm4
ध्यान देने योग्य एक बात यह है कि यह सच है, एक संगत आवंटक के साथ संयुक्त एक सिंगल-लिंक्ड सूची एक विशाल संपत्ति हो सकती है, मुख्य रूप से क्योंकि एक कंटेनर से दूसरे तत्वों को स्थानांतरित करने में केवल पॉइंटर तर्क शामिल होता है। यदि आप उन लोगों के मेमोरी लेआउट को देखते हैं, हालांकि, यह संगत है और सरणी में अगले तत्व के लिंक के साथ एक सरणी की तरह दिखता है, और इसलिए यह अभी भी कैश-अनुकूल है (कम से कम जब तक सूची सभी पुनर्गठित नहीं हो जाती है)। –