Waktu awal dapet mata kuliah Algoritma dan bahas LinkedList, awalna kukira struktur data ini udah ada fitur bawaannya di Python. Ternyata pas dicoba, kita harus bikin sendiri dari nol pakai class Node dan class Linkedlist! Awalna mikir kalau insert di tengah pakai Array (List) bakal bikin queue berantakan(disini aku mikir di studi kasus music player, tapi ternyata bukan seperti itu), tapi ternyata urutan indeksnya tetap rapi karena otomatis digeser sama Python. Masalah utama bukan data berantakan, melainkan performa yang menurun kalau datana besar. Penasaran sama perbedaannya, akhirnya sambil nonton beberapa tutorial di YouTube, aku nyoba eksperimen pengujian langsung dengan 30.000 data buat membandingkan List biasa sama Singly LinkedList buatan sendiri. Inilah hasil bedah kodenya!

FYI:

1. Insert di Awal (Prepend)

LinkedList menang telak dibanding Array biasa (~13x lebih cepat).

1. Array (List): 0,31800 detik.
2. LinkedList: 0,02413 detik.
3. Analisis: Menyisipkan data di indeks 0 pada Array memaksa sistem menggeser seluruh 30.000 elemen ke kanan di memori (\mathcal{O}(n)). Sedangkan di LinkedList, kita cuma perlu bikin node baru dan mengalihkan pointer head (\mathcal{O}(1)).

2. Insert di Akhir (Append)

Di luar dugaan, Array (List Python) justru jauh lebih cepat dibanding LinkedList.

1. Array (List): 0,00463 detik.
2. LinkedList: 0,02915 detik.
3. Analisis: List bawaan Python diimplementasikan memakai dynamic C-array dengan alokasi memori berlebih (over-allocation). Operasi .append() beroperasi di kompleksitas \mathcal{O}(1) amortized di level bahasa C yang super cepat. Sementara LinkedList buatan sendiri di Python kena overhead karena harus membuat objek kelas baru di memori.

3. Akses Data di Tengah (Indeks 15.000)

Array menang mutlak tanpa perlawanan.

1. Array (List): 0,0000039 detik.
2. LinkedList: 0,0025743 detik.
3. Analisis: Array mendukung Random Access (\mathcal{O}(1)) karena posisi memorinya contiguous (berurutan) dan bisa langsung dihitung alamat memorinya. LinkedList wajib melakukan penelusuran (traversal) baris demi baris dari node head sampai ke node tujuan (\mathcal{O}(n)).

4. Hapus Elemen di Awal (Head)

LinkedList kembali unggul jauh untuk operasi di bagian paling depan.

1. Array (List): 0,0001952 detik.
2. LinkedList: 0,0000139 detik.
3. Analisis: Menghapus elemen pertama di Array memaksa penggeseran seluruh sisa elemen ke kiri (\mathcal{O}(n)). Di LinkedList, kita tinggal memindahkan pointer self.head = self.head.next tanpa menggeser memori fisik (\mathcal{O}(1)).