Pertemuan 2-Linked List 1-2101706066-Muhammad Fauqhi

LINKED LIST 1

Pengantar Kita sudah pelajari bahwa sebuah array adalah kumpulan dari suatu data yang sama elemennya dimana unsur-unsurnya disimpan pada lokasi memori yang berurutan. Saat mendeklarasikan array kita harus membatasi jumlah elemen yang disimpan array tersebut. Tetapi, bagaimana jika kita tidak yakin dengan jumlah elemen sebelumnya? Memudahkan penggunaan memori, elemen harus disimpan secara acak di lokasi manapun dan bukan di lokasi berturut-turut. Jadi, harus ada struktur data yang menghilangkan batasan pada jumlah elemen maksimum dan kondisi penyimpanan agar program lebih efisien.


Pengenalan pada Link List Link list adalah struktur data yang menghilangkan batasan tersebut. Daftar yang terhubung tidak menyimpan elemen-elemennya di lokasi yang berturut-turut dan pengguna dapat menambahkan sejumlah elemen kedalamnya. Namun tidak seperti array, linked list tidak memungkinkan untuk mengakses data secara acak. Elemen dalam linked list hanya dapat diakses secara berurutan. Tapi sebuah array, penyisipan dan penghapusan dapat dilakukan pada setiap titik dalam daftar waktu yang konstan.


Istilah Dasar Link List Sebuah linked list, secara sederhana, adalah koleksi elemen data yang linier. Elemen data ini disebut node. Linked list adalah struktur data yang pada gilirannya dapat digunakan untuk mengimplementasikan struktur data lainnya. Sebuah linked list dapat dianggap sebagai kereta atau urutan node dimana masing-masing node berisi satu atau lebih field data dan pointer ke node berikutnya.

Gambar 2.1

Pada Gambar 2.1, kita bisa lihat bahwa setipa node linked list itu terdiri dari dua bagian, yang pertama adalah tipe data integer dan yang kedua ada pointer untuk ke node berikutnya. Bagian kiri dari node bisa berisi apa saja, contohnya array, atau struct. Dan yang bagian kanan adalah untuk pointer ke node berikutnya. Node terakhir tidak memiliki pointer atau tidak ada lagi node berikutnya. Node terakhir biasa disebut juga NULL.

Pada bahasa C, kita dapat implementasikan linked list sebagai berikut:

               struct node 
               { 
                   int data;
                   struct node *next;  
               };


Melintas Linked List Mengkases node dari link list melakukan beberapa pemrosesan pada link lists. Sebuah linked list selalu berisi variabel pointer START yang menyimpan alamat node pertama dari linked list. Akhir dari linked list ditandai dengan menyimpan NULL atau -1 pada node terakhir. Untuk melintasi linked list, kita memerlukan variabel pointer lain disebut PTR dimana yang menunjukkan ke node yang saat ini sedang diakses. Contoh Algoritma melintas linked list: 

Step 1: [INITIALIZE] SET PTR = START 
Step 2: Repeat Steps 3 and 4 while PTR != NULL 
Step 3:                   Apply Process to PTR -> DATA 
Step 4:                   SET PTR = PTR -> NEXT 
             [END OF LOOP] 
Step 5: EXIT


Mencari Nilai pada Linked List Mencari nilai pada linked list berarti mencari unsur elemen didalam linked list tersebut. Jadi pencarian pada linked list apakah ada  nilai tertentu di bagian informasi dari node atau tidak. Jika ada, algoritma mengembalikan alamat dari node yang berisi nilai tersebut. Contoh Algoritmanya:

Step 1: [INITIALIZE] SET PTR = START 
Step 2: Repeat Step 3 while PTR != NULL 
Step 3:       IF VAL = PTR -> DATA 
                           SET POS = PTR 
                           Go To Step 5 
                  ELSE 
                           SET PTR = PTR -> NEXT 
                  [END OF IF] 
            [END OF LOOP] 
Step 4: SET POS = NULL 
Step 5: EXIT


Memasukkan Nilai pada Linked List Dalam memasukkan nilai pada Linked List ada beberapa kasus. Yaitu : Memasukkan node baru dari awal, Memasukkan node baru dari belakang. Sebenarnya ada kasus lainnya tetapi kali ini hanya dua kasus yang dibahas. Langsung saja ke algoritmanya.

