Struktur data tertaut adalah kumpulan data yang disusun dalam format seperti daftar. Setiap bagian datum dalam daftar disebut sebagai simpul. Setiap simpul terhubung ke yang berikutnya dalam daftar dengan referensi ke alamat memori node berikutnya. Struktur data yang terhubung digunakan sebagai pengganti array ketika jumlah node pada daftar tidak diketahui atau mungkin bertambah atau berkurang selama eksekusi program Jenis yang paling umum dari struktur data tertaut disebut daftar tertaut.
Sebuah node dari struktur data tertaut umumnya berisi dua bagian informasi — referensi ke data aktual yang disimpan dan referensi ke node berikutnya dalam daftar. Daftar tertaut dilintasi, atau dicari, dengan melangkah melalui masing-masing node data, mulai dari yang pertama, atau kepala daftar.Tidak ada cara untuk menemukan informasi dalam daftar tertaut tanpa bergerak secara berurutan melalui node dari awal hingga akhir.
Sebagian besar struktur data tertaut akan menggunakan memori sesedikit mungkin selama eksekusi program. Jika daftar tertaut dibuat hanya dengan satu simpul dan tidak ada simpul lain yang ditambahkan, daftar itu akan menggunakan memori yang dibutuhkan hanya untuk satu node. Ini sangat kontras dengan struktur data array di mana ukuran seluruh array harus dideklarasikan dan dialokasikan pada awal program dan tidak dapat diubah .
Daftar tertaut membayar efisiensi penggunaan sumber daya memori dengan membutuhkan lebih banyak daya komputasi. Menemukan bagian data tertentu dalam daftar tertaut memerlukan pengulangan seluruh daftar setiap saat, sehingga dapat lebih lambat untuk mengakses informasi di tengah daftar Menghapus atau menyusun ulang data dalam daftar tertaut juga bisa lebih intensif secara komputasi daripada mengelola larik di mana elemen dapat ditukar dengan mudah.
Struktur data yang ditautkan tidak diharuskan hanya memiliki satu referensi ke node berikutnya; itu dapat memiliki beberapa. Beberapa daftar tertaut memiliki dua referensi simpul, satu ke simpul berikutnya dalam daftar dan satu ke simpul sebelumnya. Ini dikenal sebagai daftar tertaut ganda. Ini dapat membuat perpindahan melalui daftar di kedua arah jauh lebih cepat, meskipun dengan mengorbankan peningkatan penggunaan memori untuk struktur data.
Daftar tertaut mungkin memiliki tiga atau lebih referensi ke node lain dalam daftar. Ini menciptakan struktur yang mirip dengan pohon dengan seluruh cabang node yang muncul dari satu node. Jenis data ini strukturnya disebut daftar tertaut ganda. Daftar tertaut berganda sangat berguna untuk algoritme pengurutan kompleks yang digunakan untuk menyusun data. Pohon pencarian dimungkinkan sebagian besar karena penggunaan struktur data tertaut untuk membuat banyak cabang dengan panjang variabel.