PENGERTIAN
Linked List adalah salah satu bentuk struktur data, berisi kumpulan data (node) yang tersusun secara sambung menyambung, dinamis dan terbatas. Linked List sering disebut juga Senarai Berantai Linked List saling terhubung dengan bantuan variabel pointer. Dengan menggunakan linked list maka programmer dapat menimpan datanya kapanpun dibutuhkan. Linked list mirip dangan array, kecuali pada linked list data yang ingin disimpan dapat dialokasikan secara dinamis pada saat pengoperasian program (run-time).
Operasi-Operasi yang ada pada Linked List
- Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
- IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
- Find First
Fungsi ini mencari elemen pertama dari linked list
- Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now
- Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
- Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu
- Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.
- Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
- Clear
Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.
Jenis-Jenis Linked List yaitu :
1. Singly linked list
2. Double linked list
3. Circular Linked List
Operasi-operasi untuk Singly Linked List :
- IsEmpty
Fungsi memeriksa apakah singly yang ada masih kosong.
- Push
Fungsi memasukkan elemen baru ke dalam singly. Push di sini mirip dengan insert dalam single linked list biasa.
- Pop
Fungsi ini mengeluarkan elemen teratas dari singly.
- Clear
Fungsi ini akan menghapus singly yang ada.
Operasi-operasi Queue dengan Double Linked List :
- IsEmpty
Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong.
- IsFull
Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bisa menampung data dengan cara mengecek apakah Jumlah Queue sudah sama dengan MAX_QUEUE atau belum. Jika benar maka queue sudah penuh.
- EnQueue
Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head dan tail mula-mula meunjukkan ke NULL).
- DeQueue
Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).
# Circular Linked List
Circular Linked List (CLL) adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya.
Pengertian:
Node : rangkaian beberapa simpul
Single : artinya field pointer-nya hanya satu buah saja dan satu arah.
Linked List : artinya node-node tersebut saling terhubung satu sama lain.
Circular : artinya pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar.
Sumber :
[1] http://goblog.herisonsurbakti.com/2009/05/09/linked-list/
[2] http://id.wikipedia.org/wiki/Linked_list
Minggu, 03 April 2011
Teknik Sorting dan Searching
SORTING
Dewasa ini kita tidak perlu lagi untuk mengurutkan kumpulan data - data dengan cara manual, karena era ini sudah banyak sekali metode atau program untuk melakukan kebutuhan sorting.
Ada 5 metode dalam teknik sorting, diantaranya adalah :
1. Comparison-Based Sorting (pengurutan berdasarkan perbandingan)
# Bubble sort, exchange sort
2. Priority Queue Sorting Method (pengurutan berdasarkan prioritas)
# Selection sort, heap sort
3. Insert and Keep Sorted Method (pengurutan berdasarkan penyisipan dan penjagaan terurut)
# Insertion sort, tree sort
4. Devide and Conquer Method(pengurutan berdasarkan pembagian dan penguasaan)
# Quick sort, merge sort
5. Diminishing Increment Sort Method (pengurutan berkurang menurun)
# Shell sort
- Bubble Sort
Teknik ini dilakukan degan pola membawa nilai terbesar menjadi nilai index terakhir array. jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 samapai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. proses ini dilakuan hingga jumlah data.
- Exchange Sort
Teknik sorting ini dibuat dengan cara pola membawa nilai terbesar menjadi nilai index terakhir array. Jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 samapai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. proses ini dilakuan hingga jumlah data dikurangi 1 atau sampai program tidak melakukan pertukaran. jadi waktu untuk melakukan proses sorting lebih cepat.
- Selection Sort
Teknik sorting ini dibuat dengan cara melakukan pengecek'an 1 persatu, bila kita akan mengurutkan secara ascending maka kita lakukan pengecek'an nilai tempat yang pertama (index pertama pada array)kita bandingkan dengan semua nilai yang ada kita cari nilai minimalnya. lalu simpan index/ letak nilai minimum itu di temukan, setelah pengecekan selesai tukar index awal pengecekan dengan nilai minimum yang telah di simpan tadi. Proses ini dilakukan terus menerus sampai pada pengecekan index terakhir min 1 dengan index terakhir. beda dengan streith selection sort adalah dengan teknik ini melakukan pertukaran nilai lebih sedikit, hanya jumlah data - 1 pertukaran. jadi waktu untuk melakukan proses sorting lebih cepat.
- Heap Sort
Teknik sorting ini dibuat dengan versi yang jauh lebih efisien selection sort. Ia juga bekerja dengan menentukan elemen (atau terkecil) terbesar daftar, menempatkan bahwa pada akhir (atau awal) dari daftar, kemudian melanjutkan dengan sisa daftar, tapi menyelesaikan tugas ini secara efisien dengan menggunakan struktur data yang disebut tumpukan, tipe khusus pohon biner. Setelah daftar data telah dibuat menjadi tumpukan, simpul akar dijamin menjadi unsur (atau terkecil) terbesar. Ketika dipindahkan dan ditempatkan di akhir daftar, tumpukan adalah ulang sehingga elemen terbesar yang tersisa bergerak ke akar. Menggunakan heap, menemukan elemen terbesar berikutnya membutuhkan O (log n) waktu, bukan O (n) untuk linear scan di selection sort sederhana. Hal ini memungkinkan heapsort untuk menjalankan dalam O (n log n) waktu, dan ini juga merupakan kompleksitas kasus terburuk.
- Insertion Sort
Teknik sorting ini dibuat dengan cara menyisipkan atau memasukkan 1 persatu, bila kita akan mengurutkan data, kemudian ingin menyisipkan suatu data maka data tersebut akan otomatis masuk dimana dia berada.
- Quick Sort
Teknik sorting ini dibuat dengan cara yang menggunakan partisi. Pada teknik ini, data dibagi menjadi dua bagian, yaitu data disebelah kiri partisi selalu lebih kecil dari data disebelah kanan. Namun data pada kedua partisi belum terurut, sehingga untuk mengurutkannya, proses pengurutan dilakukan pada kedua partisi secara terpisah. Selanjutnya, data di sebelah kiri dan kanan dipartisi lagi.
- Merge Sort
Teknik sorting ini dibuat dengan cara mengambil keuntungan dari kemudahan penggabungan daftar sudah disortir ke daftar diurutkan baru. Dimulai dengan membandingkan setiap dua elemen (yaitu, 1 dengan 2, kemudian 3 dengan 4 ...) dan swapping mereka jika yang pertama datang setelah kedua. Kemudian masing-masing menggabungkan daftar yang dihasilkan dari dua ke daftar empat, kemudian menggabungkan daftar tersebut empat, dan seterusnya, sampai akhirnya dua daftar digabungkan ke dalam daftar diurutkan akhir.
- Shell Sort
Teknik sorting ini dibuat dengan cara meningkatkan atas bubble sort dan insertion sort dengan menggerakkan keluar dari elemen-elemen memesan lebih dari satu posisi pada suatu waktu. Salah satu implementasi dapat digambarkan sebagai mengatur urutan data dalam array dua dimensi dan kemudian menyortir kolom dari array menggunakan insertion sort.
SEARCHING
Teknik searching merupakan suatu proses pencarian data dari sejumlah data yang ada. Pencarian data dapat dilakukan pada sejumlah data yang sudah terurut atau juga pada data yang sama sekali belum terurut. dalam pencarian data juga terdapat beberapa jenis algoritma, tujuan dari adanya banyak algoritma yang di temukan adalah karena memiliki keuntungan-keuntungan tersendiri, seperti lebih cepatnya bila mengolah data yang jumlahnya lebih dari juta data, ada yang lebih efisien dengan jumlah kurang dari jutaan. serta ada pula yang tidak perlu untuk mengurutkan data terlebih dahulu, tetapi memakan waktu lebih lama.
Ada beberapa jenis teknik searching, sebagai berikut :
1. Line Search
Line Search adalah suatu teknik searching ini dibuat dengan cara melakukan pengecek'an 1 persatu, yaitu antara data yang di cari dengan kumpulan data yang di miliki, Keuntungan metode ini adalah kita tidak perlu mengurutkan data yang ada, bila mencari data pada kumpulan data yang tidak urut hanya terdapat metode ini yang dapat di lakukan.
2. Fibonachi Search
Fibonachi Search yaitu suatu teknik ini hanya dapat digunakan hanya pada kumpulan data yang sudah di urutkan, karena teknik ini melakukan pencarian dengan mencari data melalui pola bilangan fibonachi. Bila pada binnary search pembandingnya adalah nilai pada index tengahnya jumlah data, pada fibonachi search berbeda yaitu: bilangan fibonachi, yang bilangan fibonachinya terdekat dengan jumlah data tetapi tidak lebih besar dari jumlah data yang akan di proses. Bilangan fibonachi itu di jumlahkan dengan batas paling awal data dikurangi 1. Contohnya: jumlah data yang akan di cari adalah 15, maka batas paling bawah adalah 1 dan batas paling akhir=15 dan index pembandingnya= 13(nilai awal + dijumlahkan Bilangan fibonachi - 1) karena bilangan fibonachi terdekat dengan 15 (data ke 1- data ke 15) adalah 13 (1,2,3,5,8,13,21,34.....), bila data yang di cari lebih besar dari bilangan indeks ke tengahnya maka. batas paling bawah= tetap, batas akhir nilai tengah-1, bila data yang dicari lebih kecil maka batas bawah = nilai tengah +1 dan batas akhir tetap, sedangkan nilai tengahnya memakai fungsi tadi.
3. Sequential Search
Sequential search adalah suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.
4. Binary Search
Binary search merupakan salah satu metode searching, binary search hanya bisa dilakukan pada data yg telah tersort ato terurut karena proses algoritmanya yg terus menerus membagi data menjadi 2 bagian hingga angka / input yg dicari ditemukan.
Sumber:
[1] http://sangadik.blogspot.com/2009/11/teknik-sortingpengurutan-data.html
[2] http://lightluna.wordpress.com/2008/10/24/prinsip-algoritma-pada-teknik-tencarian-search-engine/
[3] http://alpro.awardspace.com/tehnik.html
[4] http://mazterchez.blogspot.com/2010/04/teknik-sorting-dan-searching.html
Dewasa ini kita tidak perlu lagi untuk mengurutkan kumpulan data - data dengan cara manual, karena era ini sudah banyak sekali metode atau program untuk melakukan kebutuhan sorting.
Ada 5 metode dalam teknik sorting, diantaranya adalah :
1. Comparison-Based Sorting (pengurutan berdasarkan perbandingan)
# Bubble sort, exchange sort
2. Priority Queue Sorting Method (pengurutan berdasarkan prioritas)
# Selection sort, heap sort
3. Insert and Keep Sorted Method (pengurutan berdasarkan penyisipan dan penjagaan terurut)
# Insertion sort, tree sort
4. Devide and Conquer Method(pengurutan berdasarkan pembagian dan penguasaan)
# Quick sort, merge sort
5. Diminishing Increment Sort Method (pengurutan berkurang menurun)
# Shell sort
- Bubble Sort
Teknik ini dilakukan degan pola membawa nilai terbesar menjadi nilai index terakhir array. jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 samapai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. proses ini dilakuan hingga jumlah data.
- Exchange Sort
Teknik sorting ini dibuat dengan cara pola membawa nilai terbesar menjadi nilai index terakhir array. Jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 samapai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. proses ini dilakuan hingga jumlah data dikurangi 1 atau sampai program tidak melakukan pertukaran. jadi waktu untuk melakukan proses sorting lebih cepat.
- Selection Sort
Teknik sorting ini dibuat dengan cara melakukan pengecek'an 1 persatu, bila kita akan mengurutkan secara ascending maka kita lakukan pengecek'an nilai tempat yang pertama (index pertama pada array)kita bandingkan dengan semua nilai yang ada kita cari nilai minimalnya. lalu simpan index/ letak nilai minimum itu di temukan, setelah pengecekan selesai tukar index awal pengecekan dengan nilai minimum yang telah di simpan tadi. Proses ini dilakukan terus menerus sampai pada pengecekan index terakhir min 1 dengan index terakhir. beda dengan streith selection sort adalah dengan teknik ini melakukan pertukaran nilai lebih sedikit, hanya jumlah data - 1 pertukaran. jadi waktu untuk melakukan proses sorting lebih cepat.
- Heap Sort
Teknik sorting ini dibuat dengan versi yang jauh lebih efisien selection sort. Ia juga bekerja dengan menentukan elemen (atau terkecil) terbesar daftar, menempatkan bahwa pada akhir (atau awal) dari daftar, kemudian melanjutkan dengan sisa daftar, tapi menyelesaikan tugas ini secara efisien dengan menggunakan struktur data yang disebut tumpukan, tipe khusus pohon biner. Setelah daftar data telah dibuat menjadi tumpukan, simpul akar dijamin menjadi unsur (atau terkecil) terbesar. Ketika dipindahkan dan ditempatkan di akhir daftar, tumpukan adalah ulang sehingga elemen terbesar yang tersisa bergerak ke akar. Menggunakan heap, menemukan elemen terbesar berikutnya membutuhkan O (log n) waktu, bukan O (n) untuk linear scan di selection sort sederhana. Hal ini memungkinkan heapsort untuk menjalankan dalam O (n log n) waktu, dan ini juga merupakan kompleksitas kasus terburuk.
- Insertion Sort
Teknik sorting ini dibuat dengan cara menyisipkan atau memasukkan 1 persatu, bila kita akan mengurutkan data, kemudian ingin menyisipkan suatu data maka data tersebut akan otomatis masuk dimana dia berada.
- Quick Sort
Teknik sorting ini dibuat dengan cara yang menggunakan partisi. Pada teknik ini, data dibagi menjadi dua bagian, yaitu data disebelah kiri partisi selalu lebih kecil dari data disebelah kanan. Namun data pada kedua partisi belum terurut, sehingga untuk mengurutkannya, proses pengurutan dilakukan pada kedua partisi secara terpisah. Selanjutnya, data di sebelah kiri dan kanan dipartisi lagi.
- Merge Sort
Teknik sorting ini dibuat dengan cara mengambil keuntungan dari kemudahan penggabungan daftar sudah disortir ke daftar diurutkan baru. Dimulai dengan membandingkan setiap dua elemen (yaitu, 1 dengan 2, kemudian 3 dengan 4 ...) dan swapping mereka jika yang pertama datang setelah kedua. Kemudian masing-masing menggabungkan daftar yang dihasilkan dari dua ke daftar empat, kemudian menggabungkan daftar tersebut empat, dan seterusnya, sampai akhirnya dua daftar digabungkan ke dalam daftar diurutkan akhir.
- Shell Sort
Teknik sorting ini dibuat dengan cara meningkatkan atas bubble sort dan insertion sort dengan menggerakkan keluar dari elemen-elemen memesan lebih dari satu posisi pada suatu waktu. Salah satu implementasi dapat digambarkan sebagai mengatur urutan data dalam array dua dimensi dan kemudian menyortir kolom dari array menggunakan insertion sort.
SEARCHING
Teknik searching merupakan suatu proses pencarian data dari sejumlah data yang ada. Pencarian data dapat dilakukan pada sejumlah data yang sudah terurut atau juga pada data yang sama sekali belum terurut. dalam pencarian data juga terdapat beberapa jenis algoritma, tujuan dari adanya banyak algoritma yang di temukan adalah karena memiliki keuntungan-keuntungan tersendiri, seperti lebih cepatnya bila mengolah data yang jumlahnya lebih dari juta data, ada yang lebih efisien dengan jumlah kurang dari jutaan. serta ada pula yang tidak perlu untuk mengurutkan data terlebih dahulu, tetapi memakan waktu lebih lama.
Ada beberapa jenis teknik searching, sebagai berikut :
1. Line Search
Line Search adalah suatu teknik searching ini dibuat dengan cara melakukan pengecek'an 1 persatu, yaitu antara data yang di cari dengan kumpulan data yang di miliki, Keuntungan metode ini adalah kita tidak perlu mengurutkan data yang ada, bila mencari data pada kumpulan data yang tidak urut hanya terdapat metode ini yang dapat di lakukan.
2. Fibonachi Search
Fibonachi Search yaitu suatu teknik ini hanya dapat digunakan hanya pada kumpulan data yang sudah di urutkan, karena teknik ini melakukan pencarian dengan mencari data melalui pola bilangan fibonachi. Bila pada binnary search pembandingnya adalah nilai pada index tengahnya jumlah data, pada fibonachi search berbeda yaitu: bilangan fibonachi, yang bilangan fibonachinya terdekat dengan jumlah data tetapi tidak lebih besar dari jumlah data yang akan di proses. Bilangan fibonachi itu di jumlahkan dengan batas paling awal data dikurangi 1. Contohnya: jumlah data yang akan di cari adalah 15, maka batas paling bawah adalah 1 dan batas paling akhir=15 dan index pembandingnya= 13(nilai awal + dijumlahkan Bilangan fibonachi - 1) karena bilangan fibonachi terdekat dengan 15 (data ke 1- data ke 15) adalah 13 (1,2,3,5,8,13,21,34.....), bila data yang di cari lebih besar dari bilangan indeks ke tengahnya maka. batas paling bawah= tetap, batas akhir nilai tengah-1, bila data yang dicari lebih kecil maka batas bawah = nilai tengah +1 dan batas akhir tetap, sedangkan nilai tengahnya memakai fungsi tadi.
3. Sequential Search
Sequential search adalah suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.
4. Binary Search
Binary search merupakan salah satu metode searching, binary search hanya bisa dilakukan pada data yg telah tersort ato terurut karena proses algoritmanya yg terus menerus membagi data menjadi 2 bagian hingga angka / input yg dicari ditemukan.
Sumber:
[1] http://sangadik.blogspot.com/2009/11/teknik-sortingpengurutan-data.html
[2] http://lightluna.wordpress.com/2008/10/24/prinsip-algoritma-pada-teknik-tencarian-search-engine/
[3] http://alpro.awardspace.com/tehnik.html
[4] http://mazterchez.blogspot.com/2010/04/teknik-sorting-dan-searching.html
Langganan:
Postingan (Atom)
