O structură de date legată este o colecție de date aranjate într-un format asemănător unei liste. Fiecare parte de date din listă este denumită un nod. Fiecare nod este conectat la următorul din listă printr-o referință la adresa de memorie a nodului următor. Structurile de date legate sunt utilizate în locul unei matrice atunci când numărul de noduri dintr-o listă este necunoscut sau ar putea crește sau micșora pe parcursul execuția programului.Cel mai comun tip de structură de date legate se numește listă legată.
Un nod al unei structuri de date conectate conține, în general, două informații – o referință la datele reale care sunt stocate și o referință la următorul nod din listă. O listă legată este parcursă sau căutată prin pas. prin fiecare dintre nodurile de date, începând de la primul sau de la capul listei.Nu există nicio modalitate de a găsi informații într-o listă legată fără a trece succesiv prin noduri de la început până la sfârșit.
Majoritatea structurilor de date legate vor folosi cât mai puțină memorie posibil în timpul execuției programului. Dacă o listă legată este creată cu un singur nod și nu sunt adăugate alte noduri, acea listă va ocupa memorie necesară doar pentru un singur nod. Aceasta este în contrast puternic cu o structură de date matrice în care dimensiunea întregii matrice trebuie să fie declarată și alocată la începutul programului și nu poate fi modificată .
Listele conectate plătesc pentru utilizarea eficientă a resurselor de memorie, necesitând mai multă putere de calcul. Găsirea unei anumite date dintr-o listă conectată necesită parcurgerea întregii liste de fiecare dată, astfel încât accesul la informații în Înlăturarea sau reordonarea datelor dintr-o listă legată poate fi, de asemenea, mai intensă din punct de vedere al calculului decât gestionarea unei matrice în care elementele pot fi schimbate cu ușurință.
O structură de date legată nu este necesară pentru a avea o singură referință la următorul nod; poate avea mai multe. Unele liste legate au două referințe de noduri, una la următorul nod din listă și una la nodul anterior. Acestea sunt cunoscute sub numele de liste dublu legate. Acest lucru poate face deplasarea printr-un listează în ambele direcții mult mai rapid, deși în detrimentul utilizării crescute a memoriei pentru structura de date.
Este posibil ca listele conectate să aibă trei sau mai multe referințe la alte noduri din listă. Acest lucru creează o structură similară cu un arbore cu ramuri întregi de noduri care apar dintr-un singur nod. Aceste tipuri de date structurile se numesc liste cu legături multiple. Listele cu legături multiple sunt utile în special pentru algoritmii de sortare complecși care sunt utilizați pentru structurarea datelor. Arborele de căutare sunt posibile în mare parte datorită utilizării structurilor de date legate pentru a crea ramuri multiple, de lungime variabilă.