Array-urile stochează elementele în locații de memorie contiguă, rezultând adrese ușor de calculat pentru elementele stocate și acest lucru permite un acces mai rapid la un element la un anumit index. Listele legate sunt mai puțin rigide în structura lor de stocare, iar elementele nu sunt de obicei stocate în locații contigue, prin urmare trebuie să fie stocate cu etichete suplimentare care oferă o referință la următorul element. Această diferență în ceea ce privește schema de stocare a datelor decide ce structură de date ar fi mai potrivită pentru o anumită situație.

Schema de stocare de date a unui array

Schema de stocare de date a unei liste legate

Diferențele majore sunt enumerate mai jos:

• Dimensiunea: Deoarece datele pot fi stocate numai în blocuri contigue de memorie într-o matrice, dimensiunea acestora nu poate fi modificată în timpul execuției din cauza riscului de suprascriere peste alte date. Cu toate acestea, într-o listă legată, fiecare nod indică spre cel următor, astfel încât datele pot exista la adrese dispersate (necontinue); acest lucru permite o dimensiune dinamică care se poate modifica în timpul execuției.
• Alocarea memoriei: Pentru array-uri în momentul compilării și în momentul execuției pentru listele legate.
• Eficiența memoriei: Pentru același număr de elemente, listele legate utilizează mai multă memorie deoarece o referință la nodul următor este, de asemenea, stocată împreună cu datele. Cu toate acestea, flexibilitatea dimensiunii în listele legate poate face ca acestea să utilizeze mai puțină memorie în general; acest lucru este util atunci când există incertitudine cu privire la dimensiune sau există variații mari în ceea ce privește dimensiunea elementelor de date; memoria echivalentă cu limita superioară a dimensiunii trebuie să fie alocată (chiar dacă nu este utilizată în totalitate) atunci când se utilizează array-uri, în timp ce listele legate își pot crește dimensiunile pas cu pas proporțional cu cantitatea de date.
• Timp de execuție: Orice element dintr-o matrice poate fi accesat direct cu ajutorul indicelui său; cu toate acestea, în cazul unei liste legate, trebuie parcurse toate elementele anterioare pentru a ajunge la orice element. De asemenea, o mai bună localizare a cache-ului în array-uri (datorită alocării de memorie contiguă) poate îmbunătăți semnificativ performanța. Ca urmare, unele operații (cum ar fi modificarea unui anumit element) sunt mai rapide în array-uri, în timp ce altele (cum ar fi inserarea/eliminarea unui element în date) sunt mai rapide în listele legate.

Cele ce urmează sunt puncte în favoarea listelor legate.
(1) Dimensiunea tablourilor este fixă: Deci trebuie să cunoaștem în prealabil limita superioară a numărului de elemente. De asemenea, în general, memoria alocată este egală cu limita superioară, indiferent de utilizare, iar în utilizările practice, limita superioară este rareori atinsă.

(2) Inserarea unui nou element într-un array de elemente este costisitoare deoarece trebuie creat un spațiu pentru noile elemente, iar pentru a crea spațiu elementele existente trebuie să fie deplasate.

De exemplu, să presupunem că menținem o listă ordonată de ID-uri într-un array id.

id = .

Și dacă dorim să inserăm un nou ID 1005, atunci, pentru a menține ordinea ordonată, trebuie să mutăm toate elementele de după 1000 (excluzând 1000).

Ștergerea este, de asemenea, costisitoare cu array-uri până când dacă nu se folosesc unele tehnici speciale. De exemplu, pentru a șterge 1010 în id, tot ce este după 1010 trebuie mutat.

Așa că lista legată oferă următoarele două avantaje față de array-uri
1) Dimensiunea dinamică
2) Ușurința inserției/ștergerii

Listele legate au următoarele dezavantaje:
1) Accesul aleatoriu nu este permis. Trebuie să accesăm elementele în mod secvențial, începând cu primul nod. Așadar, nu putem face o căutare binară cu listele legate.
2) Este necesar spațiu suplimentar de memorie pentru un pointer cu fiecare element al listei.
3) Listele au o localitate mai bună a cache-ului care poate face o diferență destul de mare în ceea ce privește performanța.

.