LINKED LIST

Linked list (list bertaut) adalah salah satu struktur data dasar yang sangat fundamental dalam bidang ilmu komputer. 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).
Pada array, apabila programmer ingin menyimpan data, programmer diharuskan untuk mendefinisikan besar array terlebih dahulu, seringkali programmer mengalokasikan array yang sangat besar(misal 100). Hal ini tidak efektif karena seringkali yang dipakai tidak sebesar itu. Dan apabila programmer ingin menyimpan data lebih dari seratus data, maka hal itu tidak dapat dimungkinkan karena sifat array yang besarnya statik. Linked list adalah salah satu struktur data yang mampu menutupi kelemahan tersebut.

1. Pengertian
Bekerja dengan data yang besar tidak dapat kita hindari. Dan tidak jarang pula, data besar tersebut memiliki hubungan yang erat. Sebagai contoh, kita akan bekerja dengan file yang menyimpan sangat banyak record, di mana setiap record juga memiliki banyak field. Tugas kita tidak hanya sekadar menampilkan setiap record-nya, melainkan harus pula menambahkan record, menghapus beberapa record sesuai keinginan user, sampai mengurutkan record! Kondisi tersebut mengharuskan kita memiliki satu rantai data yang panjang dan saling berhubungan. Rantai data tersebut harus mampu menampung semua data yang kita miliki. Penggunaan array saja jelas tidak bisa, karena kita bekerja dengan barisan data heterogen. Kita perlu menggunakan union ataupun struct. Namun, kita juga tidak dapat semena-mena menggunakan array of struct dalam jumlah besar. Karena lokasi penampungan memory untuk alokasi konvensional tidak akan mempu mencukupi kebutuhan memory kita. Selain itu, kita mungkin akan melakukan alokasi dan dealokasi beberapa kali di dalam program untuk mengoptimasi penggunaan memory. Solusi yang lebih baik adalah menggunakan linked list, baik singly (single) linked list ataupun doubly (double) linked list. Tetapi pada makalah ini yang dibahas adalah singly (single) linked list.
Nude merupakan komponen-komponen yang membentuk hubungan seperti rantai dengan bantuan pointer. Atau bisa juga dikatakan sebagai beberapa obyek yang saling terhubung dan membentuk linked list. Setiap node terbagi menjadi dua bagian, yaitu bagian data dan bagian penyambung. Bagian data berisi data yang akan disimpan dan diolah. Sedangkan bagian penyambung berisi alamat simpul berikutnya.
Linked adalah koleksi obyek heterogen dengan sifat setiap obyek (kecuali obyek terakhir) mempunyai penerus dan setiap obyek (kecuali obyek pertama) mempunyai pendahulu. Salah satu penggunaan pointer adalah untuk membuat linked list atau senarai berantai. Linked list sendiri dapat diartikan sebagai sekumpulan komponen yang saling berhubungan (berantai) dengan bantuan pointer.
Secara teori, linked list adalah sejumlah node yang dihubungkan secara linier dengan bantuan pointer. Dikatakan singly (single) linked apabila hanya ada satu pointer yang menghubungkan setiap node. Setiap node akan berbentuk struct dan memiliki satu buah field bertipe struct yang sama, yang berfungsi sebagai pointer. Dalam menghubungkan setiap node, kita dapat menggunakan cara first-create-firstaccess ataupun first-create-last-access.
2. Pembahasan
Single linked list atau biasa disebut linked list terdiri dari elemen-elemen individu, dimana masing-masing individu akan saling terhubung. Masing-masing elemen terdiri dari dua bagian, yaitu bagian data atau informasi yang disimpan dan bagian lainnya sebagai penghubung dengan elemen selanjutnya.
Untuk mengakses elemen dalam linked list, dimulai dari instance head dan menggunakan instance nextNode dari elemen selanjutnya untuk berpindah dari elemen ke elemen berikutnya sampai elemen yang diminta dicapai. Dengan single linked list, list dapat dilintasi hanya satu arah dari head ke tail karena masing-masing elemen tidak terdapat link dengan elemen sebelumnya. Sehingga, apabila kita mulai dari head dan berpindah ke beberapa elemen dan berharap dapat mengakses elemen sebelumnya, kita harus mulai dari head.
Asumsikan kita memiliki sejumlah node yang selalu menoleh ke sebelah dalam arah yang sama. Atau, sebagai alat bantu, Anda bisa mengasumsikan beberapa orang yang bermain kereta api. Yang belakang akan memegang yang depan, dan semuanya menghadap arah yang sama. Setiap pemain adalah node. Dan tangan pemain yang digunakan untuk memegang bahu pemain depan adalah variabel next. Sampai di sini, kita baru saja mendeklarasikan tipe data dasar sebuah node. Selanjutnya, kita akan mendeklarasikan beberapa variabel pointer bertipe struct tnode. Beberapa variabel tersebut akan kita gunakan sebagai awal dari linked list, node aktif dalam linked list, dan node sementara yang kita gunakan dalam pembuatan node di linked list. Berikan nilai awal NULL kepada mereka. Berikan deklarasi seperti berikut ini:
struct tnode *head=NULL, *curr=NULL,
*node=NULL;
Dengan demikian, sampai saat ini, kita telah memiliki tiga node. Satu sebagai kepala (head), satu sebagai node aktif dalam linked list (curr) dan satu lagi node sementara (node). Kita telah siap untuk membuat singly linked list. Untuk itu, kita akan memasukkan nilai tertentu sebagai nilai untuk field x dengan cara melakukan perulangan sehingga campur tangan user tidak diperlukan. Seperti yang dikemukakan sebelumnya, kita akan membuat singly linked list dengan cara first-create-first-access. Dengan cara ini, node yang dibuat pertama akan menjadi head. Node-node yang dibuat setelahnya akan menjadi node-node pengikut. Untuk mempermudah pengingatan, ingatlah gambar anak panah yang mengarah ke kanan. Head akan berada pada pangkal anak panah, dan node-node berikutnya akan berbaris ke arah bagian anak panah yang tajam.
[head]->[node1]->[node2]->[node3]…
[noden]->NULL
Apabila kita perhatikan, setiap node memiliki petunjuk untuk node sebelahnya. Bagaimana dengan node terakhir? Kita berikan nilai NULL. Dengan demikian, setiap node kebagian jatah.
Sebagai contoh perhatikan ilustrasi berikut untuk lebih jelasnya:
Single Linked List merupakan jenis Linked List yang hanya menggunakan satu variabel pointer untuk menyimpan banyak data.
Double Linked List Merupakan linked list yang tiap-tiap nodenya menyimpan node sebelumnya dan node yang selanjutnya, atau biasa disebut dengan linked list berpointer ganda.
Circular Linked adalah linked list yang node awalnya menunjuk ke node akhir dan node akhirnya menunjuk ke node awal. Sehingga membentuk link list tersebut membentuk suatu siklus seperti lingkaran.
Pointer pada c++
Penjelasan tentang pointer
pointer adalah built-in type di C dan C++, dimana C++ mengambil konsep pointer dari C. Pointer sebenarnya sangat terkait dengan “Abstract C Machine”, yaitu model mesin abstrak dimana program C bekerja. Abstract C Machine adalah mesin abstrak dimana mesin tersebut memiliki prosesor untuk menginterpretasikan stream of instruction, dan addressable memory yang terbagi kedalam 3 bagian : automatic memory, static memory dan free memory. Addressable memory adalah memory yang konten-nya dapat diambil jika diketahui alamatnya. Lebih jauh lagi, terdapat asumsi bahwa konten memori dapat di ambil dengan waktu konstan, tidak peduli berapa nilai alamat.Hal ini disebut dengan Random Access Memory.
— Penggunaan Awal Pointer
Jika variabel merupakan isi memori, dan untuk mengakses isi memori tersebut diperlukan address, lalu bagaimana cara kita mengetahui alamat dari suatu variabel ? Jawabannya adalah : untuk kebanyakan kasus kita sama sekali tidak perlu tahu alamat dari sebuah variabel. Untuk mengakses sebuah variabel kita hanya perlu nama dari variabel tersebut. Tugas kompiler lah yang mentranslasikan nama ke alamat mesin yang diperlukan oleh komputer.
Akan tetapi terdapat beberapa kasus dimana kita tidak mungkin memberi nama pada sebuah entitas di program kita. Hal ini terjadi terutama saat kita menggunakan data struktur dinamis seperti linked list, resizeable array, tree dan lain sebagainya. Hal ini karena kita tidak mungkin memberi nama terhadap entitas yang mungkin ada atau tidak ada. Struktur seperti linked list hampir mustahil dibuat tanpa pointer tanpa harus mendefinisikan LISP-like list.
Inilah awal mula penggunaan pointer sebagai moniker. Istilah moniker di sini berarti sesuatu yang menunjuk atau mengacu kepada entitas lain. Istilah moniker ini bukanlah istilah standard dan lazim , tetapi sesuatu yang saya pilih impromptu untuk membedakan dengan pointer atau reference yang sudah memiliki arti tersendiri.
Penggunaan lain pointer sebagai moniker adalah untuk mengatasi kelemahan bahasa C awal : Dahulu fungsi – fungsi di C hanya mengerti pass by value. Pointer digunakan untuk mengemulasi pass by reference karena pointer berisi alamat ke objek lain, sehingga fungsi tersebut dapat mengubah objek tersebut dengan memanipulasi pointer.
Pertanyaanya : siapa yang bertugas menentukan alamat objek yang di tunjuk oleh pointer dalam kasus ini ? jelas bukan kompiler karena objek tersebut tidak bernama. Apakah kita sebagai programmer menentukannya sendiri ? ternyata tidak. Hal tersebut ditentukan oleh fungsi malloc dan sejenisnya (dan juga new di C++), atau untuk kasus passing pointer ke dalam fungsi, operator &. Jadi dalam hal ini kita tidak juga menentukan alamat sebuah objek.
— Builtin Array di C dan C++
Sebelum membahas array di C dan di C++, ada baiknya kita membahas tentang array. Array adalah asosiasi antara sebuah index dengan nilai. Jika diketahui sebuah index, kita akan mengetahui nilainya. Dari definisi ini :
1. Tidak disebutkan bahwa index harus integer, atau tipe tertentu.
2. Tidak disebutkan range dari indexnya dimulai dari nilai tertentu, Bahkan tidak disebutkan bahwa indeks nya memiliki batas bawah maupun batas atas.
3. Tidak disebutkan bahwa nilai harus disimpan secara contigous, bahkan tidak disebutkan bahwa nilainya harus di simpan sama sekali.
akan tetapi :
1. Banyak bahasa pemrograman yang di desain tahun 60-an hingga tahun 70-an menentukan bahwa index array adalah integer atau sesuatu yang bisa dikonversi menjadi integer atau sesuatu yang memiliki nilai berurutan seperti integer.
2. Beberapa bahasa menentukan bahwa array dimulai dengan nilai tertentu. contohnya di C, array dimulai dari 0 sementara di Pascal Array dimulai dari 1. Dalam Algo-68 programmer dapat menentukan sendiri batas- batas array. Akan tetapi dalam semua bahasa pemrograman mengakses nilai dengan indeks yang di luar batas dianggap sebagai programming error.
3. Semua bahasa pemrogramman yang saya tahu menyimpan elemen – elemen array di memory. beberapa bahasa, misalnya C, menjamin bahwa elemen – elemen tersebut disimpan dalam memory yang contigous.
Sekarang tipe yang lebih mendekati definisi awal array tersedia dengan nama associative array. Tipe ini didukung oleh beberapa bahasa seperti PHP dan JavaScript, dan juga tersedia dalam beberapa bahasa lain sebagai library ( seperti std::map di C++).
Kembali ke C dan C++ array, kita dapat tentukan beberapa property array : zero based, contigous dan convertible to pointer. Banyak alasan dengan dipilihnya property seperti ini, tapi yang paling penting adalah efisiensi, yang akan kita bicarakan sebentar lagi. setiap array dapat dikonversi menjadi pointer yang menunjuk ke elemen pertama. Hal ini sangat konvenien mengingat dynamic array diciptakan dengan alokasi memori dari free memory (dengan fungsi calloc, yang berarti contigous alloc. yang aneh adalah fungsi ini berperilaku mirip dengan malloc kecuali dia menginisialisasi memori dengan nol. ). Kemudian kita tahu bahwa elemen dalam array di simpan secara berurutan, dengan demikian alamat semua elemen array adalah ptr + n * sizeof(elemen). Dengan mendefinisikan pointer arithmatic, didapat kesamaan ar[idx] == *(ar + idx). hal ini menimbulkan sesuatu yang menarik , ar[idx] == *(ar + idx) == *(idx + ar) == idx[ar] (yes, it is valid C !!).
Operasi pointer arithmatic lain juga didefinisikan untuk pointer. yang menarik adalah increment dan decrement. programmer dapat memeriksa semua elemen dalam array dengan cara menginkremen pointer dari pointer penunjuk elemen pertama. Tentu saja hal yang sama dapat dilakukan dengan indexing biasa, ar[idx], akan tetapi dengan operasi pointer bisa lebih efisien. Alasannya terletak pada bagaimana cara komputer membaca data di ar[idx]. Untuk mesin yang memiliki indexed addressing hal ini cukup sederhana dan efisien (ar jadi base, idx jadi index, fetching cukup 1 instruksi mov). Tetapi untuk mesin yang tidak memiliki indexed addressing, akan ada operasi ADD antara ar dan idx, lalu simpan hasilnya ke suatu tempat (register), lalu baru mov. Kadang – kadang register tersebut digunakan untuk operasi ADD sehingga terdapat beberapa mov untuk menyimpan state. Akan tetapi jika menggunakan pointer arithmatic, cukup meng-increase nilai yang sudah ada di register, lalu mov. Tentu saja instruksi di dalam loop juga mempengaruhi efisiensi ini, tetapi untuk mesin yang mendukung operasi increment langsung, iterasi lewat pointer biasanya lebih efisien.
Ini adalah penggunaan pointer sebagai iterator. Nama iterator diambil dari STL, dan iterator di STL adalah abstraksi dari pointer. Yang menakjubkan adalah konsep iterator, yang digeneralisasi dari pointer, adalah konsep yang cukup powerful untuk merepresentasikan semua algoritma yang bekerja untuk linear container ( linear container adalah semua container yang memiliki iterator yang menunjuk pada elemen pertama, memiliki iterator yang menunjuk pada elemen one-past-end, dan semua elemen dapat dicapai dengan melakukan operasi incremen dari iterator penunjuk elemen pertama sebanyak yang diperlukan. Contoh linear container adalah array, vector, linked – list, dan deque. contoh yang bukan linear container adalah graph dan forest.).
—Fixed memory Location
Dalam pemrograman, kita dihadapkan pada beberapa situasi seperti :
- setelah startup, prosesor 80386 akan memulai eksekusi pada alamat ( … lupa).
- Interrupt vector beberapa prosesor ditaruh pada alamat yang ditentukan oleh pembuat prosesor tersebut.
- Video Memory di DOS dimulai pada alamat (… lupa).
Situasi – situasi tersebut hanya mungkin terjadi jika kita memrogram “close to metal” e.g membuat operating system, atau kita memrogram dalam OS yang super primitif seperti DOS. Dalam kasus – kasus ini kita memerlukan pointer dengan alamat di set ke nilai tertentu. Ini adalah penggunaan pointer sebagai abstraksi alamat di hardware. Penggunaan ini adalah penggunaan pointer paling jarang.
— So, What’s a big deal about it ?
Ketiga fungsi pointer di atas memerlukan operasi yang berbeda- beda. Contohnya jika pointer berfungsi sebagai moniker, operasi yang sangat diperlukan adalah fungsi malloc, calloc, free, new, delete, operator ->, operator * dan operator &. sebagai moniker pointer tidak memerlukan konvertability ke integer dan operasi pointer arihmatic (walaupun ada trik mengakses field struct dari pointer dengan meng-cast pointer to struct menjadi char*, tambahkan offsetnya, lalu baca dengan operator * dan di cast ke tipe field tersebut. trik ini sangat berbahaya dan sebaiknya tidak dipakai ).
Jika pointer berfungsi sebagai iterator, operasi pointer arithmatic adalah esensial. Tetapi operasi new dan delete sama sekali tidak di perlukan (kecuali untuk array of pointer). bottom line is: you do not do memory management via iterator.
Sifat konvertibilitas antara integer dan pointer hanya diperlukan jika pointer tersebut dipakai sebagai abstraksi fixed address. Dua fungsi lain tidak memerlukan sifat ini.
— Pointer in OOP
C++ mendukung OOP, akan tetapi pada saat yang sama juga kompatibel dengan C. Hal ini menimbulkan masalah. Akan tetapi sebelum melihat apa masalahnya, ada baiknya kita bahas sedikit tentang Polymorphism.
Polymorphism adalah jawaban untuk pertanyaan: bagaimana cara menulis fungsi atau prosedur yang tidak dibatasi oleh tipe. contohnya adalah fungsi average, fungsi ini menjumlahkan sejumlah elemen dan membaginya dengan banyaknya elemen. hal ini benar untuk banyak tipe termasuk integer, koordinat kartesian, bilangan kompleks, kuartenion, matrix ,dsb walau aturan penjumlahan tipe – tipe tersebut berbeda. Untuk bahasa yang tidak mendukung polymorphism, anda harus menulis fungsi seperti averageInt, averageMatrix, averageComplex, etc.
Dari sifatnya, polymorphism terbagi dua: ad-hoc polymorphism dimana polymorphism hanya bekerja pada tipe yang sudah ada. contoh mekanisme ad-hoc polymorphism adalah function dan operator overloading. Sedangkan true polymorphism atau parametric polymorphism dapat digunakan bahkan untuk tipe yang belum dispesifikasi. Perbedaan lainnya adalah untuk ad-hoc polymorphism biasanya anda harus menulis fungsi untuk semua tipe yang berpartisipasi dalam mekanisme polymorphism, sperti menulis average untuk integer, lalu untuk quartenion, lalu satu lagi untuk complex, dll. Sedangkan untuk parametric polymorphism anda hanya perlu menulis satu fungsi.
Dari binding-time nya, polymorphism dapat dibagi 2: static dan dynamic polymorphism. Static polymorphism menentukan fungsi mana yang akan di panggil (atau mungkin di generate ) pada saat kompilasi. Sedangkan dynamic polymorphism menentukan fungsi yang di panggil pada saat run-time. contoh static polymorphism adalah template, sedangkan contoh dynamic polymorphism adalah virtual function.
static polymorphism dapat dibagi menjadi predicative atau impredicative, tetapi hal ini tidak ada hubungannya dengan diskusi kita.
Untuk dynamic polymorphism, dapat dibagi lagi berdasarkan berapa banyak parameter yang berpengaruh dari penentuan fungsi. Jika hanya parameter pertama yang berpengaruh, hal ini disebut dengan single dispatch. Jika lebih dari satu, hal ini disebut dengan multimethod. multimethod yang dipengaruhi oleh dua parameter mempunyai nama khusus yaitu double dispatch. Harap perhatikan bahwa p->somefunc(a,b) itu secara prinsip sama dengan somefunc(p,a,b) dimana p adalah this parameter (walaupun semua kompiler akan mereject kalau anda mengganti fungsi seperti itu).
Dynamic Polymorphism juga dapat dibagi berdasarkan constraint nya menjadi dua: Subtyping Polymorphism dimana polymorphic type harus merupakan turunan dari satu base class yang merupakan sebuah interface yang menentukan sifat mana yang polymorphic. Yang lainnya adalah DuckTyping yang tidak memerlukan base class yang berfungsi sebagai interface. Dalam DuckTyping sebuah object dapat menerima message apa saja, walau jika object tersebut tak dapat merespond message tersebut objeck yang bersangkutan akan mengeluarkan error seperti DoesNotUnderstand message di SmallTalk. Untuk subtype polymorphism, hal ini tidak mungkin karena sebuah object hanya akan menghandle message yang didefinisikan di base class, dan kompiler akan mereject message lain.
Kembali ke bahasan kita, C++ mendukung Subtyping single dispatch dynamic Polymorphism. Jadi untuk dynamic polymorphism, semua tipe yang ingin digunakan secara polymorphic harus diturunkan dari satu base class. C++ juga mengharuskan semua fungsi yang bisa dipanggil secara polymorphic harus dideklarasikan virtual. Dan pemilihan fungsi yang diperlukan hanya ditentukan oleh satu parameter (this parameter) melalui mekanisme vtable.
So, what’s the big deal ?
Masalahnya adalah untuk semua bahasa yang menggunakan subtype polymorphism, semua object harus bisa di akses melalui base class nya. Jadi kode berikut harus valid:
Parent p = create_child(); // asumsi nya create child menghasilkan
// object child;
Hal ini menimbulkan pertanyaan : Bagaimana caranya membuat kode di atas valid ?
Dalam bahasa pemrograman tradisional, ketika anda mendeklarasikan sebuah variabel, anda menciptakan instance dari sebuah tipe, kecuali jika dideklarasikan khusus. Di C
Sometype somevar;
artinya anda menciptakan sebuah objek somevar bertipe Sometype.
Sometype somevar2 = somevar;
artinya anda mengkopi nilai somevar ke somevar2
somevar2 == somevar; // OK, ini tidak didefinisikan di C untuk User Defined Type,
// but you got the idea
artinya anda membandingkan nilai somevar dengan nilai somevar2. Mari kita sebut ini value semantic, dimana sebuah variabel mengandung isi instance dari tipe tertentu.
Lalu perhatikan kode berikut :
Child child;
Parent parent = child;
See the problem ? Masalahnya adalah anda mencoba mengkopi nilai child ke variabel parent, tapi apa artinya operasi kopi tersebut ? jika berarti mengopi nilai byte by byte, implikasinya adalah ukuran parent dan child harus sama. Akan tetapi hal ini sulit atau tidak mungkin dipenuhi. Bila parent adalah pure interface, parent hampir tidak memiliki data member, tapi child akan memiliki data member untuk mendukung operasi – operasi method-nya.
Bagaimana cara mengatasinya ? salah satu cara yang populer adalah dengan tidak menggunakan value semantic. Di bahasa seperti Java, setiap variable adalah reference ke sebuah instance. Artinya:
1. Ketika anda mendeklarasikan sebuah variabel, anda tidak menginstansiasi sebuah object. object harus di instansiasi secara terpisah, biasanya lewat operator new.
2. Ketika anda mengkopi dua buah variabel, anda tidak mengkopi instance byte by byte, tapi hanya membuat dua reference mengacu pada object yang sama. Jika ingin menghasilkan kopi dari instance, biasanya anda menggunakan method seperti clone.
3. Ketika anda membandingkan dua buah variabel, anda hanya mengetahui apakah dua variabel tersebut merujuk pada objek yang sama atau tidak. jika anda ingin membandingkan nilainya, anda harus menggunakan method seperti equal.
let’s call this reference semantic.
Masalahnya C++ karena berbagai alasan (salah satunya kompatibilitas dengan C) tidak mungkin mengadopsi reference semantic dan harus tetap menggunakan value semantic. Akan tetapi reference semantic sepertinya diperlukan untuk subtype polymorphism. so, what to do ? Ternyata Pointer adalah object yang dapat dipakai untuk mengemulasi reference semantic tanpa harus mengubah bahasa menggunakan reference semantic.
Dengan demikian dynamic polymorphism di C++ harus menggunakan pointer (atau reference, yang sebenarnya adalah pointer dengan sedikit perubahan sifat).
— Bahaya Pointer
1. Bahaya yang mungkin ada dengan pointer sebagai moniker: memory leak, double delete, invalid memory access. Semuanya dapat dihindari dengan ownership analysis yang bagus (pada setiap saat, harus diketahui pihak mana yang bertanggung jawab mendelete sebuah object). Jika hal ini sulit dilakukan, misalnya karena shared ownership, anda dapat menggunakan smart pointer atau garbage collector.
2. Bahaya yang mungkin ada dengan pointer sebagai iterator: array out of bound. Salah satu cara yang efektif menghindari hal ini adalah dengan menggunakan standard algorithm.
3. Bahaya yang mungkin ada dengan pointer sebagai abstraksi fixed memory : Tidak tahu, tetapi ini bukan mainan sembarang programmer.
— Bahasa Pemrograman tanpa pointer ?
1. Semua Bahasa pemrograman Fungsional, terutama yang murni , tidak mengenal pointer atau memerlukan pointer. Akan tetapi bahasa ini menggunakan model komputasi yang jauh berbeda, bukan abstract C machine.
2. Beberapa bahasa pemrograman dengan reference semantik dapat mengklaim mereka tidak memiliki pointer, akan tetapi setiap variabel sebenarnya adalah pointer. Secara fisik mungkin reference tidak memiliki struktur seperti pointer (biasanya merupakan data struktur yang lebih kompleks sehingga lebih friendly terhadap garbage collector) tapi reference tersebut memiliki fungsi yang mirip dengan pointer di C atau C++. Ada yang bilang bahwa reference dalam bahasa – bahasa ini menyebabkan optimasi lebih mudah karena tidak menyebabkan aliasing, tetapi optimasi tersebut juga mungkin dilakukan di C dan C++ ( dengan restrict pointer, sayangnya belum merupakan bagian dari standard C++).


