LINKED LIST, SORTING, & SEARCHING

1. LINKED LIST

Linked list merupakan salah satu struktur data fundamental dalam membangun program. Sesuai namanya, linked list terdiri dari deretan node (yang berisikan data) dan link ke_node_lainnya.

Merupakan suatu struktur data pengembangan dari konsep ADT (Abstrak Data Type) yang bersifat dinamis. Linked List dapat dimanfaatkan secara effektif sesuai dengan keperluan. Linked List juga dapat benar – benar dihapus / dibersihkan dari memory.Linked List sebenarnya merupakan suatu typedata tersendiri. Ciri – ciri utama dari Linked List adalah, dia mempunyai minimal dua elemen utama. Elemen – elemen itu adalah data dan pointer untuk menunjukkan ke list berikutnya.

Kita akan lebih efektif jika kita menggunakan konsep Linked List jika kita memerlukan suatu pengaksesan pada struktur data yang lebih dinamis. Konsep yang lebih cocok menggunakan linked list adalah : Stack, Queue, Tree, dan Graph.

Hal ini dikarenakan oleh sifat dinamis dari Linked List. Kita tidak perlu untuk mengetahui berapa block memory yang akan kita akses. Jadi, jika kita butuh block baru pada memory, tinggal menyisipkan pada kanan atau kiri list yang telah ada.

Untuk deretan node yang memiliki satu link ke node lain, kita menyebutnya sebagai singly-linked list, atau single linked list. Singly-linked list bisa diilustrasikan dengan barisan di mana setiap anggota barisan (node) berbaris menghadap ke satu arah dan anggota barisan memegang bahu anggota di depannya (link). Anggota paling depan cukup memegang udara kosong (null).

Untuk deretan node yang memiliki dua link ke node-node lain, kita menyebutnya sebagai doubly-linked list atau double linked list. Doubly-linked list bisa diilustrasikan dengan deretan orang di mana tangan kiri setiap anggota memegang tangan kanan anggota di sebelah kiri, dan tangan kanannya memegang tangan kiri anggota di sebelah kanan. Tangan kiri anggota paling kiri memegang udara kosong. Demikian juga dengan anggota paling kanan yang memiliki nasib sama: tangan kanannya memegang udara kosong. Linked list bisa disusun linear atau circular. Ketika disusun circular, pada singly-linked list, anggota barisan yang tadi kita bahas tidak lagi memegang udara kosong, namun memegang bahu anggota paling belakang. Jadi, tidak pegel. Untuk circular doubly-linked list (atau doubly circularly linked list), nasib anggota paling kiri dan paling kanan juga berubah. Tangan kanan anggota paling kanan memegang tangan kiri anggota paling kiri. Struktur data fundamental ini sangat berguna. Jadi, mahasiswa ilmu komputer yang mempelajari struktur data ini harus sungguh-sungguh mempelajarinya, walaupun harus berpusing-pusing. Linked list sendiri sudah berumur cukup tua dan dikembangkan_sejak_tahun_1955-56.

Struktur Linked List dalam Bahasa C

Struktur Data – Macam – macam Linked List, berikut merupakan macam – macam linked list :

ü  Singly Linked List :

Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya dan juga memiliki field yang berisi data.

Akhir linked list ditandai dengan node terakhir akan menunjuk ke null yang akan digunakan sebagai kondisi berhenti saat pembacaan linked list.

ü  Double Linked List :

Linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu: 1 field pointer yang menunjuk ke pointer berikutnya, 1 field pointer yang menunjuk ke pointer sebelumnya dan field yang berisi data dari node tersebut. Pointer next dan prev-nya menunjuk ke null.

ü  Single Circular Linked List :

Single Linked List yang pointer next-nya menunjuk ke dirinya sendiri, jika terdiri dari beberapa node maka pointer terakhirnya akan menunjuk ke pointer terdepannya.

ü  Double Circular Linked List :

Double Linked List yang pointer next dan prev-nya menunjuk ke dirinya sendiri secara circular.

Jika dilihat pengaksesannya, Linear dan Circular Linked List dapat dibedakan sebagai berikut :

Linear Linked List	Circular Linked List
Tail.next dihubungkan ke null	Tail.next dihubungkan ke head
Pada perulangan, akan break pada now = null	Pada perulangan, akan break pada now = null
Method lebih sederhana	Method lebih sulit debandingkan dengan Linear linked list
Algoritma akan lebih sulit jika kita melakukan penyelesaian masalah dengan menggunakan konsep circular queue	Akan lebih mudah pada konsep – konsep tertentu salah satunya seperti konsep queue.

