2 - linked list implementation 1- 2101656755 - Wantika Aprilia Wangke

Hari ini pada pertemuan kedua kami belajar tentang

LO1: konsep struktur data dan penggunaannya dalam aplikasi.
LO2: Terapan struktur data dalam aplikasi.

Sub topik
Single Linked List
-Polynomial Representation
-Circular Single Linked List
-Doubly Linked List
-Circular Doubly Linked List
-Header Linked List

Berikut adalah pembahasan sub topik yang ada:
1. Single linked list
Linked List merupakan koleksi linear dari data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer. Linked List dapat didefinisikan pula sebagai kumpulan nodes yang merepresentasikan sebuah sequence.

Representasi sebuah linked list dapat digambarkan melalui gambar di bawah ini:

Sebuah linked list yang hanya memiliki 1 penghubung ke node lain disebut sebagai single linked list.

Berikut adalah algoritma untuk memasukkan, menghapus dan mencari node dalam satu linked list.

Insert: Untuk memasukkan node baru di awal daftar, buat pointer berikutnya dari node baru menunjuk ke kepala daftar dan buat node baru sebagai head. Untuk memasukkan pada akhirnya, cukup melintasi seluruh daftar dan pindah ke node terakhir, lalu buat pointer berikutnya dari titik satu terakhir ke yang baru. Misalkan, Anda ingin memasukkan node baru p antara dua node x dan y (daftar saat ini adalah x -> y). Kemudian, buatlah berikutnya dari titik ke y dan selanjutnya x menunjuk ke hlm. Daftar yang dihasilkan adalah x -> p -> y.

Hapus: Misalkan daftar saat ini adalah x -> y -> z. Untuk menghapus x, buat saja head point ke y dan hapus x. Untuk menghapus z, buat saja y berikutnya ke NULL dan hapus z. Untuk menghapus y, buat titik x berikutnya ke z dan hapus y (daftar hasilnya adalah x -> z).

Pencarian: Untuk mencari sebuah node, daftarnya harus dilalui mulai dari daftar utama.

2. Polynomial Representation
Masalah aritmatika polinom adalah membuat sekumpulan subrutin manipulasi terhadap polinom simbolis

(symbolic Polynomial).  Misalnya:

P1 = 6x8 + 8x7 + 5x5 + x3 + 15

P2 = 3x9 + 4x7 + 3x4 + 2x3 + 2x2 + 10

P3 = x2 + 5

Terdapat empat operasi aritmatika polinom dasar antara lain:

Penambahan (P1 + P2 = 3x9 + 6x8 + 12x7 + 5x5 + 3x4 + 3x3 + 2x2 + 25)

- Pengurangan (P1 - P2 = - 3x9 + 6x8 + 4x7 + 5x5 - 3x4 - x3 - 2x2 + 5)

- Perkalian (P1 * P3 = 6x10 + 8x9 + 5x7 + x5 + 15x2 + 30x8 + 40x7 + 25x5 + 5x3 + 75 = 6x10+ 8x9 + 30x8+45x7 + 26x5 + 5x3 + 15x2 + 75)

- Turunan (P2'= 27x8 + 28x6 + 12x3 + 6x2 + 4x)

Representasi bilangan polinom dengan array :

int P1[10] = {0,6,8,0,5,0,1,0,0,15};

[] index menunjukkan jumlah pangkat dan nilai array menunjukkan konstanta pada setiap pangkat polinom. Hal ini berlaku sama untuk P2 dan P3.

int P2[10] = {10,0,2,2,3,0,0,4,0,3};

[] index menunjukkan jumlah pangkat dan nilai array menunjukkan konstanta pada setiap pangkat polinom. Hal ini berlaku sama untuk P2 dan P3.

int P3[10] = {5,0,1,0,0,0,0,0,0,0};

[] index menunjukkan jumlah pangkat dan nilai array menunjukkan konstanta pada setiap pangkat polinom. Hal ini berlaku sama untuk P2 dan P3.

3. Circular Single Linked List

Single Linked List Circular adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node,
maka pointer next pada node terakhir akan menunjuk ke node terdepannya.

Pengertian:
Single : artinya field pointer-nya hanya satu buah saja dan satu arah.
Circular : artinya pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar

Ilustrasi Single Linked List Circular
- Setiap node pada linked list mempunyai field yang berisi pointer ke node
Berikutnya, dan juga memiliki field yang berisi data.
- Pada akhir linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar. Node terakhir akan menunjuk lagi ke head

PEMBUATAN SINGLE LINKED LIST CIRCULAR
Deklarasi node
Dibuat dari struct berikut ini:
typedef struct TNode
int data;
TNode *next;
};

Penjelasan:
- Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data bertipe integer dan field next yang bertipe pointer dari TNode
- Setelah pembuatan struct, buat variabel haed yang bertipe pointer dari TNode yang berguna sebagai kepala linked list.

Pembentukan node baru
Digunakan keyword new yang berarti mempersiapkan sebuah node baru
berserta alokasi memorinya.

TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = baru;

4. Doubly Linked List
Double Link List adalah elemen-elemen yang dihubungkan dengan dua pointer dalam satu elemen dan list dapat melintas baik di depan atau belakang.

Elemen double link list terdiri dari tiga bagian:
- Bagian data informasi
- Pointer next yang menunjuk ke elemen berikutnya
- Pointer prev yang menunjuk ke elemen sebelumnya

Untuk menunjuk head dari double link list, pointer prev dari elemen pertama menunjuk NULL. Sedangkan untuk menunjuk tail, pointer next dari elemen terakhir menunjuk NULL.
Contoh Membuat TDA(Tipe Data Abstrak) dari Double Linked Circular List tersebut.
Instan :
Double Linked Circular List
Operasi :
Buat_node(char x) : membuat node baru dengan informasi x
Tambah_elemen_didepan() : menambah elemen paling depan (pointernya menunjuk elemen pertama link list)
Tambah_elemen_dibelakang() : menambah elemen paling belakang (pointer elemen yang baru menunjuk elemen pertama)
Hapus_elemen_() : Menghapus elemen (pointer menunjuk elemen yang akan dihapus)
Cetak () : menelusuri elemen satu demi dan menampilkan informasinya.

5. Double Linked List Circular

Pengertian secara umumnya DLLCitu Linked list yang menggunakan pointer, dimana setiap node memiliki 3 field, yaitu:
1 field pointer yang menunjuk pointer berikutnya “next“,
1 field menunjuk pointer sebelumnya ” prev “,
1 field yang berisi data untuk node tersebut .

Double Linked List Circular pointer next dan prev nya menunjuk kedirinya sendiri secara circular. Bentuk Node DLLC

Ilustrasi Double Linked List Circular

6. Header Linked List
Header linked list merupakan header spesial yang terdiri dari node headernya. Jadi, linked list jenis ini tidak menunjuk pada node pertama (head) namun hanya menyimpan alamat dari node headernya.