TULISAN TENTANG PERKEMBANGAN KOMPUTER SEKARANG INI DAN PENERAPANNYA DI BIDANG ELEKTRONIK.

Perkembangan Komputer dan Penerapan di Bidang Elektronika

SEJARAH PERKEMBANGAN KOMPUTER

beberapa waktu yang lalu, proses pengolahan data telah dilakukan oleh manusia. Manusia juga menemukan alat-alat mekanik dan elektronik untuk membantu manusia dalam penghitungan dan pengolahan data supaya bisa mendapatkan hasil lebih cepat. Komputer yang kita temui saat ini adalah suatu evolusi panjang dari penemuan-penemuan manusia sejah dahulu kala berupa alat mekanik maupun elektronik. Saat ini komputer dan piranti pendukungnya telah masuk dalam setiap aspek kehidupan dan pekerjaan.

Komputer yang ada sekarang memiliki kemampuan yang lebih dari sekedar perhitungan matematik biasa. Diantaranya adalah sistem komputer di kassa supermarket yang mampu membaca kode barang belanjaan, sentral telepon yang menangani jutaan panggilan dan komunikasi, jaringan komputer dan internet yang mennghubungkan berbagai tempat di dunia.Bagaimanapun juga alat pengolah data dari sejak jaman purba sampai saat ini bisa kita golongkan ke dalam 4 golongan besar :

1. Peralatan manual: yaitu peralatan pengolahan data yang sangat sederhana,
dan faktor terpenting dalam pemakaian alat adalah menggunakan tenaga
tangan manusia.

2. Peralatan Mekanik: yaitu peralatan yang sudah berbentuk mekanik yang
digerakkan dengan tangan secara manual.

3. Peralatan Mekanik Elektronik: Peralatan mekanik yang digerakkan secara
otomatis oleh motor elektronik.

4. Peralatan Elektronik: Peralatan yang bekerjanya secara elektronik penuh
Tulisan ini akan memberikan gambaran tentang sejarah komputer dari masa ke
masa, terutama alat pengolah data.

Pendekatan ini didasarkan pada hasil kerja George Boole (1815-1864) berupa sistem biner aljabar, yang menyatakan bahwa setiap persamaan matematik dapat dinyatakan sebagai benar atau salah. Dengan mengaplikasikan kondisi benar-salah ke dalam sirkuit listrik dalam bentuk terhubung-terputus, Atanasoff dan Berry membuat komputer elektrik pertama di tahun 1940. Namun proyek mereka terhenti karena kehilangan sumber pendanaan.

Untuk mencapai keadaan komputer seperti saat ini, ternyata diperlukan proses yang sangat amat panjang. Berikut perkembangan komputer dari generasi ke generasi :

GENERASI PERTAMA

Perkembangan komputer generasi pertama umumnya dirancang untuk mengerjakan suatu tugas spesifik tertentu dimana hal ini dicirikan dengan adanya program kode-biner yang sangat berbeda. Hal ini membuat sistem kerja generasi komputer pertama sangat dibatasi.

GENERASI KEDUA

Perkembangan Komputer Generasi Kedua, ditandai dengan penemuan transistor pada tahun 1948, menggantikan fungsi tube vakum dalam televisi, radio, dan komputer. Secara resmi transistor digunakan pada komputer sejak 1956, dan sangat mempengaruhi ukuran komputer. Pengecilan ukuran komputer semakin dipercepat dengan pengembangan memori inti magnetik.

GENERASI KETIGA
Perkembangan Komputer Generasi Ketiga, dengan ditemukannya IC (Intergrated Circuit) pada 1958, disebabkan sistem kerja transistor yang menghasilkan panas sangat besar sehingga merusak komponen yang lainnya. IC terbuat dari batu quarsa yang ditemukan oleh seorang ilmuwan ahli instrument dari Texas, Jack Kilby. Penemuan penting selanjutnya, sebuah chip dapat mewakili beberapa komponen yang dibutuhkan oleh komputer. Akibatnya, komputer terlihat lebih bersahabat dan nyaman ketka digunakan, karena ukurannya yang semakin mengecil.

GENERASI KEEMPAT
Perkembangan Komputer Generasi Keempat, ditandai dengan ditemukannya Large Scale Integration (LSI), yang memuat ratusan komponen dalam hanya sebuah chip. Pada 1980 ditemukan produk turunannya yaitu 1980-an, Very Large Scale Integration (VLSI) yang memiliki kemampuan luar biasa untuk dapat memuat ribuan komponen hanya dalam sebuah chip tunggal.

