DIG1G3 Implementasi Struktur Data Program Studi Diploma III Teknik Informatika Fakultas Ilmu Terapan Telkom University Dosen: Cahyana, S.T., M.Kom. Indra Azimi, S.T., M.T.
Tujuan Pertemuan 4 • Mahasiswa mengetahui dan dapat mengimplementasikan ADT untuk Singly Linked List
3
LIST • List: A collection of elements of the same type. • The length of a list is the number of elements in the list. • Following are some of the operations performed on a list: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
Create the list. The list is initialized to an empty state. Determine whether the list is empty. Determine whether the list is full. Find the size of the list. Destroy, or clear, the list. Determine whether an item is the same as a given list element. Insert an item in the list at the specified location. Remove an item from the list at the specified location. Replace an item at the specified location with another item. Retrieve an item from the list from the specified location. Search the list for a given item.
4
Linked List
Data
Link
Alamat node berikutnya
Informasi
• Linked list: kumpulan komponen nodes. Setiap node (kecuali node terakhir) menyimpan alamat dari node berikutnya. • Alamat dari node pertama pada list disimpan di lokasi yang berbeda head / first • Setiap node terhubung dengan penguhubung (pointer) yang mengindikasikan dimana node berikutnya berada. • Dynamic data structure
5
Linked List • Declare each node as a class or struct. • The data type : ?? • The link component of each node is a pointer. The data type of this pointer variable is the node type itself. • The variable declaration is as follows: typedef struct node { int info; nodeType *link; } nodeType;
nodeType *head; Deklarasi head Pointer
Singly Linked List • Simplest form of linked list • Linked list object holds a pointer to the first node in the list • Each node object consists of the data object being stored, and a pointer to the next node in the list
Singly Linked List • One-way list: each list node has a single pointer to the next node on the list.
Misal, alamat node pertama adalah 2000
Node terakhir, pointer menunjuk ke NULL
Maka, isi dari head adalah 2000 (head “menunjuk” node pertama
Singly Linked List
head->info = 17 head->link = 2800 head->link -> info = ?
• Penelusuran linked list : gunakan satu pointer bantuan: current ▫ nodeType *current = head; ▫ Maka, current = current -> link :
current->info =?
Singly Linked List - Traversing • Penelusuran linked list : current akan menelusuri linked list sampai akhir current = head; while (current != NULL) { //Process current cout << current->info << " "; current = current->link; }
Pointer current menelusuri linked list dan mencetak isinya
Singly Linked List - Insert • Inserting node baru pada linked list dapat dilakukan pada tiga posisi: ▫ Di depan linked list ▫ Di belakang linked list ▫ Di tengah linked list
• Untuk memudahkan, gunakan dua pointer sebagai “penanda” linked list; head dan tail ▫ Head selalu menunjuk node pertama linked list ▫ Tail selalu menunjuk node terakhir linked list
• Gunakanpointer current sebagai penelusur
Singly Linked List – Insert • Membuat node baru: nodeType* nodeBaru (int x){ nodeType *newNode = new nodeType; newNode->info = x; newNode->link= NULL; //selalu menunjuk NULL return newNode; }
• Tail adalah variabel pointer dengan tipe yang sama dengan head. nodeType *tail; info Link, buat menunjuk NULL
Singly Linked List – Insert Depan • Jika sebelumnya linked list masih kosong, maka head dan tail akan menunjuk ke NULL ▫ Head = tail = NULL;
• Jika linked list sudah berisi node, maka insert node baru di depan linked list dengan cara: ▫ “Sambungkan” link node baru dengan linked list yang ada ▫ Pindahkan posisi head ke depan linked list, posisi tail tetap newNode->link = head; Head = newNode;
Tugas • Bangunlah ADT linked list berdasarkan apa yang telah Anda peroleh dari insert depan linked list • Operasi / primitif bagi linked list: 1. 2. 3. 4. 5.
Inisialisasi linked list (linked list masih kosong) Menentukan apakah linked list masih kosong Mencetak isi linked list. Membuat node baru: insert depan + belakang Menghapus node: delete tengah