Sumber : http://id.wikipedia.org/wiki/Linked_list
http://islam-download.net/tips-tricks/software-tips-windows/doubly-linked-list-pada-c-c.html

Prinsip algoritma pada teknik pencarian search engine

Search engine adalah sebuah sistem yang diperuntukkan untuk pencarian dan pengambilan informasi untuk menampilkan hasilnya. Biasanya sistem ini berbasis indeks beberapa dokumen HTML, sehingga pencarian dapat dengan mudah dilakukan.
Bisa anda bayangkan bagaimana search engine mencari keyword yang anda masukkan dalam milyaran halaman web, mengindeks atau mengurutkannya berdasarkan prioritas dan menampilkannya ke browser web anda dalam hitungan kurang dari 0.5 detik.
Semua bagian yang terdapat dalam setiap search engine adalah penting, namun ada satu bagian yang sangat penting dari setiap search engine. Apa itu? Yup, Algoritma Pencarian.
Algoritma Search engine
Algoritma search engine merupakan suatu instruksi yang menyusun sekumpulan halaman web berdasarkan kata kunci. Instruksi tersebut menganalisis komponen-komponen dari sebuah halaman web, seperti judul, struktur link ke halaman lain, dan sebagainya. Ketika pengguna mencari dokumen maka search engine akan mengakses data yang telah dikumpulkan sebelumnya. Pencarian tersebut dilakukan berdasarkan kata kunci yang dimasukkan oleh pengguna. Pada umumnya algoritma search engine mencari kata dalam dokumen dan menghitung banyaknya kemunculan kata tersebut. Kemudian dokumen yang memiliki lebih banyak jumlah kata kunci tersebut berada di urutan paling atas. Tetapi cara ini kurang efektif sebab banyaknya kemunculan kata kunci tidak selalu menentukan isi dokumen. Dan bahkan seringkali tidak berhubungan sama sekali dengan
apa yang dicari oleh pengguna.
Jenis-jenis algoritma pencarian nilai yang akan kita bahas adalah pencarian secara linear
(sequential search) dan pencarian biner (binary search)
Pencarian secara linear mempunyai dua jenis metode yaitu dengan boolean dan tanpa boolean.
Jenis-jenis algoritma pengurutan nilai yaitu count sort (pengurutan dengan mencacah), selection sort (pengurutan dengan menyeleksi), insertion sort (pengurutan dengan penyisipan), quick sort (pengurutan cepat), merge sort (pengurutan dengan penggabungan), heap sort (pengurutan dengan tumpukan), shell sort (pengurutan cangkang, dan bubble sort (pengurutan gelembung).
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.
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.
Count sort
merupakan jenis algoritma yang dapat diterapkan hanya dibawah kondisis-kondisi tertentu. Namun, apabila kondisi yang dihadapi berbalik maka akan jadi yang paling tercepat. CountSort dapat digunakan untuk jenis variable yang bertipe integer
Selection Sorting
adalah teknik atau cara untuk mengurutkan suatu deretan data. Teknik atau algoritma untuk melakukan pengurutan, sesungguhnya ada beberapa, salah satunya: Selection Sort. Selection Sort salah satu algoritma pengurutan yang mudah untuk dipelajari.
Konsep dasarnya yaitu : “Melakukan pencarian data terkecil/terbesar pada suatu iterasi. Kemudian data tersebut ditukar dengan data[index]. index=iterasi. Jumlah iterasi ditentukan oleh banyaknya data
Insertion sort
merupakan salah satu teknik sorting yg mengurutkan data secara ascending (dari kecil ke besar), dengan cara insert / memasukkan data. (Kamu dapat mencari simulasi proses sort nya)
Quick Sort
Quick sort adalah algoritma yang menggunakan metode divide and qonquer yaitu dengan mempartisi tabel dengan acuan elemen tabel yang dijadikan sebagai pivot. Tabel dipartisi menjadi tabel dengan elemen pivot, < pivot dan > pivot, hingga elemen tersebut terurut.
Merge sort
adalah algritma yang digunakan untuk menyusun list yang diberikan dengan cara membagi list yang diberikan menjadi dua bagian yang lebih kecil. Kedua list yang baru ini kemudian akan disusun secara terpisah. Setelah kedua buah list tersusun, maka akan dibentuk list baru yang merupakan hasil penggabungan dua buah list sebelumnya
Heap Sort
Heapsort merupakan salah satu bentuk dari selection sort yang memiliki kompleksitas algorima yang menggunakan struktur data heap.
Algoritma ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari sebuah daftar elemen, dan diletakkan pada akhir (atau awal) dari daftar tersebut. Heap sort menyelesaikan sebuah pengurutan menggunakan struktur data yang disebut heap.
Shell Sort
salah satu algoritma pengurutan yang lebih handal dibandingkan Selection Sort dan Bubble Sort.
Kehandalannya yaitu : “Membagi deret data menjadi dua bagian. Masing-masing bagian diurutkan menggunakan Bubble Sort. Tidak menggunakan iterasi melainkan increment. Perulangan diakukan sesuai nilai increment.”
Bubble Sort
Seperti gelembung (”bubble”) yang timbul ke permukaan air, metode ini juga menimbulkan angka terbesar dan menaruhnya pada akhir urutan, mengatur sampai urut dari kecil sampai besar. Untuk metode sorting ini, semua data dibacakan terlebih dahulu ke omputer dan disimpan di “memori komputer”, kemudian pengurutan baru dilakukan
Straight Selection
Metode ini sebenarnya kebalikan dari metode bubble sort. Metode seleksi langsung ini akan memilih nilai yang terkecil dan meletakkannya di urutan terkemuka. Nilai-nilai terkecil berikutnya akan diseleksi dan diletakkan diurutan setelah nilai terkecil pertama, kedua, dan seterusnya sampai akhirnya di dapat nilai yang urut dari kecil ke besar. Program berikut akan mengambil data yang sama dengan metode Bubble sort. Dari hasil output langkah-langkah pengurutan akan tampak perbedaan proses pengurutannya.

perkembangan komputer di bidang elektronik

Perkembangan Komputer dari Waktu ke Waktu

Perkembangan komputer dari masa ke masa salalu mengalami peningkatan. Pada awalnya komputer bukanlah alat yang diciptakan untuk berbagai kegunaan seperti yang kita amati pada zaman sekarang. Dulu komputer diciptakan hanya sebagai alat untuk mempermudah dalam penghitungan atau lebih mudahnya sebagai mesin hitung matematika. Tetapi seiring dengan perkembangan zaman komputer ini terus berevolusi menjadi mesin serba guna khususnya pada bidang industri dan penelitian.
Oleh karena itu, kata dasar komputer berasal dari kata “compute” yang berarti menghitung dengan kata lain komputer berati alat penghitung. Komputer pertama kali ditemukan oleh Charles Babbage, kecerdasannya logika matematikanya yang sangat sepesial membuatnya mampu menciptakan sebuah mesin yang dia sebut dengan nama Analytical Engine pada tahun 1882, sebuah mesin yang berfungsi sebagai alat perhitungan-perhitungan umum.
Beberapa tahun kemudian munculah John V. Atanasoff dengan komputer rancangannya Atanasoff-Berry Computer (ABC) pada tahun 1937 yang kemudian dianggap resmi menjadi komputer elektronik pertama. selang beberapa tahun kemudian munculah ENIAC ( Electronic Numerical Integrator and Computer) yang di perkenalkan oleh John Mauchly dan J. Presper Eckert. Sebuah mesin yang dibuat oleh kerjasama antara pemerintah Amerika Serikat dan University of Pennsylvania. Terdiri dari 18.000 tabung vakum(vacum tube), 70.000 resistor, dan 5 juta titik solder, komputer tersebut merupakan mesin yang sangat besar yang mengkonsumsi daya sebesar 160kW.
1. Komputer Generasi Pertama
Komputer genarasi pertama ini disebut juga sebagai komputer dinosaurus karena ukurannya yang relatif besar. Hanya orang yang ahli sajalah yang dapat menggunakan komputer ini karena sangat sulit dan daya komputesinya sangatlah lambat.
Ciri ciri komputer pada generasi pertama adalah sebagai berikut :
• Komponen elektronikanya dari Tabung Hampa (Vacuum Tube)
• Program dibuat dalam bahasa mesin (Machine Language), yang programnya tersimpan dalam memori komputer. Programnya masih menggunakan bahasa mesin dengan menggunakan kode 0 dan 1 dalam urutan tertentu.
• Sifat-sifatnya:
o Ukurannya besar dan memerlukan tempat yang sangat luas
o Memerlukan banyak Pendingin (AC) karena banyak mengeluarkan panas
o Prosesnya relatif lambat
o Kapasitas untuk menyimpan data kecil.
• Pabrik yang memproduksi; UNIVAC, IBM, BURROGHS, HONEYWELL
• Contoh mesin; ENIAC, MARK II, EDSAC, MARK III, UNIVAC I & II, IBM 650, ADVAC
Komputer generasi pertama berawal dari tahun 1942 hingga tahun 1959
2. Komputer Generasi Kedua
Komputer generasi kedua ini muncul pada era 1960-an dan dulu komputer ini banyak di gunakan di berbagai perusahaan perusahaan khususnya dalam bidang bisnis. Ukurannya lebih kecil ketimbang komputer generasi pertama yaitu kira kira seukuran lemari saja. Pada era ini juga manusia telah mengenal printer, memori, disket ataupun sitem operasi.
Ciri ciri komputer generasi kedua adalah sebagai berikut :
• Komponen elektronikanya dari Transistor
• Program dibuat dengan Assembly Language, Common Business-Oriented Language (COBOL) dan Formula Translator (FORTRAN) dan ALGOL
• Sifat-sifatnya:
o Ukurannya relatif kecil
o Tidak banyak mengeluarkan panas
o Telah mengenal Magnetic Tape dan Magnetic Disk untuk menyimpan data
o Mulai mengenal Tele Processing (time sharing yang memungkinkan beberapa user dapat memakai kokmputer secara bersama-sama)
o Proses relatif lebih cepat
o Kapasitas untuk menyimpan data semakin besar.
• Pabrik yang memproduksi; UNIVAC, IBM, BURROGHS, HONEYWELL, CDC (Control Data Corporation), NCR
• Contoh mesin; IBM (IBM 1620, IBM 1401, IBM 7070, IBM 7080, IBM 7094), UNIVAC III, CDC 6600 Super dan CDC 7600, BURROGHS 5500, HONEYWELL 400, PDP 1 & 5
Walaupun komputer ini telah menggunakan transistor yang mana menggantikan fungsi tabung hampa tetapi tetap saja mengeluarkan panas walaupun tidak sebanyak yang di keluarkan oleh komputer generasi pertama dan itu dapat berpotensi untuk merusak komponen komponen yang ada pada komputer. Pada generasi ini juga bermunculan banyak programmer, analyst dan ahli di bidang komputer serta juga bermunculan dan mulai berkembang industr piranti lunak atau softwere.
3. Komputer Generasi Ketiga
Komputer generasi ketiga merupakan perkembangan yang paling pesat dari perkembangan komputer yang ada. Komputer generasi ketiga muncul sejak era 1965-1971-an. Transistor yang dianggap tidak effisien lagi membuat manusia mencari solusi lain dan solusi itu di temukan pada batu kuarsa ( Quartz rock ). Jack Kilby, seorang insinyur di Texas Instrument, mengembangkan sirkuit terintegrasi (IC : integrated circuit) di tahun 1958. Hal ini merupakan sebuah inovasi yang dapat mendongkrak munculnya komputer generasi ketiga.
Ciri ciri komputer generasi ketiga adalah sebagai berikut :
• Komponen elektronikanya dari Integrated Circuit (IC) yang berbentuk lempengan atau chip
• Program dibuat dengan bahasa tingkat tinggi (High Level Language), yaitu: BASIC, FORTRAN, COBOL
• Sudah menerapkan konsep multi processing dan dapat menjalankan program lebih dari satu multi programming dalam waktu yang bersamaan
• Dapat berkomunikasi dengan peralatan lain untuk melakukan komunikasi data seperti telepon dengan komputer.
• Sifat-sifatnya:
o Ukurannya lebih kecil dari komputer generasi kedua
o Mulai mengenal Multi Programming dan Multi Processing
o Adanya integrasi antara Software dan Hardware dalam Sistem Operasi
o Prosesnya sangat cepat
o Kapasitas untuk menyimpan data lebih besar.
• Pabrik yang memproduksi; IBM, BURROGHS, HONEYWELL, NCR
• Contoh mesin; IBM S/360, UNIVAC 1108, PDP 8 & 11, HONEYWELL 200, RCA, SPECTRA 70.
Pada era ini juga mulai digunakannya sistem operasi (operation sistem) yang memungkinkan mesin menjalankan berbagai program yang berbeda secara serentak dengan sebuah program utama yang memonitor dan mengkoordinasi memori komputer. Sistem operasi komputer pada generasi ketiga adalah UNIX dan Windows. Walapupun grafiknya masihlah sangat minim.
4. Komputer Generasi Keempat
Komputer generasi keempat adalah komputer yang kita temui pada saat ini. Komputer yang dalam komponen elektriknya masih menggunakan mikrochip walaupun ukurannya dan bahan yang digunakan berbeda. Ukurannya lebih kecil membuat ukuran komputerpun lebuh sederhana.
Ciri ciri komputer generasi keempat adalah sebagai berikut :
• Komponen elektronikanya dari miniaturisasi yang disebut LSI dan mulai memperkenalkan VLSI (Very Large Scale Integration) yang merupakan paduan dari IC dengan kapasitas rangkaian dapat mencapai 100.000 komponen tiap chip
• Mulai dikembangkan suatu jaringan komputer lokal yang menggunakan ARCNET (Attach Research Computing Network)
• Program dibuat dengan bahasa: BASIC, FORTRAN, COBOL, PASCAL
• Sifat-sifatnya:
o Ukurannya relatif lebih kecil
o Sudah menerapkan Multi Programming dan Multi Processing
o Mengenal DataBase Management System (DBMS).
• Pabrik yang memproduksi; IBM, BURROGHS, HONEYWELL, INTEL
• Contoh mesin; IBM (IBM S/34, IBM S/36, IBM PC/AT & XT, IBM PS/2), HONEYWELL 700, BURROGHS 600, CRAY I, CYBER, PC Aplle II, COMMODORE PC ,INTEL i386 sampai dengan intel Pentium I, II, III, IV, Dual Core, Core 2 Duo, dan Quad Core.
Komputer genarasi ini telah berkembang sangat pesat karena penggunannya yang sangat mudah (friendly user) dan serba guna apalagi di bidang industri dan teknologi informasi, peranan komputer sangatlah membantu.
5. Komputer Generasi Kelima
Rencana masa depan komputer generasi ke lima adalah komputer yang telah memiliki Artificial Intelligence (AI). Sehingga komputer di masa depan dapat memberikan respon atas keinginan manusia.
Ciri ciri komputer generasi kelima adalh sebagai berikut :
• Komputer generasi ini masih dalam tahap pengembangan dan pemakainya belum banyak. Pengembangan komputer genarasi ini dipelopori oleh negara Jepang
• Komponen elektronikanya menggunakan bentuk paling baru dari chip VLSI
• Program dibuat dalam bahasa PROLOG (Programming Logic) dan LISP (List Processor)
• Komputer generasi kelima difokuskan kepada AI (Artificial Inteligence / Kecerdasan Buatan), yaitu sesuatu yang berhubungan dengan penggunaan komputer untuk melaksanakan tugas-tugas yang merupakan analog tingkah laku manusia.
• Sifat-sifatnya:
o Dapat membantu menyusun program untuk dirinya sendiri
o Dapat menerjemahkan dari suatu bahasa ke bahasa lain
o Dapat membuat pertimbangan-pertimbangan logis
o Dapat mendengar kalimat perintah yang diucapkan serta melaksanakannya
o Dapat memilih setumpuk fakta serta menggunakan fakta yang diperlukan
o Dapat mengolah gambar-gambar dan grafik dengan cara yang sama dengan mengolah kata, misalnya dapat melihat serta mengerti sebuah foto.
Dua tanda tanda akan munculnya inovasi komputer generasi kelima adalah komputer paralel yang berarti memungkinkan banyak CPU bekerja sama membentuk suatu jaringan yang efisien. Selin itu ditemukannya superkonduktor yang memungkinkan aliran listrik mengalir tanpa hambatan sedikitpun sehingga dapat meningkatkan kecepatan informasi yang di dapat. Lembaga ICOT (Institute for new Computer Technology) juga dibentuk untuk merealisasikan keberadaan komputer generasi kelima ini.
Berikut ini beberapa kejadian penting yang memberi dampak besar bagi sejarah perkembangan komputer:
• 1936 – Alan Turing mempublikasikan “On Computable Numbers,” yang berisi konsep mengenai sebuah mesin penghitung fantasy yang disebutnya the Turing Machine, yang akhirnya dijadikan sebagai pondasi bagi mesin penghitung modern.
• 1937 – John V. Atanasoff mulai mengerjakan the Atanasoff-Berry Computer (ABC), yang kemudian secara resmi dianggap sebagai komputer elektronik pertama.
• 1943 – Thomas (Tommy) Flowers mengembangkan Colossus, sebuah komputer yang digunakan oleh Inggris sebagai pemecah kode untuk mesin Enigma cipher yang dibuat oleh pihak Jerman.
• 1945 – John von Neumann menulis “First Draft of a Report on the EDVAC,” yang berisi konsep mengenai arsitekture dari media penyimpan modern untuk program komputer.
• 1946 – ENIAC diperkenalkan, sebuah mesin penghitung elektronik yang dibuat oleh John Mauchly dan J. Presper Eckert.
• 1953 – IBM memasarkan komputer elektronik yang pertama, yaitu 701.
• 1956 – Dijadikan sebagai era dari magnetic disk storage dengan dipasarkannya 305 RAMAC oleh IBM ke Zellerbach Paper di San Francisco.
• 1958 – Jack Kilby berhasil membuat integrated circuit pertama di Texas Instruments, ini untuk membuktikan bahwa resistor dan kapasitor bisa bersatu dalam materi semiconductor yang sama.
• 1964 – CDC’s 6600 supercomputer, yang di design oleh Seymour Cray, mampu melakukan lebih dari tiga juga instruksi perdetik—kemampuan ini tiga kali lebih cepat di banding pesaing terdekatnya, IBM Stretch.
• 1964 – IBM memperkenalkan System/360.
• .
• 1971 – Sebuah tim di IBM’s San Jose Laboratories berhasil membuat 8” floppy disk.
• 1971 – Iklan pertama untuk sebuah microprocessor, Intel 4004, muncul di Electronic News.
• 1971 – Kenbak-1, salah satu PC pertama di iklankan dan dijual dengan harga $750 di Scientific American.
• 1972 – Hewlett-Packard mengumumkan HP-35 sebagai “a fast, extremely accurate electronic slide rule” dengan sebuah solid-state memory yang sama dari sebuah komputer.
• 1974 – Para peneliti dari Xerox Palo Alto Research Center mendesign Alto, workstation pertama yang dilengkapi dengan sebuah built-in mouse sebagai input.
• 1974 – Scelbi mengiklankan 8H computer-nya, komputer berbasis microprocessor (Intel’s 8008) pertama di US.
• 1975 – Telenet, packet-switching network komesial dan civilian equivalent dari ARPAnet, lahir.
• 1975 – Majalah Popular Electronics edisi Januari, memperkenalkan Altair 8800, yang berbasis pada microprocessor Intel’s 8080.
• 1975 – Prototype dari Visual Display Module (VDM), di design oleh Lee Felsenstein, ditandai sebagai implementasi dari sebuah memory-mapped alphanumeric video display pertama untuk personal computers.
• 1976 – 5 1/4” flexible disk drive dan disk diperkenalkan oleh Shugart Associates.
• sukses.
• 1977 – Tandy Radio Shack memperkenalkan TRS-80.
• 1977 – Apple Computer memperkenalkan Apple II.
• 1977 – Commodore memperkenalkan PET (Personal Electronic Transactor).
• 1978 – VAX 11/780 dari Digital Equipment Corp. memperkenalkan fitur virtual memory yang mampu mencapai 4.3GB, menyediakan ratusan kali kapasitas bagi banyak minicomputer.
• , Athlon versi hemat dengan pengurangan pada L2 cache.
• 2000 – Intel memperkenalkan Pentium 4, processor terakhir Intel dengan Architecture 32-bit (IA-32) family.
• 2001- Intel memperkenalkan processor 2GHz pertama, sebuah versi lain dari Pentium 4.
• 2001 – Microsoft merelease Windows XP edisi Home dan Professional, yang merupakan sistem operasi gabungan dari sistem operasi untuk konsumen rumahan (9x/Me), dan konsumen bisnis (NT/2000).
• 2002 – Intel merelease processor 3GHz-class, sebuah versi 3.06GHz dari Pentium 4. Processor ini juga memperkenalkan Intel’s Hyper-Threading (HT) technology (yang membuat sebuah processor mampu mengerjakan dua threads aplikasi secara bersamaan) untuk komputer desktop.
• 2003 – AMD merelease Athlon 64, processor 64-bit pertama, yang ditargetkan untuk konsumen mainstream dan pasar bisnis.
• Dan yang terakhir intel merelease Pentium Core2duo.



PENERAPAN DI BIDANG ELEKTRONIKA

• Kecepatan dan ketepatan komputer sangat bermanfaat dalam pengolahan data padaaplikasi teknik

• Para ahli nuklir dapat membuat model reactor nulkir pada layar komputer, tidak perlu membuat model yang sebenarnya. Kondisikondisi yang diperlukan pada reaktor nuklir dapat diprogram, dan dapat dicoba diberikan data yang melampaui batas keamanan reactor tersebut.

• Komputer dapat juga digunakan untuk membuat model molekul-molekul, yang dapat ditampilkan secara grafik pada layar komputer. Melalui grafik ini, ahli kimia dapat mengamati bagaimana molekul-molekul tersebut bereaksi dengan yang lainnya.

• Komputer juga dapat dipergunakan pada bidang geologi untuk mempelajari keadaan tanah serta contour dari suatu daerah

• Aplikasi yang lain dari komputer dalam bidang teknik adalah computer aided design

Daftar Pustaka
http://www.bismillahslamet.com/2009/08/sejarah-komputer-dan-perkembangannya.html
http://id.wikipedia.org/wiki/Sejarah_komputer
http://linux.or.id/node/982
http://e-majalah.com/agusruslan2-6-07.html

spanning tree dan penerapannya di bidang elektronika

pengertian

Spanning Tree Protocol disingkat menjadi STP, Merupakan bagian dari standard IEEE 802.1 untuk kontrol media akses. Berfungsi sebagai protocol untuk pengaturan koneksi dengan menggunakan algoritma spanning tree.
Kelebihan STP dapat menyediakan system jalur backup & juga mencegah loop yang tidak diinginkan pada jaringan yang memiliki beberapa jalur menuju ke satu tujuan dari satu host.
Loop terjadi bila ada route/jalur alternative diantara host-host. Untuk menyiapkan jalur back up, STP membuat status jalur back up menjadi stand by atau diblock. STP hanya membolehkan satu jalur yang active (fungsi pencegahan loop) diantara dua host namun menyiapkan jalur back up bila jalur utama terputus.
Bila "cost" STP berubah atau ada jalur yang terputus, algoritma spanning tree merubah topology spanning tree dan mengaktifkan jalur yang sebelumnya stand by.

Prinsip Kerja STP
Masalah umum yang bisa diatasi oleh Spanning Tree Protocol ini adalah broadcast storm. Broadcast storm menyebabkan banyak broadcast ( atau multicast atau unknown-destination unicast) pada loop yang ada di jaringan secara terus menerus. Hal ini akan menciptakan sebuah link yang tidak berguna (karena adanya link ganda antar bridge/switch) dan secara signifikan akan mempengaruhi performance dari komputer end-user karena terlalu banyak memproses broadcast yang ada.

•Menentukan least cost paths ke root bridge.
Spanning tree yang sudah dihitung mempunyai properti yaitu pesan dari semua alat yang terkoneksi ke root bridge dengan pengunjungan (traverse) dengan cost jalur terendah, yaitu path dari alat ke root memiliki cost terendah dari semua paths dari alat ke root.Cost of traversing sebuah path adalah jumlah dari cost-cost dari segmen yang ada dalam path. Beda teknologi mempunya default cost yang berbeda untuk segmen-segmen jaringan. Administrator dapat memodifikasi cost untuk pengunjungan segment jaringan yang dirasa penting.

•Menentukan root bridge.
Root bridge dari spanning tree adalah bridge dengan bridge ID terkecil (terendah). Tiap bridge mempunyai unique identifier (ID) dan sebuah priority number yang bisa dikonfigurasi. Untuki membandingkan dua bridge ID, priority number yang pertama kali dibandingkan. Jika priority number antara kedua bridge tersebut sama, maka yang akan dibandingkan selanjutnya adalah MAC addresses. Sebagai contoh, jika switches A (MAC=0000.0000.1111) dan B (MAC=0000.0000.2222) memiliki priority number yang sama, misalnya 10, maka switch A yanga akan dipilih menjadi root bridge. Jika admin jaringan ingin switch B yang jadi root bridge, maka priority number switch B harus lebih kecil dari 10.

•Non-aktifkan root path lainnya.
Karena pada langkah diatas kita telah menentukan cost terendah untuk tiap path dari peralatan ke root bride, maka port yang aktif yang bukan root port diset menjadi blocked port. Kenapa di blok? Hal ini dilakukan untuk antisipasi jika root port tidak bisa bekerja dengan baik, maka port yang tadinya di blok akan di aktifkan dan kembali lagi untuk menentukan path baru.
Spanning tree algoritma secara automatis menemukan topology jaringan, dan membentuk suatu jalur tunggal yang yang optimal melalui suatu bridge jaringan dengan menugasi fungsi-2 berikut pada setiap bridge. Fungsi bridge menentukan bagaimana bridge berfungsi dalam hubungannya dengan bridge lainnya, dan apakah bridge meneruskan traffic ke jaringan-2 lainnya atau tidak.
1. Root bridge
Root bridge merupakan master bridge atau controlling bridge. Root bridge secara periodik mem-broadcast message konfigurasi. Message ini digunakan untuk memilih rute dan re-konfigure fungsi-2 dari bridge-2 lainnya bila perlu. Hanya da satu root bridge per jaringan. Root bridge dipilih oleh administrator. Saat menentukan root bridge, pilih root bridge yang paling dekat dengan pusat jaringan secara fisik.
2. Designated bridge
Suatu designated bridge adalah bridge-2 lain yang berpartisipasi dalam meneruskan paket melalui jaringan. Mereka dipilih secara automatis dengan cara saling tukar paket konfigurasi bridge. Untuk mencegah terjadinya bridging loop, hanya ada satu designated bridge per segment jaringan
3. Backup bridge
Semua bridge redundansi dianggap sebagai backup bridge. Backup bridge mendengar traffic jaringan dan membangun database bridge. Akan tetapi mereka tidak meneruska paket. Backup bridge ini akan mengambil alih fungsi jika suatu root bridge atau designated bridge tidak berfungsi.
Semua implementasi Spanning protocol didasarkan pada algoritma IEEE 802.1.d. Dengan bertukar pesan dengan switch lain untuk mendeteksi loop, dan kemudian mengeluarkan loop dengan menutup dipilih antarmuka jembatan, algoritma ini menjamin bahwa ada satu dan hanya satu jalur yang aktif antara dua perangkat jaringan.
Secara sederhana, IEEE 802.1d algoritma spanning tree protocol seperti berikut :
•Menghilangkan loop di-link jaringan berlebihan secara efektif menonaktifkan link.
•Monitor untuk kegagalan link aktif dan mengaktifkan kembali redundant link untuk memulihkan jaringan agar penuh konektivitas (sambil menjaga bebas topologi loop).
Keuntungan dari spanning tree algoritma :
Spanning tree algoritma sangat penting dalam implementasi bridge pada jaringan anda. Keuntungan nya adalah sebagai berikut:
•Mengeliminir bridging loops
•Memberikan jalur redundansi antara dua piranti
•Recovery secara automatis dari suatu perubahan topology atau kegagalan bridge
•Mengidentifikasikan jalur optimal antara dua piranti jaringan
•Menyediakan system jalur backup menjadi stand by atau diblock. STP hanya membolehkan satu jalur yang active (fungsi pencegahan loop) diantara dua host namun menyiapkan jalur back up bila jalur utama terputus.
•Mencegah loop yang tidak diinginkan pada jaringan yang memiliki beberapa jalur menuju ke satu tujuan dari satu host. Loop terjadi bila ada route/jalur alternative diantara host-host.
Penerapan di Kehidupan dan di Bidang Elektro
Algoritma Semut merupakan salah satu algoritma sistem cerdas yang belum banyak diterapkan terutama dalam kasus minimum spanning tree. Penyelesaian kasus dengan Algritma Semutini didasarkan pada tingkah laku semut dalam memperoleh makanan dengan memilih lintasan terpendek. Ciri pengolahan data dengan Algoritma Semut ini permaasalahan yang harus mempunyai siklus tertutup yang artinya node awal semut berangakat juga merupakan node akhir semut kembali.
Pemasanagn kabel telepon yang dgunakan oleh PT. Telkom sebelumnya adalah pemasangan dengan menggunakan rute terpendek yang didasarkan secara intituisi. Pemasangan ini merupakan pemasangan yang tidak sistematis sehingga hasil yang dihasilkan tidak optimal. Hasil awal yang digunakan pada 21 titik dengan menggunakan Q.S 3.0 maupun dengan perhitungan manual menggunakan algoritma kruskal adalah 2235 meter. Namun sayangnya dalam menggunakan Algoritma Semut memperoleh penyelesaian yang lebih optimal yaitu panjang lintasannya dalah 2461 meter. Walaupun terjandi perbedaan jarak yang sangat besar, namun dari segi penghematan waktu, dengan menggunakan algoritma semut perhitungan lebih cepat.
Pertumbuhan kehidupan ekonomi masyarakat yang pesat saat ini, dimana masyarakat dihadapkan pada kecanggihan teknologi yang mendorong manusia untuk berusaha mendapatkan informasi yang lebih cepat, mudah, dan akurat. Hal ini tidak hanya berlaku bagi negara maju saja, namun bagi negara-negara yang sedang berkembang misalnya Indonesaia pun jasa telekomunikasi sangat dibutuhkan. Dengan kata lain bahwa pertumbuhan ekonomi tidak boleh tidak harus sejalan dengan pembangunan sarana komunikasinya.
Pembangunan jaringan yang dilakukan sekaarang ini mencakup dimensi yang cukup besar, baik ditinjau dari segi jumlah sarana maupun dari segi jangkauan geografis pembangunannya. Dalam rangka mencapai keberhasilan pembangunan tersebut, perlu adanya rancangan yang menyeluruh sebagai pedoman atau acuan teknik bagi perencanaan pembangunan dan operasi jaringan nasional.
Namun dalam pemenuhan sarana komunikasi tersebut banyak terhambat oleh keterbatasan jaringan kabel yang menjadi prioritas pembangaunan jaringan saat ini. Keterbatasan ini sering disebabkan oleh keadaan lingkungan dan letak geografis suatu daerah yang mengakibatkan penarikan kabel membutuhkan biaya yang tidak sedikit dan waktu yang lama. Kondisi suatu kota dengan tingkat kepadatan penduduk, bangunan, dan jalan-jalan raya serta keadaan berupa hutan, lautan, pegunungan dan sebagainya merupakan kendala utama dalam pemasangan kabel yang berkaitan dengan instansi yang terkait dan biaya pemasangan yang mahal.
Referensi :
en.wikipedia.org/wiki/Spanning_tree_protocol
nic.unud.ac.id/…/A17%20SPANNING%20TREE%20PROTOKOL%20_802.pdf
www.sysneta.com/spanning-tree-protocol

Teknik Sorting Dan Teknik Searching

A. Teknik Sorting (Pengurutan Data)
Dalam struktur data, teknik sorting ini sangat diperlukan untuk suatu kegiatan. Teknik ini tentunya punya kriteria tersendiri. Ada dua macam cara pengurutan data, yaitu descending order(pengurutan data dari nilai tertinggi ke nilai terendah), dan ascending order (teknik pengurutan data dari nilai terkecil ke nilai terendah). Sebenarnya jika kita ingin mengimplementasikan teknik sorting ini ke dalam suatu bahasa pemograman, yang paling penting adalah, kita terlebih dahulu harus memahami konsep dari teknik Sorting itu sendiri. berikut caranya:

Untuk sorting yang paling sederhana ialah:
anggaplah kita punya nilai yaitu:
nilai [1]=15;
nilai [2]= 9;

Disini kita ingin mengurutkan dengan menggunakan teknik Ascending(pengurutan dari nilai terkecil ke nilai terendah).
Tentunya kita ingin menukar kedua angka itu yaitu
nilai[1]=9;dan
nilai[2]=15
Kita tidak bisa melakukannya dengan cara seperti ini.

nilai[1]=nilai[2]
nilai[2]=nilai[1] yakinlah, kalau seperti ini program tak akan bekerja.
Jadi,,
Pemahaman langkah pertama yaitu dengan cara nilai yang tersimpan pada "nilai[1]" akan dihapus, dan kemudian diganti dengan nilai yang tersimpan pada "nilai[2]". Sehingga sekarang antara "nilai[1] dan nilai[2]" punya nilai yang sama.OOpppsss, tapi apa yang terjadi dengan nilai[1]????? Jawabannya, ia telah tiada.

Nah, dalam penukaran dua variabel, kita harus mendefinisikan variabel ke-tiga, yaitu sebuah temporary yang memegang nilai variabel agar nilai tersebut tidak hilang.Ia akan menjaga proses penukaran nilai agar salah satu nilai tidak hilang.

Misalnya:
//Pertukaran Variabel
temp = nilai[1]; //pemegang variabel agar tidak hilang"temp"
nilai[1] = nilai[2];
nilai[2] = temp;

Proses penukaran ini akan berhasil dilakukan sesuai pemahaman teknik sorting. Pertukaran berhasil dilakukan tanpa nilai yang hilang [1]

Metode teknik sorting ada beberapa jenis:
- Pengurutan berdasarkan perbandingan (comparison-based sorting)
• Bubble sort, exchange sort
- Pengurutan berdasarkan prioritas (priority queue sorting method)
• Selection sort, heap sort
- Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep
sorted method)
• Insertion sort, tree sort
- Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer
method)
• Quick sort, merge sort
- Pengurutan berkurang menurun (diminishing increment sort method)
• Shell sort

B. Teknik 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.

Jenis-jenis teknik searching ada dua cara yakni pencarian secara linear
(sequential search) dan pencarian biner (binary search).

1. 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.
2. 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/