Dan mungkin Ultra-Large Scale Integration (ULSI) yang memiliki kemampuan yang lebih luar biasa untuk dapat meningkatkan jumlah tersebut menjadi jutaan.

Contoh produk dipasaran adalah Chip Intel 4004 yang dibuat pada pertengahan tahun 1971. Inilah awal komputer dibuat dan disain untuk keperluan komersial yang terjangkau untuk semua pihak.

GENERASI KELIMA
Perkembangan Komputer Generasi Kelima (Komputer Masa Depan), nyatanya masih sebatas imajinasi, seperti film berjudul 2001:Space Odyssey karya Arthur C. Clarke. Dalam film tersebut, komputer dapat diprogram sehingga dapat mendekati pemikiran manusia, bahkan mampu memprogram dirinya sendiri sehingga bisa mengalahkan pemikiran manusia.

Meskipun gambaran visual yang ditayangkan dalam komputer tersebut masih jauh dari pemikiran kita dan realita, namun tanda-tanda untuk mewujudkan itu semua sudah terlihat. Sejauh ini telah ada komputer yang dapat diprogram untuk dapat merespon perintah secara lisan maupun nalar manusia.

Dewasa ini banyak kemajuan teknologi untuk mendukung perkembangan komputer, seperti ditemukannya kemampuan pemrosesan paralel yang direncanakan mengganti model non Neumann, dimana sistem pemrosesan paralel itu akan mampu bekerja mengkoordinasikan banyak CPU untuk secara serempak.

Ditemukan pula teknologi superkonduktor, yang menghantarkan informasi lebih cepat. Bagaimanapun, secanggih apapun kemampun komputer, maka tidak akan bisa mengalahkan kemampuan yang membuatnya, yaitu pikiran manusia.

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

http://mayorpelangi.blogspot.com/2011/03/perkembangan-komputer-dan-penerapan-di.html

makalah tentang spanning tree dan penerapannya di dalam kehidupan sehari2 terutama pada bidang teknik elektro.

Pengertian

Spanning Tree Protocol atau yang sering disingkat dengan STP adalah link layer networ protocol yang menjamin tidak adanya loop dalam topologi dari banyak bridge/switch dalam LAN. STP ini berdasarkan pada sebuah algoritma yang ditemukan oleh Radia Perlman sewaktu bekerja untuk Digital Equipment Corporation. Dalam model OSI untuk jaringan komputer, STP ada di layer 2 OSI. Spanning tree memperbolehkan desain jaringan memiliki redundan links untuk membuat jalur backup otomatis jika sebuah link aktif gagal bekerja, tanpa adanya bahaya dari loop pada bridge/switch. Loop pada bridge/switch akan menghasilkan flooding pada network.

Spanning Tree Protocol (STP) merupakan bagian dari standar 802.1 IEEE yang dinginakan untuk kontrol media akses.  suatu Layer 2 protokol yang berjalan pada bridge dan switch. Spesifikasi untuk STP adalah 802.1d IEEE. Tujuan utama dari STP adalah untuk memastikan bahwa Anda tidak membuat loop bila Anda memiliki jalan berlebihan di jaringan anda. Loop yang mematikan ke jaringan. Ini juga berfungsi sebagai protocol untuk pengaturan koneksi dengan menggunakan algoritma Spanning tree. Spanning Tree Protokol (802.1d). Spanning Tree (802.1d) merupakan sebuah protokol yang berada di jaringan switch yang memungkinkan semua perangkat untuk berkomunikasi antara satu sama lain agar dapat mendeteksi dan mengelola redundant link dalam jaringan.

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.

Secara garis besar, Spanning Tree Protocol bekerja dengan cara :

• 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.

• 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.

• 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

www.cisco.com/univercd/cc/td/doc/…/stpapp.htm – Amerika Serikat

http://wartawarga.gunadarma.ac.id/2011/03/188087//

tulisan tentang teknik sorting dan searching

Teknik Sorting dan Teknik Searching

1.  Sorting
Dalam penyelesaian suatu masalah pasti terdapat banyak cara atau solusi-solusi yang dapat dilakukan, seperti halnya pembuatan program memiliki banyak tehnik atau algoritma yang dapat di gunakan salah satunya untuk kebutuhan SORTING atau PENGURUTAN kumpulan data-data. terdapat 4 algoritma atau tehnik dalam melakukan sorting.

• Straight 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) bila lebih kecil daripada index berikutnya (index 1 dengan index 2, index 1 dengan index 3, ….. index 1 dengan index terakhi) maka kita lakukan pertukaran nilai pada array index tersebut. proses ini dilakukan terus menerus sampai pada pengecekan index terakhir – 1 dengan nidex terakhir.

