kuis

mengapa dalam penyimpanan data diperlukan sebuah struktur yang baik ?

• supaya data terlihat rapi

• menghemat memori penyimpanan

• supaya data tidak hilang

• supaya lebih mudah/efisien dalam pengaksessan /pemrosesan data tersebut

Sebuah linked list dilengkapi dengan beberapa atribut reference (selain data elemennya), KECUALI:

• First/Header: reference/pointer yang menunjuk ke elemen pertama.

• Last/Tail: reference/pointer yang menunjuk ke elemen pertama.

• Next: reference/pointer yang menunjuk elemen berikutnya

• Prev: reference/pointer yang menunjuk elemen di posisi selanjutnya

Linked List atau List linier adalah:

• Sekumpulan elemen bertipe sama, yang mempunyai “keterurutan” tertentu, dan setiap elemennya terdiri dari dua bagian, yaitu informasi mengenai elemennya, dan informasi mengenai isi dari elemen suksesornya (pointer/reference)

• Sekumpulan elemen bertipe berbeda,yang mempunyai “keterurutan” tertentu, dan setiap elemennya terdiri dari dua bagian, yaitu informasi mengenai elemennya, dan informasi mengenai alamat elemen suksesornya (pointer/reference)

• Sekumpulan elemen bertipe sama,tidak ada keterurutan, dan setiap elemennya terdiri dari dua bagian, yaitu informasi mengenai elemennya, dan informasi mengenai alamat elemen suksesornya (pointer/reference)

• Sekumpulan elemen bertipe sama,yang mempunyai “keterurutan” tertentu, dan setiap elemennya terdiri dari dua bagian, yaitu informasi mengenai elemennya, dan informasi mengenai alamat elemen suksesornya (pointer/reference)

Mengakses suatu elemen, get/set maka:

• Elemen array dapat dengan mudah diakses melalui indeks (jika diketahui indeks).

• Pengakses suatu elemen pada linked list dapat dengan mudah diakses melalui indeks

• Pengakses suatu elemen pada array butuh mekanisme khusu

• Pengakses suatu elemen pada array dan linked list butuh mekanisme khusus

Proses membuat sebuah node baru di antara 2 buah node lalu meletakkan sebuah nilai pada field elemen baru, node selanjutnya dari node baru adalah node di akhir dan node selanjutnya dari node awal adalah node baru. Ini adalah proses:

• Menghapus elemen

• Mengedit elemen

• Menyisipkan elemen baru

• Menambah elemen

Kenapa kita membutuhkan struktur List Linier/linked List?

• Array menyimpan kumpulan elemen secara non-contiguous.

• Dengan array, ukuran array harus tidak harus ditentukan di awal dan bisa melewati batas ukuran yang sudah ditentukan

• Dengan linked list, penambahan jumlah elemen tidak dapat dilakukan dengan bebas

• Dengan array, ukuran array harus ditentukan di awal dan tidak bisa melewati batas ukuran yang sudah ditentukan

Penghapusan pada posisi tertentu (delete after/before):

• Array: tanpa pergeseran elemen lain, O(1). Linked list: tanpa pergeseran elemen lain, O(1) - ada Last, O(n) - tanpa Last

• Array: menyebabkan pergeseran elemen lain, O(n). Linked list: tanpa pergeseran elemen lain, O(1).

• Array: menyebabkan pergeseran elemen lain, O(n). Linked list: ada proses iterasi, O(n).

• Array: tanpa pergeseran elemen lain, O(1). Linked list: tanpa pergeseran elemen lain, O(1) - tanpa Last, O(n) - ada Last

Penambahan di akhir (insert last):

• Array: menyebabkan pergeseran elemen lain, O(n). Linked list: tanpa pergeseran elemen lain, O(1).

• Array: tanpa pergeseran elemen lain, O(1). Linked list: tanpa pergeseran elemen lain, O(1)- tanpa Last, O(n) - ada Last

• Array: menyebabkan pergeseran elemen lain, O(n). Linked list: ada proses iterasi, O(n).

• Array: tanpa pergeseran elemen lain, O(1). Linked list: tanpa pergeseran elemen lain, O(1) - ada Last, O(n) - tanpa Last

Penambahan di awal (insert first):

• Array: menyebabkan pergeseran elemen lain, O(n). Linked list: ada proses iterasi, O(n).

• Array: menyebabkan pergeseran elemen lain, O(n). Linked list: tanpa pergeseran elemen lain, O(1)

• Array: tanpa pergeseran elemen lain, O(1). Linked list: tanpa pergeseran elemen lain, O(1)- tanpa Last, O(n) - ada Last

• Array: tanpa pergeseran elemen lain, O(1). Linked list: tanpa pergeseran elemen lain, O(1) - ada Last, O(n) - tanpa Last

Proses mengabaikan elemen dengan cara melewati pointer (reference) dari elemen tersebut langsung pada elemen selanjutnya. Elemen tersebut kemudian dihapus dengan meng-assign field next pada elemen sebelumnya dengan alamat elemen selanjutnya. Ini adalah proses:

• Menghapus elemen

• Menambah elemen

• Mengedit elemen

• Menyisipkan elemen baru