linked list

Download Linked list

Post on 02-Jul-2015

222 views

Category:

Data & Analytics

1 download

Embed Size (px)

DESCRIPTION

membahas tentang senarai berantai beserta operasinya

TRANSCRIPT

  • 1. Senaraiberantailinked listPertemuan keempatStruktur datast3telkom.ac.idby : tenia wahyuningrum

2. Senarai berantaiDalam pemakaian sehari-hari istilahsenarai berantai (list) adalahkumpulan liniersejumlah data. 3. DaftarbelanjaAda yangdihapusjika barangtelah dibeliatauditambahkan barangbaru yang akandibeli. 4. Keunggulan :kemudahan dan efektifitas kerjayang lebih baik dalam halmenambah, mengurangi, sertamencari suatu elemen/node yangterdapat dalam senarai. 5. Elemen-elemen yang terdapat padasebuah senarai berantai tersimpandalam blok memori terpisah 6. Penambahan,pengurangan, ataupunpenggantian nodedapat dilakukandenganmengubahelemen rujukan atastiap-tiap node yangterkait 7. Kerugiannya, sebuah senaraiberantai tidak memungkinkanpengaksesan elemen secaraacak 8. Jenis-jenissenarai berantai 9. Senarai TunggalBila struktur data sebuah node hanya memiliki satu tautanatas node berikutnya dalam sebuah senarai, maka senaraitersebut dinamakan sebagai senarai tunggal. 10. Senarai GandaBerbeda halnya dengan senarai tunggal, padasenarai ganda, struktur data atas tiap-tiap nodememiliki rujukan pada node sebelum danberikutnya. Sebagian algoritma membutuhkantaut ganda, contohnya sorting dan reversetraversing. 11. Pada dua jenis senarai sebelumnya, node terakhirdalam senarai tersebut merujuk pada null yang artinyaakhir dari sebuah senarai, begitu pula null sebagairujukan node sebelumnya pada node pertama bilasenarai yang dimaksudkan adalah senarai ganda. Padasenarai sirkular, informasi rujukan pada node terakhirakan merujuk pada node pertama, dan rujukan padanode pertama akan merujuk pada node terakhir bilayang digunakan sebagai dasar implementasi adalahsenarai ganda. 12. info9nextnodeMenunjuk kenode lain 13. Contoh senarai berantai dengan 6 simpul :AwalA B C D E FMedan penyambung dari simpul keduaMedan informasi dari simpul kedua 14. 2INFO SAMBUNGANC 5A 6D 10B 1F 0E 812345678910AwalHabis 15. Representasi Simpul (Node)typedef struct node *list;struct node {int datalist;struct node *next;};Membuat tipe data baru (tipe databentukan) 16. dilanjutkan dengan deklarasi dari pointer kestruktur di atas sebagai berikut:struct node *head;ataulist head 17. Mengalokasikan nodeint allocate_node(int data, list *new){new = (list) malloc (sizeof(node));if(new==NULL)return 0;new->datalist = data;new->next=NULL;return 1;}/* Perintah malloc merupakah perintah memory allocation. Perintah ini berfungsi mengalokasikan suatu alamat padamemory pada sebuah variabel*/ 18. Untuk inisialisasi list setelah alokasi untuknode pertama maka ditambahkan statementsebagai berikut:head = new 19. Ilustrasi fungsi allocate_node 20. Untuk inisialisasi list setelah alokasi untuk nodepertama ilustrasinya adalah sebagai berikut 21. operasisenarai berantai 22. insertFungsi insert pada linked list meliputi :- insert sebagai node awal (head) dari linked list- insert setelah node tertentu- insert sebelum node tertentu- insert sebagai node akhir (tail) dari linked list 23. Insert sebagai node awal (head) darilinked listvoid insertashead(list insert){insert->next=head;head = insert;} 24. ilustrasi dari fungsi diatas adalahsebagai berikut: 25. Insert setelah node tertentuvoid insertafternode(int x, listinsert){list after;after = head;doafter = after->next;while (after->datalist != x);insert->next = after->next;after->next = insert;} 26. Langkah-langkah untuk proses di atas adalahsebagai berikut:1. Pointer next dari elemen baru menunjukelemen setelah elemen tertentu2. Pointer next elemen sebelumnya menunjukke elemen baru 27. Insert sebelum node tertentuvoid insertbeforenode(int x, list insert){list before, prevbefore;if (head->datalist = x)insertashead(insert)else{before = head;doprevbefore = before;before = before->next;while (before->datalist != x);insert->next = before;prevbefore->next = insert;} } 28. Langkah-langkah untuk proses di atas adalahsebagai berikut:1. Telusuri list sampai elemen tertentu, catatjuga elemen sebelumnya2. Lakukan penyisipan sebelum elemen tertentutersebut 29. Insert di akhir (tail) dari linked listvoid insertastail(list insert){list tail;tail = head;dotail = tail->next;while (tail->next != NULL);tail->next = insert;tail = tail->next;} 30. Langkah-langkah untuk proses di atas adalahsebagai berikut:1. Telusuri list sampai elemen terakhir (tail->next=NULL)2. Lakukan pentisipan setelah elemen terakhir 31. DeleteFungsi delete pada linked list meliputi :- delete sebagai simpul pertama(head) darilinked list- delete setelah simpul tertentu- delete simpul terakhir 32. delete sebagai simpul pertama(head) dari linked list 33. Langkah-langkah untuk proses di atas adalahsebagai berikut:1. Pointer first diarahkan pada data ke-22. Pointer p diarahkan pada data ke-13. Bebaskan pointer p (secara otomatis data ke-1 terhapus) 34. delete setelah simpul tertentu 35. Langkah-langkah untuk proses di atas adalahsebagai berikut:1. Arahkan pointer first s/d data yang ditunjuk2. Pointer p diarahkan pada first->next3. Arahkan pointer first->next pada p->next4. Bebaskan pointer p (secara otomatis datasetelah simpul tertentu terhapus) 36. delete simpul terakhir 37. Langkah-langkah untuk proses di atas adalahsebagai berikut:1. Telusuri simpul s/d first->next = NULL2. Arahkan pointer p ke first3. Bebaskan pointer p->next (Simpul Terakhir)4. Arahkan p->next ke NULL 38. Latihansoal 39. TuliskanOutputnya! 40. TuliskanOutputnya! 41. selesaioktober-2014