• 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.

• 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 – 1.

• Modified 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 dikurangi 1 atau sampai program tidak melakukan pertukaran. jadi waktu untuk melakukan proses sorting lebih cepat.

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 contoh 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.
Demikian juga dengan bentuk ini :
nilai[1]=nilai[2]
nilai[2]=nilai[1], kalau seperti ini program tak akan bekerja.
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. Tapi yang terjadi dengan nilai[1] adalah nilai tersebut telah hilang. 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 pembarteran 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 pertukaran ini akan berhasil dilakukan sesuai pemahaman teknik sorting, dan pertukaran berhasil dilakukan tanpa nilai yang hilang.
2. Searching
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.

• Line Search. 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.

• Binnary Search. teknik ini hanya dapat digunakan hanya pada kumpulan data yang sudah di urutkan, karena teknik ini melakukan pencarian dengan mencari data pada index yang tengah, apakah lebih besar/lebih kecil/sama dengan. bila hasil sama dengan maka nilai yang di cari telah di temukan. bila lebih kecil/lebih besar maka akan di buang setengah data dari yang salah, dan mencari dari indeks yang tengah dari sisanya. demikian samapi data ditemukan atau tidak di temukan.

• Fibonachi Search. 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.
• http://andikafisma.wordpress.com/teknik-sorting-dan-teknik-searching/

TULISAN TENTANG LINKED LIST

Linked list

Jadi di dalam memori komputer, dia kesimpannya berurutan addressnya…, jadi buat untuk mencari data ke i, kita tinggal maen tunjuk aja datanya ada dimana dan kita bakal langsung dengan instan mendapatkan data tersebut… Jadi kompleksitas pencariannya itu O[1]  atau bisa dibilang tinggal nunjuk.

Nah sekarang kita ke linked list…
Ini mungkin ada yang pernah denger tapi masih banyak belum tahu ini apa dan untuk apaan…
Bisa dibilang linked list fungsinya sama kayak array, tapi ada yang berbeda dalam penyetoran datanya…
Linked list ini datanya gak dijadiin satu barisan data gitu, melainkan kayak gini…
Misalkan tiap elemen yang ada di simpen linked list itu kita namakan node, maka di dalam node tersebut mempunyai beberapa properties, yaitu :

1. data, yaitu data sebenernya yang disimpan
2. prev, yaitu menunjuk ke node sebelumnya
3. next, yaitu menunjuk ke node selanjutnya

Jadi bisa dibayangkan kalau data itu berurutan dan ada link yang menghubungkan mereka itu…
Memori tempat tiap – tiap node itu bisa nggak berurutan… tapi mereka selalu merefer ke node selanjutnya dan node sebelumnya…
Nah disini ada masalah jika kita pengen mengakses data ke i.
Jadi bayangkan kita pengen nyari suatu alamat ke i, kita hanya tahu alamat yang pertama dari suatu rumah, nah kita berkunjung ke rumah itu nanya alamat selanjutnya dimana, terus kita ikutin lagi seterusnya sampe i kali baru ketemu rumah yang kita cari.
Berbeda dengan array, jika kita pengen ngakses alamat ke i, kita tinggal liat rumah urutan ke i dari rumah pertama dan langsung nyampe / bisa dibilang tinggal tunjuk.
Nah jadi untuk mengakses suatu elemen ke i dalam linked list itu diperlukan kompleksitas O[N], jadi misalkan datanya ada 100, kemungkinan paling buruk pas kita ngakses data ke 100, kita musti ngecek dari awal sampe 100, jadi ada 100 kali pengecekan, jadi gak bisa langsung tunjuk.
Representasi Linked list ini seperti ini… [sori programmer art XD]

Nah mungkin kalo gitu buat apa ada linked list?
Nah disini linked list ini dibuat dengan tujuan tertentu… yaitu dia bisa dengan cepat menghapus atau menyelipkan suatu data ke tengah – tengah list.
Mungkin ada yang nanya, array juga bisa kan? Nah di array menghapus data atau menyelipkan data di tengah itu sungguhlah lambat.
Jadi kira2 kalau di linked list itu pas menyelipkan [insertion] data di tengah itu prosesnya kayak gini… [misalkan data yang ingin kita selipkan itu [b] diantara suatu node [a] dengan node selanjutnya ]

c = a.next;

a.next = b;

b.prev = a;

b.next = c;

c.prev = b;

