Linked List

Linked list adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian atau dapat diartikan sebagai sekumpulan komponen yang saling berhubungan (berantai) dengan bantuan pointer.

Operasi Dasar pada Linked List

Ada beberapa aturan yang didefinisikan pada operasi didalam linked list, yaitu :

·         Jika P adalah suatu variabel pointer, maka nilainya adalah alamat atau lokasi dari variabel lain yang akan dituju.

·         Operasi yang didefinisikan pada suatu variabel pointer adalah :

1.      Test apakah sama dengan NULL

2.       Test untuk kesamaan dengan variabel pointer lain

3.      Menetapkan sama dengan NULL

4.      Menetapkan menuju ke node lain

Keuntungan dan Kerugian Linked List

Keuntungan dari linked list adalah :

-        Jenis data yang berbeda dapat di-link.

-        Operasi REMOVE atau INSERT hanya dilakukan dengan mengubah pointer-nya saja

Sedangkan kerugian dari linked list yaitu:s

-        Diperlukan ruang tambahan untuk menyatakan/tempat field pointer.

-        Diperlukan waktu yang lebih banyak untuk mencari suatu node dalam linked list.

POLYNOMIAL LIST

Penyajian  Polinomial

Penyajian polinomial dalam memori ini disimpan di dalam Header linked list. Header linked list ini merupakan suatu list yang mengandung suatu simpul khusus yang terletak pada bagian awal dari list yang disebut simpul header. Simpul  header ini selalu merupakan bagian penting  dalam penyajian, karena dibutuhkan  untuk  menyajikan  polinomial  nol. Ada 2 jenis header linked list yang sering digunakan yaitu :

1.      Grounded Header List  yaitu suatu header list yang simpul terakhirnya berisi NULL

2.      Circular Header List yaitu header list yang simpul terakhirnya menuding ke simpul header dari list tersebut.

LINK[START] = NULL è menunjukkan Grounded Header List hampa

LINK[START] = START è menunjukkan Circular Header List hampa  

Contoh: polinomial p(x) = 2x⁸ – 5x⁷ – 3x² - 4.  Polinomial ini disimpan sebagai header list. Masing-masing simpul berkorespondensi dengan suku tidak nol dari polinomial. Secara khusus, bagian informasi dari simpul dibagi menjadi dua  field  yang masing-masingnya berturut-turut menyajikan koefisien dan eksponen dari suku yang bersangkutan, dan  simpul dikaitkan berdasar  atas  derajat  menurun.

 

Variabel penuding POLY menuding ke simpul  header, yang field eksponennya diberi nilai bilangan negatif, dalam hal ini adalah -1. Di sini penyajian larik dari list membutuhkan 3 larik linier, misalnya COEF, EXP  dan  LINK.

Evaluasi polinom ialah menghitung nilai suatu polinom apabila variabel x diganti dengan sebuah nilai tertentu. Misalnya polinom bila dievaluasikan dengan nilai x=4 akan memberikan hasil 1241.

Pada perhitungan biasa maka perlu dilakukan kalkulasi untuk yaitu dilakukan kalkulasi berulang-ulang. Untuk mengurangi pengulangan perkalian dapat digunakan Horner’s rule sehingga polinom berderajat n dapat dihitung dengan n perkalian dan n penjumlahan.

Implementasi dengan Linked List

Implementasi polinom dengan struktur data aray menjadi tidak efisien jika pangkat relatif jarang (sparse), misalnya untuk polinom walaupun sebenarnya hanya ada dua koefisien yang perlu disimpan namun memerlukan tempat penyimpanan sebanyak 1001 elemen. Sebagai alternatif dapat menggunakan linked list. Node digunakan untuk menyimpan elemen yang tidak nol yaitu koefisien dan pangkatnya.

Untuk mempermudah proses pembentukan dan penjumlahan polinom maka setiap polinom diberi dua dummy node pada saat di-create. Dummy node pertama diberi nilai pangkat ekstrem kecil dan node kedua diberi nilai pangkat ekstrem besar. Dengan demikian, maka semua simpul lain akan disisipkan diantara kedua simpul ini.
Contoh :

tPolinom *createpolinom() {

tPolinom *head, *tail;

                head = (tPolinom *) malloc (sizeof (tPolinom));

                tail = (tPolinom *) malloc (sizeof (tPolinom));

                head ->pkt = -32768;

                tail->pkt = 32767;

                head->next =tail;

                tail -> next = NULL;

                return head;

}

Pada linked list elemen polinom diurutkan berdasarkan pangkat dari pangkat terendah sampai pangkat tertinggi.  Setiap penambahan elemen secara umum membentuk satu simpul baru, tetapi tidak selalu demikian. Modul insetnode() digunakan untuk  memeriksa apakah terdapat simpul dengan pangkat seperti pangkat elemen baru yang akan ditambahkan. Apabila terdapat simpul dengan pangkat demikian maka nilai koefisiennya akan dijumlahkan tanpa membentuk simpul baru. Jika hasil penambahan ini menyebabkan koefisien bernilai nol,maka simpul ini akan dihapus dari linked list. Apabila pada linked list polinom belum terdapat simpul dengan pangkat seperti pangkat elemen yan akan ditambahkan maka akan dibentuk simpul baru.

Penjumlahan dua polinom akan membentuk polinom hasil. Penjumlahan dilakukan dengan membandingkan nilai pangkat. Jika nilai pangkat pada simpul-simpul kedua polinom sama besar dan hasil jumlah koefisiennya sama dengan nol maka abaikan kedua simpul tersebut. Akan tetapi apabila jumlah koefisiennya bukan nol maka data akan ditambahkan ke polinom hasil.

Pada pangkat polinom, jika nilai pangkat pada simpul polinom pertama lebih kecil daripada nilai pangkat pada simpul polinom kedua, maka simpul polinom pertama ini yang disalin ke polinom hasil dan pointer pindah ke simpul berikutnya pada polinom pertama. Akan tetapi jika pangkat pada simpul polinom pertama lebih besar daripada nilai pangkat pada simpul polinom kedua, maka simpul polinom kedua ini yang disalin ke polinom hasil dan pointer pindah ke simpul berikutnya pada polinom kedua.

Sedangkan pada perkalian polinom dilakukan dengan mengalihkan setiap koefisien polinom pertama dengan setiap koefisien polinom kedua. Hasil perkalian dengan pangkat yang sama akan disimpan pada simpul yang sama.

Contoh :

//perkalian polinom

tPolinom * mulpolinom(tpolinom *pnoml, tPolinom *pnom2){

tPolinom *pnom3, *curr1, *curr2;

pnom3 = createpolinom();

curr1 = pnom1->next;

while (curr1->next !=NULL) {

curr2 = pnom2->next;
While (curr2->next !=NULL) {

Insertnode (pnom3, curr1->pkt + curr2->pkt, curr1 -> koef * curr2 -> koef);

curr1 -> koef * curr2->koef);

curr2 = curr2->next;

}

curr1 = curr1->next;

}

Return pnom3;

}