Introduction To Linked List (L) +Linked List Implementation 1 (L)
Sub Topic
Introduction to Linked List :
-1. Structure Declaration
-2. Structure Assignments
-3. Nested Structure
-4. Array of Structure
-5. Memory Allocation
-6. Linked List Introduction
-7. Linked List versus Array
1. Structure Declaration (Deklarasi Struktur)
=> Struktur pada dasarnya adalah tipe data yang ditentukan pengguna yang dapat menyimpan informasi terkait (bahkan dari tipe data yang berbeda) bersama-sama, sementara array hanya dapat menyimpan entitas dari tipe data yang sama. Ini adalah kumpulan variabel dengan satu nama.
Variabel dalam struktur adalah tipe data yang berbeda dan masing-masing memiliki nama yang digunakan untuk memilihnya dari struktur.
2. Structure Assignment
Sebagai Contoh :
tdata x;
• You can use operator .
(dot) to access member of x •
x.age = 17;
strcpy(x.name,
“andi”);
x.score =
82.5;
3. Nested Structure
Anda juga bisa memiliki struktur sebagai anggota struktur lain
4. Array Of Structure
Anda juga bisa memiliki susunan struktur.
5. Memory Allocation (Alokasi Memori)
=> Jika Anda perlu mengalokasikan memori secara dinamis (dalam runtime), Anda bisa gunakan malloc di C / C ++. Untuk de-mengalokasikan Anda bisa menggunakan gratis.
6. Linked List Introduction
=> suatu struktur data linier. Berbeda dengan array yang juga merupakan struktur data linier dan tipe data komposit, linked list dibentuk secara dinamik. Pada saat awal program dijalankan elemen linked list belum data. Elemenlinked list (disebut node) dibentuk sambil jalan sesuai instruksi.
Example of a list whose nodes contain two fields:
nilai integer dan link ke node berikutnya. Linked list
node mana yang hanya berisi satu link ke node lain
disebut single linked list.
7. Linked List Versus Array
Array:
- Kumpulan data elemen linier
- Simpan nilai di lokasi memori berurutan
- Bisa acak dalam mengakses data
Daftar Linked:
- Linear koleksi dari node
- Tidak menyimpan simpulnya di lokasi memori berturut-turut
- Dapat diakses hanya secara berurutan
Linked List Implementation 1 (L)
SUB TOPIC
Linked List:
- 1. Single Linked List
- 2. Polynomial Representation
- 3. Circular Single Linked List
- 4. Doubly Linked List
- 5. Circular Doubly Linked List
- 6. Header Linked List
1. Single Linked List
=> Untuk membuat daftar, pertama kita perlu mendefinisikan struktur simpul untuk daftar. Seharusnya kita ingin membuat daftar bilangan bulat.
Sebagai Contoh :
struct tnode {
int value;
struct tnode *next;
};
•
struct tnode
*head = 0;
Head adalah pointer ke elemen pertama dalam
linked list kami.
2. 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. Seharusnya kita ingin menambahkan simpul baru di depan kepala.
Sebagai Contoh :
struct tnode *node =
(struct tnode*)
malloc(sizeof(struct tnode));
node->value = x;
node->next =
head;
head = node;
Operator -> memiliki arti yang sama dengan:
(*node).value = x;
(*node).next = head;
Tambahkan simpul baru di depan kepala. Dengan asumsi sudah ada linked list
mengandung 10, 35, 27.
3. Single Linked List : Delete
=> Untuk menghapus sebuah nilai, pertama kita harus mencari lokasi node yang menyimpan nilai yang ingin kita hapus, keluarkan, dan hubungkan sisa linked list.
Seharusnya nilai yang ingin kita hapus adalah x dan dengan asumsi x ada dalam linked list dan unik.
Ada dua kondisi yang harus kita perhatikan: Jika x berada dalam head node atau x tidak berada dalam head node.
Menghapus 31 (terletak di kepala [Head])
4. Polynomial Representation
=> Polinomial diberikan sebagai 6x3 + 9x2 + 1 Setiap istilah individu dalam polinom terdiri dari dua bagian, koefisien dan kekuatan Di sini, 6, 9, 7, dan 1 adalah koefisien dari persyaratan yang masing-masing memiliki 3, 2, 1, dan 0 sebagai kekuatan masing-masing. Setiap istilah polinomial dapat direpresentasikan sebagai simpul dari linked list.
5. Circular Single Linked List
- Secara sirkuler, node terakhir berisi pointer ke node pertama
- Kita bisa memiliki daftar terkait melingkar dan juga daftar ganda yang saling terkait.
- Tidak ada penyimpanan nilai NULL dalam daftar
6. Doubly Linked List
=> Daftar ganda atau linked list dua arah adalah data daftar tertaut struktur dengan dua link, satu yang berisi referensi ke data berikutnya dan satu yang berisi referensi ke data sebelumnya.
Sebagai Contoh :
struct tnode {
int value;
struct tnode *next;
struct tnode *prev;
};
•
struct tnode *head = 0;
struct tnode *tail = 0;
7. Doubly Linked 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 ekor.
Sebagai Contoh :
struct tnode *node =
(struct tnode*)
malloc(sizeof(struct tnode));
node->value = x;
node->next =
NULL;
node->prev =
tail;
tail->next =
node;
tail = node;
Seharusnya kita ingin memasukkan simpul baru dalam posisi tertentu (apapun lokasi antara kepala dan ekor)
Sebagai Contoh :
struct tnode *a = ??;
struct tnode *b = ??;
// the new node will be inserted between a and b
struct tnode *node =
(struct tnode*)
malloc(sizeof(struct tnode));
node->value = x;
node->next = b;
node->prev = a;
a->next = node;
b->prev = node;
8. Doubly Linked List: Delete
=> 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 kepala.
- Simpul yang akan dihapus adalah ekor.
- Simpul yang akan dihapus bukan kepala atau ekor.
1. Jika simpul yang akan dihapus adalah satu-satunya simpul:
- bebas (kepala);
- kepala = NULL;
- ekor = NULL;
2. Jika simpul yang akan dihapus adalah kepala:
- kepala = kepala-> berikutnya;
- bebas (kepala-> prev);
- head-> prev = NULL;
3. Jika simpul yang akan dihapus adalah ekor:
- ekor = ekor-> prev;
- bebas (ekor-> berikutnya);
- tail-> next = NULL;
9. Circular Doubly Linked List
=> Ini mirip dengan linked list melingkar tunggal, tapi total pointer di setiap node di sini adalah 2 (dua) pointer.
10. Header Linked 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.