Make sense?
Jadi bisa dibilang a.next kita ganti menjadi b [yang sebelumnya adalah c], dan b.prev kita ganti menjadi a [karena a akan menjadi node sebelum b], b.next ganti menjadi c [karena node sesudahnya adalah c], dan c.prev kita ganti menjadi b [yang sebelumnya adalah a].
Dan selesai sudah kita menyelibkannya, dan operasinya gak ribet2 amat…
Nah… kalau menghapusnya juga mirip2, misalkan node yang pengen kita hapus adalah b, dan node sebelumnya adalah a dan node sesudahnya adalah c.

a = b.prev;

c = b.next;

b.prev = null; // optional

b.next = null; // optional

a.next = c;

c.prev = a;

Nah… sebenernya kodenya dah jelas maksudnya apaan.
Jadi kita pertama2 mengosongkan b.prev dan b.next karena dia bakal keluar dari list, jadi next sama prev nya kosong [gak usah seh sebenernya juga gak apa2 ... tapi kayaknya lebih memudahkan GC kayaknya :p].
Terus a.next jadi c [yang sebelumnya b], dan c.prev jadi a [yang sebelumnya b].
Jadi kompleksitasnya? Kompleksitasnya adalah O[1] kalau kita udah nyediain node a pas kita mau nyelipin nodenya, kalau kita hanya bilang selipin node b setelah node ke – i, artinya dia musti nyari dulu kan? Jadi bakalan O[N], tapi biasanya jarang orang mau bilang selipin setelah node ke – i, biasanya langsung tau dia mau diselipin disebelah node mana.
Representasi selip2an di linked list [ini bukan saya yang buat ==a... minjem dari polygonal] [tarik node ke atas atau ke bawah buat deleting, pencet "i" buat nambahin node]
 http://lab.polygonal.de/wp-content/swf/ds/LinkedListBuilder.swf


Sekarang balik lagi ke array… aku bilang sebelumnya selip2an dan hapus2an di array lambet kan? Iya lambet banget ==a…
jadi bayangin gini…
kamu punya kotak berjejer gitu…
ada sepuluh bolah dari kotak pertama sampe kotak ke sepuluh [masing2 satu bola gitu], bolanya beda2
nah kamu pengen masukin satu bola ke urutan setelah bola ke 6 artinya posisi ke 7…
gimana kamu melakukannya? Jeng Jeng Jeng…
Kamu harus ambil bola ke sepuluh, pindahin kesebelahnya yang masih kosong (kotak ke 11), trus karena tempat ke sepuluh dah kosong, kamu bakalan ambil bola ke sembilan, pindahin ke kotak sepuluh, begitu seterusnya sampe kotak ke tujuh itu kosong kan? baru di taro di kotak itu…
Nah mending kalo kita naruh bolanya diujung2 akhir apalagi pas disamping yang paling terakhir, kita tinggal taro gak usah ngegeser satu2…
Nah masalahnya kalo kita mau taro datanya dipaling depan, kita musti ngegeser semua data yang ada satu2 sejumlah banyak datanya, iya kalo hanya 10 cepet mah, kalo datanya dah 1 jeti an? ==a…
Hal yang sama berlaku pas kita mau ngapus suatu data, pas kita hapus suatu data, artinya data yang urutannya ada di selanjutnya data itu musti digeser buat ngisi tempet kosong itu kan?
Sama ribetnya,  jadi kompleksitas buat selip2an dan ngapusin itu O[N]…
Representasinya gini [ini dari polygonal juga] [geser data ke atas buat ngapusinnya]
 http://lab.polygonal.de/wp-content/swf/ds/ArrayExample.swf

Nah mungkin anda bertanya2… gimana caranya kita mengiterasi [artinya ngakses satu2 dari data pertama sampe data terakhir]suatu linked list?
Kalo array may ya kalo indeksnya nambah2 terus gak masalah karena kita nyari datanya itu tinggal tunjuk.
Nah kalo linked list, iya kalo i nya masih angka 1, misalnya dah ujung2 dia masa nyari lagi, nyari lagi dengan kompleksitas O[N]?
Bakal sangat lambet kan?
Terus gimana kita nge-iterasiin, kalo pake array kan gampang tinggal kayak gini

for(var i:int = 0; i<n; i++) // disini pake indeks awal array = 0

{

  trace(a[i]); // kompleksitasnya O(1)

}

Kompleksitas iterasi array O[N] [karena ngulangin sebanyak N kali kompleksitas yang O[1] jadi dikaliin jadi O[N]]
nah kalo linked list? Cara kasarnya seh gini… dan sangat lambat

for(var i:int = 0; i<n; i++)

{

  trace(a.at(i)); // kompleksitas O(N)

}

