2- Lingked List - Anisa Rahmawati - 21016512196

Lingked list Adalah koleksi data item yang tersusun dalam sebuah barisan  secara linear, dengan penyisipan dan pemindahan dapat dilakukan dalam semua tempat di LL tersebut.

Single Linked List

Adalah sebuah LL yang menggunakan sebuah variabel pointer saja untuk menyimpan banyak data dengan metode LL, suatu daftar isi yang saling berhubungan.

Ilustrasi single LL:

Pada gambar di atas, data terletak pada sebuah lokasi dalam sebuah memory, tempat yang disediakan memory untuk menyimpan data disebut node ? simpul, setiap node memiliki pointer ( penunjuk ) yang menunjuk ke node berikutnya sehingga terbentuk suatu untaian yang disebut single LL.

Bila dalam single LL pointer hanya dapat bergerak ke satu arah saja, maju / mundur, kanan / kiri, sehingga pencarian datanya juga hanya satu arah saja.

Single lingked list mempunyai empat element inputan yaitu :

1.       Inputan di awal.

2.       Inputan di akhir.

3.       Inputan sebelum node.

4.       Inputan sesudah node.

Node sendiri adalah Self-referential objects (object yang mereferensikan dirinya sendiri) yang disebut nodes, yang dihubungkan dengan links, membentuk kata “linked” list.

Contoh :

struct tnode {

        int value;

        struct tnode *next;

};

struct tnode *head = 0;

                        Head adalah elemen pertama untuk lingked list.
Single Linked List : Insert

Untuk menyisipkan nilai baru, pertama kita harus mengalokasikan node baru secara dinamis dan memberikan nilai padanya dan kemudian menghubungkannya dengan linked list yang ada.

Kita bisa menambahkan node di depan.

Contoh :

struct tnode *node =

            (struct tnode*) malloc(sizeof(struct tnode));

node->value = x;

node->next  = head;

head = node;

operator ( -> ) pengertiannya sama dengan :

(*node).value = x;

(*node).next  = head;

 Single Lingked List : Delete

Ada dua kondisi yang harus kita perhatikan:

Jika x berada dalam head node atau x tidak berada dalam head node.

 Contoh :

struct tnode *curr = head;

// if x is in head node

if ( head->value == x ) {

                    head = head->next;

                    free(curr);

}

// if x is in tail node

else if(tail->value == x){

                    while(curr->next!=tail) curr = curr->next;

                    free(tail); tail = curr;

                    tail->next = NULL;

}

// 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);

}

Untuk yang lokasinya berada di head

Dan untuk yang lokasinya yang bukan pada head

                 Circular Linked List

double / single LL yang simpul terakhirnya menunjuk ke simpul awal, dan simpul awalnya menunjuk ke simpul akhir, atau dapat disebut LL yang dibuat seakan-akan merupakan sebuah lingkaran dengan titik awal dan titik akhir saling bersebelahan jika LL tersebut masih kosong, ilustrasi Circular LL :

 Double Linked List

Dalam double LL ( Linked List berpointer ganda ) dapat mengatasi kelemahan-kelemahan single LL tersebut.

Ilustrasi double LL:

Contoh :

struct tnode {

                int value;

                struct tnode *next;

                struct tnode *prev;

};

struct tnode *head = 0;

struct tnode *tail = 0;

Doubly Lingked List : Insert

Sama seperti dalam satu linked list, pertama kita harus mengalokasikan

simpul baru dan tetapkan nilainya ke sana, lalu kita

hubungkan node dengan linked list yang ada.

Seharusnya kita ingin menambahkan simpul baru di belakang tail.

Contoh :

struct tnode *node =

                (struct tnode*) malloc(sizeof(struct tnode));

node->value = x;

node->next  = NULL;

node->prev  = tail;

tail->next  = node;

tail = node;

Ada 4 kondisi yang harus kita perhatikan saat menghapus:

Node yang akan dihapus adalah satu-satunya simpul dalam linked list.

Simpul yang akan dihapus adalah head.

Simpul yang akan dihapus adalah tail.

Simpul yang akan dihapus bukan head atau tail.

1.       Jika simpul yang akan dihapus adalah satu-satunya simpul:

–      free(head);

–      head = NULL;

–      tail = NULL;

2.       Jika node akan di hapus pada head :

-          head = head->next;

-          free(head->prev);

-          head->prev = NULL;

3.       Jika node akan di hapus pada tail :

-          tail = tail->prev;

-          free(tail->next);

-          tail->next = NULL;

Header Lingked List

Sebuah header linked list adalah tipe khusus linked list yang berisi node header di awal daftar.

Jadi, dalam sebuah header linked list, START (L) tidak akan mengarah ke simpul pertama dari daftar tapi START (L) akan berisi alamat simpul header.