Step 1: IF AVAIL = NULL 
                   Write OVERFLOW 
                   Go to Step 7 
            [END OF IF] 
Step 2: SET NEW_NODE = AVAIL 
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL 
Step 5: SET NEW_NODE -> NEXT = START 
Step 6: SET START = NEW_NODE 
Step 7: EXIT

Algoritma ini untuk memasukkan node baru dari awal.

Step 1: IF AVAIL = NULL 
                   Write OVERFLOW 
                   Go to Step 10 
            [END OF IF] 
Step 2: SET NEW_NODE = AVAIL 
Step 3: SET AVAIL = AVAIL -> NEXT 
Step 4: SET NEW_NODE -> DATA = VAL 
Step 5: SET NEW_NODE -> DATA = NULL 
Step 6: SET PTR = START 
Step 7: Repeat Step 8 while PTR -> NEXT != NULL 
Step 8:         SET PTR = PTR -> NEXT 
         [END OF LOOP] 
Step 9: SET PTR NEXT = NEW_NODE
Step 10: EXIT

Algoritma ini untuk memasukkan nodebaru dari akhir.


Menghapus Nilai dari Linked List Ketika kita ingin menghapus sebuah nilai atau node dari awal linked list, maka perubahan berikut akan dilakukan di linked list. Algoritma untuk menghapus nilai dari node pertama:

Step 1: IF START = NULL 
                   Write UNDERFLOW 
                   Go to Step 5 
            [END OF IF] 
Step 2: SET PTR = START 
Step 3: SET START = START -> NEXT 
Step 4: FREE PTR 
Step 5: EXIT

Perbedaan Konsep Single Linked List, Circular, Dan Double Linked List Double Linked list memiliki 2 penunjuk arah yang biasa di inisialisasikan next dan prev. Untuk Circular Linked list, node yang terakhir berisi pointer ke node yang pertama atau Head. Jadi Circular tidak memiliki nilai NULL.

Pertemuan 1-Pointer, Array, and Introduction to Data Structure-2101706066-Muhammad Fauqhi

Pointer, Array, and Introduction to Data Structure

Sub Topics

• Array Review
• Pointer Review
• Types of Data Structure
• Abstract Data Type

Array

• Array adalah kumpulan dari suatu data yang sama elementnya
• Array memiliki tipe data yang mired atau homogenous
• Element dari array ini disimpan pada memori dan diakses dengan memanggil index element tersebut
• Index array dimulai dari 0

Menyimpan nilai index dan memanggil pada Array

• Inisialisasi

Deklarasi : 

int array[5] = {0,1,2,3,4,5,6};

Memanggil array :

array[2] = 3;

array[0] = 1;

• Menginput Nilai

int array[10];

for(int i=0;i<=10;i++){

    scanf("%d",&array[i]);

}

• Menetapkan sebuah Nilai

int array1[10];array2[10];

for(int i=0;i<=10;i++){

   array2[i] = array1[i];

}

Array juga bisa memiliki 2 atau lebih dimensi. 

Contohnya : 

int array[10][10];

Maksud dari deklarasi diatas adalah setiap index dari 1-10 diisi oleh 10 data setiap indexnya.

Pointer

adalah tipe data dimana nilai tersebut terpacu kepada nilai yang lain didalam komputer dengan mengakses alamatnya.

• & adalah untuk alamat pointer
• * nilai dari pointernya

Contoh : 

int x=10;

int *a = &x;

printf("%d\n",*p);

Output dari program ini adalah alamat dari x.

Untuk double pointer itu bisa. Maksudnya adalah pointer didalam pointer.

Data Structure

• Array
• Linked Lists

Struktur data yang dinamis, dimana element tersebut bisa ditambahkan atau dihapus darimanapun.

• Queues

First in First out.

Contoh : Antrian makanan, antrian ATM, dsb.

• Stacks

Last in First out.

Contoh : Tumpukan piring. Diambil dari paling atas

• Binary Trees
• Hash Tables

Abstract Data Type
dapat didefinisikan sebagai model matematika dari objek data yang menyempurnakan tipe data dengan cara mengaitkannya dengan fungsi-fungsi yang beroprasi pada data yang bersangkutan.