Jadi bisa dibilang pas i = 0, ngeceknya cuman sekali, kalo i = 1, ngeceknya dua kali [ditotal sama yang sebelumnya jadi 3 kali], seterusnya bakal nambah2 terus jadi sangat lambat karena banyak yang musti di cari. Kompleksitasnya mendekati O[N^2] [karena ngulang sebanyak N kali kompleksitas yang O[N] jadi dikali aja gitu]
Jadi linked list gak bagus dunk? Ya kalau implementasinya salah ==a… biasanya orang ngeiterasinya kayak gini… [ada banyak cara seh... pake yang enak aja]
Dengan for

for(var i:Node = a.head; i != null; i = i.next) // i bakalan null kalau sudah setelah node terakhir, karena node terakhir next nya berisi null

{

  trace(i.data);

}

Dengan while

var i:Node = a.head;

while(i != null)

{

  trace(i.data);

  i = i.next;

}

Pakailah dengan sesuai selera masing2… dengan begini kompleksitasnya jadi O[N].
Nah mungkin ada yang nanya2 apa itu a.head?
Yang tadi ada prev sama next nya itu baru suatu node…
Nah suatu linked list itu mempunyai property sebagai berikut

• head : yaitu node awal suatu linked list [head.prev pasti null, karena sebelumnya dah gak ada apa - apa lagi]
• tail : sama kayak head, tapi menunjukkan di bagian akhirnya [tail.next pasti null]
• size : untuk keep track jumlah yang ada di dalam linked list ada berapa [optional seh]
• push_back : untuk nambahin data di akhir linked list [jadi langsung pake tail nya]
• pop_back : untuk ngapus data di akhir linked list [jadi langsung tail nya diapus]
• push_front : untuk nambahin data di awal linked list [jadi langsung pake head nya]
• pop_front : untuk ngapus data di awal linked list [jadi langsung head nya diapus]
• append : nyelipin ke index sesudah i, O[N]
• prepend : nyelipin ke index sebelum i, O[N]
• delete : hapus node index i O[N]

Nah untuk append atau prepend dari node yang udah diketahui yang O[1], fungsinya lebih enak kalau ada langsung di Node nya
jadi yang node ditambah ini :

• ll : buat nunjukin dia ini ada di linked list mana [optional seh, gak terlalu penting]
• append : nyelipin sesudah index ini O[1]
• prepend : nyelipin sebelum index ini O[1]
• delete : hapus node ini O[1]

Sebagai tambahan… linked list ada 2 macem… yang pertama singly linked list, linked list ini hanya punya next nodenya gak ada prev… dan doubly linked list, ini punya next dan prev [yang doubly ini yang dibahas daritadi karena ini paling sering dipake].

Jadi kita sampe pada suatu kesimpulan disini…
Array :

• Pros :
• Akses ke suatu index i cepet O[1]
• Implementasinya gak belibet
• Iterasinya gak belibet
• Untuk implementasi sorting [pengurutan data] lebih gak belibet.
• Cons :
• Insertion sama Deletion itu lama O[N], hanya cepet kalo deket2 ujung akhir
• Usage :
• Kalau kita mau nyimpen data yang fixed gitu posisinya, hampir gak pernah ditambah di tengah atau ngapus di tengah2, apalagi nambah sama ngapus di awal [shift sama unshift], kalau ngepush sama ngepop seh masih boleh karena gak usah maen geser2an lagi.
• Untuk nyimpen data yang kita sering maen tunjuk index ke berapa untuk mendapatkan datanya…

Linked List :

• Pros :
• Insertion sama Deletion sangat cepat O[1]
• Cons :
• Akses ke suatu index i lambat O[N]
• Implementasinya agak belibet [karena biasanya bukan standard library, jadi musti dibuat dulu]
• Iterasinya lumayan belibet [karena penulisannya jarang dijumpai]
• Untuk implementasi sorting kayaknya lumayan belibet [belom pernah nyoba]
• Usage :
• Untuk kalau kita mo nyimpen data, yang sering diselip2in dan dihapus2in, kita nggak peduli data ke i itu apa, karena biasanya kalau kita mau ngakses, kita langsung ngeiterasi semuanya. Misalnya kayak display list, kita jarang pengen tahu display list urutan ke i itu apa ya? Kita pasti cuman pengen nambahin dan ngapusin objek yang misalnya dah ke destroy. Atau biasanya kita cuman pengen kalau objek ini ada di atas objek yang lainnya. Trus kita lebih sering gak ngakses satu2 tapi langsung diiterasiin, misalnya untuk ngerender… kita langsung iterasiin semuanya tanpa membeda2kan. Jadi bisa dibilang kita buta sama apa isinya, yang penting isinya itu saling berhubungan.

http://blog.gamedevid.org/?p=194