Pelajaran 3 dalam bahasa Pemrograman Go

Hai Guys... gimana nih kabar kalian? Baik-baik saja kan.
Kali ini saya mau sharing tentang Linked List

Apa itu Linked List?
Linked list merupakan struktur data yang terdiri dari node record/value dan reference (link atau pointer), yang bersambung satu sama lain membentuk urutan/rangkaian.

Ternyata Linked List banyak macamnya lho...

● Singly linked list, yaitu linked list yang hanya memiliki 1 link yang menunjuk ke node berikutnya
(next). Elemen pertama dari linked list disebut head, sedangkan elemen terakhir dari linked list disebut tail.


Nah, kalau kita lihat dari gambar di atas ternyata dia hanya bisa 1 arah saja.


Nah, kalau gambar di atas yaitu cara menambahkan node yang baru dari rangkaian linked list yang sudah ada.


Nah kalau yang ini delete node yang ada.

Nah, setelah kita mengetahui konsep cara menambah dan membuang suatu node, maka saya akan menunjukkan codenya.

package main
 
import "fmt"
 
type Ele struct {
    Data interface{}
    Next *Ele
}
 
func (e *Ele) insert(data interface{}) {
    if e == nil {
        panic("attept to modify nil")
    }
    e.Next = &Ele{data, e.Next}
}
 
func (e *Ele) printList() {
    if e == nil {
        fmt.Println(nil)
        return
    }
    fmt.Printf("(%v", e.Data)
    for {
        e = e.Next
        if e == nil {
            fmt.Println(")")
            return
        }
        fmt.Print(" ", e.Data)
    }
}
 
func main() {
    h := &Ele{"A", &Ele{"B", nil}}
    h.printList()
    h.insert("C")
    h.printList()
}

(A B)
(A C B)

● Doubly linked list, yaitu linked list yang memiliki 2 link yang menunjuk ke node sebelum dan sesudahnya (prev dan next)


Untuk cara membuang dan menambah, konsepnya hampir sama dengan yang singly linked list.
Berikut contoh codenya.

package main
 
import "fmt"
 
type dlNode struct {
    string
    next, prev *dlNode
}
 
type dlList struct {
    head, tail *dlNode
}
 
func (list *dlList) String() string {
    if list.head == nil {
        return fmt.Sprint(list.head)
    }
    r := "[" + list.head.string
    for p := list.head.next; p != nil; p = p.next {
        r += " " + p.string
    }
    return r + "]"
}
 
func (list *dlList) insertTail(node *dlNode) {
    if list.tail == nil {
        list.head = node
    } else {
        list.tail.next = node
    }
    node.next = nil
    node.prev = list.tail
    list.tail = node
}
 
func (list *dlList) insertAfter(existing, insert *dlNode) {
    insert.prev = existing
    insert.next = existing.next
    existing.next.prev = insert
    existing.next = insert
    if existing == list.tail {
        list.tail = insert
    }
}
 
func main() {
    dll := &dlList{}
    fmt.Println(dll)
    a := &dlNode{string: "A"}
    dll.insertTail(a)
    dll.insertTail(&dlNode{string: "B"})
    fmt.Println(dll)
    dll.insertAfter(a, &dlNode{string: "C"})
    fmt.Println(dll)
 
    // traverse from end to beginning
    fmt.Print("From tail:")
    for p := dll.tail; p != nil; p = p.prev {
        fmt.Print(" ", p.string)
    }
    fmt.Println("")
}

<nil>
[A B]
[A C B]
From tail: B C A

● Circular linked list, yaitu linked list yang ekornya (tail) menunjuk ke elemen pertama (head).
Untuk jenis yang tidak circular disebut dengan linear linked list. Circular linked list dapat berupa
doubly linked list, yaitu ketika head juga menunjuk ke tail.

Self-organizing List

Self­organizing list adalah linked list yang memindahkan data yang sering diakses ke bagian awal dari list. List ini memiliki berbagai metode:

● MTF atau move­to­front, yaitu memindahkan node yang baru saja diakses sebagai head



● Count method, yaitu dengan mengurutkan node sesuai berapa banyak node tersebut diakses, dan diurutkannya dari yang paling besar ke yang paling kecil.



● Transpose method, yaitu dengan menukar dengan node di depannya tiapkali node tersebut
diakses



Mungkin itu saja yang bisa saya share kan pada kali ini.

Sumber:
http://commoninterview.com/images/Single_Linked_List.jpg,
http://upload.wikimedia.org/wikipedia/commons/thumb/4/4b/CPT-LinkedLists-addingnode.svg/474px-CPT-LinkedLists-addingnode.svg.png,
http://www.nczonline.net/blog/wp-content/uploads/2009/04/Singly_linked_list_delete_after.png
http://rosettacode.org/wiki/Singly-linked_list/Element_insertion#Go
https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiWW_zZmx_cXfa-Fq-QkXW8pvLSXuxOusz8aP-x1KuiK48FVOTjC8YurCfue3L3bD0661C1DHNCebdN_VZAxgzfTulFHYE0YQAwdt8LtolMMQ1daFQua20O0GNHxqbvB7U8yb8GQMgMzSO1/s1600/doublylist.gif
http://rosettacode.org/wiki/Doubly-linked_list/Traversal#Go
http://www.geeksforgeeks.org/wp-content/uploads/cll1.gif
http://upload.wikimedia.org/wikipedia/commons/0/08/MTF_Algorithm.png
http://upload.wikimedia.org/wikipedia/commons/thumb/a/aa/CountAlgorithm.png/330px-CountAlgorithm.png
http://en.wikipedia.org/wiki/Self-organizing_list#mediaviewer/File:Transpose_Algorithm.png
Materi Dosen