Rabu, 16 November 2011

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.

Tidak ada komentar:

Posting Komentar