Apa itu Simpul dan Ekor

Daftar linier (Linear List)  adalah suatu struktur data umum yang terbentuk dari barisan hingga (yang terurut) dari satuan data, atau pun dari record.

Elemen dari daftar linier disebut simpul atau node. Daftar ini disebut linier karena susunan elemennya adalah linier, yaitu bahwa bagi setiap elemen selalu ada elemen setelah dan sebelumnya, kecuali pada elemen pertama dan terakhir.

Banyaknya simpul dalam suatu daftar linier dapat berubah-ubah, berbeda dengan array yang jumlah elemennya selalu tetap. Penyisipan simpul berarti menambah suatu simpul/elemen baru ke dalam sebuah list.                                                      

Dengan Head dan tail

ü  Menggunakan 2 pointer, head dan tail.

ü  Head selalu menunjuk node pertama dan tail selalu menunjuk node terakhir

Kelebihandari Single Linked List dengan Head & Tail adalah padapenambahan data di belakang, hanyadibutuhkan tail yang mengikat node baru saja tanpa harus menggunakan perulangan pointer bantu.

2. Sorting

Sorting atau pengurutan adalah proses menyusun elemen – elemen dari masukan awal acak menjadi keluaran akhir tertata dengan urutan tertentu. Proses tersebut diimplementasikan dalam bermacam aplikasi. Contoh penerapannya antara lain berupa rincian transaksi sesuai urutan tanggal dan jam pada perbankan, daftar hadir yang diurutkan berdasarkan nomor induk dan daftar pustaka yang diurutkan sesuai abjad pengarang ataupun katalog buku di perpustakaan. Fungsi-fungsi statistik seperti median dan pembuatan kuartil data (quarter), desil dan percentil (percentile) mensyaratkan data untuk diurutkan terlebih dahulu. Beberapa macam algoritma sorting telah dibuat karena proses tersebut sangat mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma – algoritma yang ada sangatlah berguna. Selain menjadi suatu 2 aplikasi yang berdiri sendiri, pengurutan juga biasanya menjadi suatu bagian dari algoritma  yang lebih besar.

- Insertion Sort

Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Insertion Sort disebut-sebut sebagai metode pertengahan. Artinya, metode ini memiliki kecepatan ratarata antara metode primitif (bubble dan selection) dan modern (merge dan quick) . Metode ini, didasarkan pada sebuah kunci yang diambil pada elemen ke-2 pada sebuah larik, lalu menyisipkan elemen tersebut jika kondisi percabangan terpenuhi. Metode penyisipan (insertion) bertujuan untuk menjadikan bagian sisi kiri larik terurutkan sampai dengan seluruh larik berhasil diurutkan. 

- Selection Sort 

 Merupakan kombinasi antara sorting dan searching. Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array. Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]). Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses. 

3. SREACHING

Searching berarti pencarian suatu situs yang belum kita ketahui secara pasti alamat yang dimiliki. Dalam melakukan searching biasanya kita gunakan search engine sebagai mesin pembantu dalam pencarian situs tersebut.Search engine adalah sebuah fasilitas (web) yang bisa mencari links dari situs lain. Ada berbagai macam search engine yang bisa kita gunakan dalam searcing, yaitu ; yahoo, google, altavista, lycos, astaga, msn, dan lain sebagainya.

Pencarian(searhing) merupakan proses yang sangat penting dalam pengolahan data. Proses pencarian adalah menemukan nilai(data) tertentu didalam sekumpulan data yang bertipe sama. Sebuah algoritma pencarian dijelaskan secara luas adalah sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Algoritma pencarian (searching algorithm) adalah algoritma yang menerima sebuah Kata kunci dan dengan  langkah-langkah tertentu akan mencari rekaman dengan kata kunci tersebut.  Setelah proses pencarian dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan atau tidak ditemukan. Macam-macam Algoritma (Searching):

·         - Pencarian sekuensial (Sequential searching)

Pencarian Sekuensial (sequential searching) atau pencarian berurutan sering disebut pencarian linear merupakan metode pencarian yang paling sederhana. Pencarian beruntun adalah proses yang membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa.

·         - Pencarian Biner (binary search)

Terdapat metode pencarian pada data terurut yang paling efficient, yaitu metode pencarian bagi dua atau pencarian biner (binary search). Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Prinsip pencarian dengan membagi data atas dua bagian mendasari metode ini. Data yang disimpan di dalam larik harus sudah terurut.data terurut yang paling efficient, yaitu metode pencarian bagidua atau pencarian biner(binary search).