Utökad länkad lista - en lista där varje fysiskt element innehåller flera logiska element (vanligtvis i form av en array, som möjliggör snabbare åtkomst till enskilda element).
Ger dig möjlighet att avsevärt minska minnesförbrukningen och öka prestanda jämfört med en vanlig lista. Särskilt stora minnesbesparingar uppnås med en liten storlek av logiska element och ett stort antal av dem - till exempel, en enkellänkad lista med 10 tusen fyra-byte heltal med fyra-byte minnesadressering kommer att ta 40 tusen byte för de faktiska värdena, plus 40 tusen byte för adresser, totalt 80 tusen byte; om du kombinerar siffrorna till 100 arrayer med 100 element kommer minnesförbrukningen för adresser att sjunka till 400 byte och den totala förbrukningen blir 40400 byte.
Prestandavinsten uppnås på grund av det faktum att de flesta operationerna utförs på relativt små arrayer, som vanligtvis passar helt i cacheminnet . På grund av detta kan programmets prestanda bli ännu högre än när man arbetar med konventionella arrayer. Det är lätt att lägga till nya element i en utökad lista utan att behöva skriva om hela arrayen, vilket är ett stort problem när man arbetar med vanliga arrayer.
När du implementerar måste du noggrant välja storleken på "blocket" (antalet element i arrayerna). Om blockstorleken är för stor börjar listan lida av samma problem som en vanlig array: lång infogning av element till början eller mitten, lång borttagning av element därifrån etc. Om den är för liten ökar minnesförbrukningen .