Linked List I

Linked List.

Apa itu Linked List? Linked list adalah struktur data yang terdiri dari urutan rekaman data sehingga setiap catatan ada bidang yang berisi referensi ke catatan berikutnya dalam urutan.

Linked list memungkinkan penyisipan dan penghapusan elemen apa pun di lokasi mana pun.

Linked list juga digunakan dalam banyak algoritma untuk memecahkan masalah real-time, ketika jumlah elemen yang akan disimpan tidak dapat diprediksi dan juga selama akses berurutan elemen.

Pemahaman  Menggunakan Gambar.

Contoh daftar diatas berisi dua bidang:

Nilai integer dan tautan ke simpul berikutnya.

Daftar tertaut yang simpulnya hanya berisi satu tautan tunggal ke simpul lain disebut daftar tertaut tunggal.

Perbedaan Array dengan Linked List.

Array:

• Koleksi linear elemen data.
• Simpan nilai di lokasi memori berurutan.
• Dapat acak dalam mengakses data.

Linked List:

• Kumpulan node linear.
• Tidak menyimpan simpulnya di lokasi memori berurutan.
• Hanya dapat diakses secara berurutan.

Alokasi Memori: Dinamis.

Jika Anda perlu mengalokasikan memori secara dinamis (dalam runtime), Anda dapat menggunakan “malloc” di C / C ++.

Untuk membatalkan alokasi, Anda dapat menggunakan gratis.

Contoh Coding:

int  *px = (int *) malloc(sizeof(int));

char *pc = (char *) malloc(sizeof(char));

*px = 205;

*pc = ‘A’;

printf( “%d %c\n”, *px, *pc );

free(px);

free(pc);

Untuk membuat Linked List, pertama-tama kita perlu mendefinisikan struktur simpul untuk daftar.

            struct tnode {

                        int value;

                        struct tnode *next;

            };

            struct tnode *head = 0;

Linked List Type.

Linked List terdiri dari dua jenis, yaitu:

• Single Linked List
• Double Linked List

 Single Linked List: Insert

Untuk menyisipkan nilai baru, pertama-tama kita harus secara dinamis mengalokasikan node baru dan menetapkan nilai padanya lalu menghubungkannya dengan daftar tertaut yang ada.

Single Linked List: Delete

Untuk menghapus nilai, pertama-tama kita harus menemukan lokasi simpul yang menyimpan nilai yang ingin kita hapus, dan hubungkan daftar yang tertaut lainnya.

Ada dua kondisi yang harus kita perhatikan:

jika x ada di simpul kepala atau, jika x tidak dalam simpul kepala.

Contoh Coding:

struct tnode *curr = head;

// if x is in head node

if ( head->value == x ) {

            head = head->next;

            free(curr);

}

// if x is not in head node, find the location

else {

            while ( curr->next->value != x ) curr = curr->next;

            struct tnode *del = curr->next;

            curr->next = del->next;

            free(del);

}

Ringkasan

Linked List berguna, terutama dalam memecahkan masalah waktu-nyata di mana jumlah elemen yang akan disimpan tidak dapat diprediksi dan juga selama akses berurutan elemen.

Linked list memungkinkan penyisipan dan penghapusan elemen apa pun di lokasi mana pun.

Linked List memiliki dua jenis, single and double linked list.

Single Linked List ditandai dengan memiliki tautan satu arah tunggal dari daftar yang menunjuk ke daftar lain