Linked List

 Sejarah Link List

Dikembangkan tahun 1955-1956 oleh Allen Newell, Cliff Shaw dan Herbert Simon di RAND Corporation sebagai struktur data utama untuk bahasa Information Processing Language (IPL). IPL dibuat untuk mengembangkan program artificial intelligence. List ini merupakan sebuah pemikiran/konsep struktur data yang sangat dasar pada pemrograman agar lebih fleksibel. Setiap elemen akan ditambahkan saat dibutuhkan, tidak dialokasikan dengan tempat tertentu dari awal.

Pengertian

Merupakan sekumpulan elemen list yang bertipe sama. Elemen list mempunyai keterurutan tertentu, nilai satu elemen boleh muncul lebih dari satu kali.  Setiap elemen mempunyai 2 bagian: Informasi elemen Alamat suksesornya. Linked List adalah salah satu bentuk struktur data, berisi kumpulan data (node) yang tersusun secara sekuensial, saling sambung-menyambung dan dinamis. Linked List saling terhubung dengan bantuan variabel pointer. Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis.Setiap node terdiri atas dua bagian. Bagian pertama berisi informasi data tersebut,  Bagian kedua merupakan  field,  link, atau  nextpointer. Link inilah yang menghubungkan satu elemen data ke elemen data lainnya, sehingga urutan elemen data tersebut membentuk suatu  linear list. Untuk FIeld nya sendiri ini berisi alamat dari simpul berikutnya dalam  list. Field link bernilai 0 bila  link tersebut tidak menuding ke data (simpul) lainnya.  Penuding  ini  disebut  penuding nol.

Contoh :

Misalnya kita ingin membuat sebuah elemen data nilai mahasiswa yang terdiri dari NRP, nama, dan nilai, maka representasinya adalah sebagai berikut:

 

Bila elemen seperti diatas dibuat dalam bahasa algoritma maka jadinya akan seperti berikut:
    type nilaiMatKul : <
        NRP : string,
        nama : string,
        nilai : string,
    >
Elemen ditambah dengan pengait/penunjuk:
    type elemen : <
        elmt : nilaiMatKul,
        next : elemen
    >  

Deklarasi listnya sebagai berikut:
    type list : <
        first : elemen
    >

Penunjuk elemen di awal ini (first) digunakan untuk memegang elemen awal sebuah list agar dapat diakses satu per satu sampai elemen terakhir list. Sebuah struktur data yang dianggap sebagai list memiliki aturan pengaksesan. Pengaksesan dilakukan dari penunjuk elemen pertama (first) kemudian berjalan maju ke elemen kedua, ketiga dan seterusnya sampai elemen terakhir.

Perbedaan Karakteristik Array dan Link List

Konsep Pointer dan link list

Untuk mengolah data yang banyaknya tidak bisa ditentukan sebelumnya, maka disediakan satu fasilitas yang memungkinan untuk menggunakan suatu peubah yang disebut dengan peubah dinamis (Dinamic variable) Peubah Dinamis (Dinamic variable) ini  Suatu peubah yang akan  dialokasikan hanya pada saat diperlukan, yaitu setelah program dieksekusi.

Perbedaan Peubah Statis dan Dinamis

Pada perubah statis, isi Memory pada lokasi tertentu (nilai perubah) adalah data sesungguhnya yang akan diolah. Pada perubah dinamis, nilai perubah adalah alamat lokasi lain yang menyimpan data sesungguhnya. Dengan demikian data yang sesungguhnya dapat dimasukkan secara langsung. Dalam hal cara pemasukkan data dapat diilustrasikan seperti dibawah ini 

 Deklarasi Pointer

Pointer digunakan sebagai penunjuk ke suatu alamat memori Dalam pemrograman C++, Type Data Pointer dideklarasikan dengan bentuk umum :

Type Data * Nama Variabel;

Type Data dapat berupa sembarang type data, misalnya char, int atau float. Sedangkan Nama veriabel merupakan nama variabel pointer

Keuntungan List

  1. Penggunaan memori yang dinamik.
  2. Kita dapat mengatur penggunaan memori sehingga bisa lebih hemat.
  3. Kesederhaan pada proses insert dan delete elemen
  4. Alamat elemen pertama dari suatu list, dapat diacu oleh First(L).
  5. Nilai yang dibawanya dapat diacu dengan info(P)
Jenis jenis Link List

  1. Single : artinya field pointer-nya hanya satu buah saja dan satu arah serta pada akhir node, pointernya menunjuk NULL

  2. Linked List : artinya node-node tersebut saling terhubung satu sama lain.


  • Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data.
  • Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.

Penyajian Link List pada Memory

Keterangan :

Sambungan[2]            = 2    , Maka     Info[2]                             = 'A'
Sambungan[6]            =  6   ,Maka    Info[6]                               = 'B'
Sambungan[1]]           = 1    ,Maka    Info[1]                               = 'C'
Sambungan[5]]           = 5    ,Maka    Info[5]                               = 'D'
Sambungan[10]]         = 10  ,Maka    Info[10]                             = 'E'
Sambungan[8]]           = 8    ,Maka    Info[8]                               = 'F'
Sambungan[0]]           = 0    ,Maka    Info[Akhir Linked List]
 
Dari Contoh diatas, diperoleh untai A,B,C,D,E,F 

Jenis Jenis Link List

  1. Single Link List dengan head

     2. Single Link List dengan Head dan Tail

Kelebihan dari Single Linked List dengan Head & Tail adalah pada penambahan data di belakang, hanya dibutuhkan tail yang mengikat node baru saja tanpa harus menggunakan perulangan pointer bantu.

Beberapa Operasi Pada List

  1. Membuat Element Linked List
    Membuat suatu elemen linked list berarti memesan tempat di memori untuk menyimpan sebuah list.

  2. Menghapus Element List

    • Menghapus elemen list berarti menghilangkan atau menghancurkan alokasi memori sebuah list yang telah ada di memori.

    • Fungsi: agar data yang tidak diperlukan benar-benar terhapus di memori  sehingga penggunaan memori dapat optimal karena data-data yang tidak diperlukan dihilangkan.

  3. Penambahan Element di posisi Awal.

    Penambahan elemen di posisi awal adalah menambahkan data baru pada posisi awal, sehingga data baru  tersebut akan menjadi awal. Ada 2 hal yang harus diperhatikan, yaitu :
    • kondisi linked list sedang kosong, atau

    • kondisi linked list sudah mempunyai elemen

  4. Konsisi Linked List Sedang Kosong.

     Ketika linked list masih kosong, maka variable awal dan akhir akan diisi dengan variable baru

 Ilustrasi Link List Masih Kosong :


 Ketika di Isi 10 

Kondisi Link list sudah punya element
Proses penambahannya adalah dengan mengisikan field next  milik elemen baru dengan posisi awal linked list, kemudian posisi awal berubah ke posisi baru.
 
Masukan data baru dari depan, Misal 15
 

Penambahan Element di posisi Akhir

Penambahan di posisi akhir adalah proses penambahan data baru dimana data baru disimpan di posisi terakhir. Setelah proses penambahan selesai, maka variable akhir akan menunjuk ke data  baru tersebut. Ada 2 hal yang harus diperhatikan yaitu :

  1. Kondisi penambahan akhir pada linked list yang masih kosong dan
  2. Kondisi penambahan akhir pada linked list yang sudah mempunyai elemen.

Menampilkan Single Linked List dengan Head

Penelusuran ini dilakukan dengan menggunakan suatu pointer bantu, karena pada prinsipnya pointer head yang menjadi tanda awal list tidak boleh berubah/berganti posisi. Penelusuran dilakukan terus sampai node terakhir ditemukan menunjuk ke nilai NULL.  Jika tidak NULL, maka node bantu akan berpindah ke node selanjutnya dan membaca isi datanya dengan menggunakan field next sehingga dapat saling berkait. Jika head masih NULL berarti data masih kosong!.
Contoh langkah langkah Penelusuran adalah sebagai berikut :

  1. Isi variable p dengan awal.
  2. Selama p tidak NULL, maka tampilkan info yang ada di elemen yang ditunjuk variable p, kemudian p dipindahkan ke elemen berikutnya.

Penghapusan data Awal 

Penghapusan data di awal adalah proses menghapus elemen pertama (awal), sehingga variable awal akan berpindah ke elemen data berikutnya.  Ada 3 kondisi yang perlu diperhatikan yaitu:

  1. kondisi linked list masih kosong
    Pada kondisi ini proses penghapusan tidak bisa dilakukan.
  2. kondisi linked list hanya memiliki 1 data.
    Langkah yang dilakukan adalah menghapus data yang ada di posisi awal kemudian akhir dan awal di-NULL-kan.
  3. kondisi linked  list yang memiliki data lebih dari 1 elemen.
    • Alamat data awal diisikan ke suatu variabel pembantu (phapus).
    • Setelah itu pindahkan awal ke data berikutnya.
    • Setelah itu hapus/hancurkan data di posisi pehapus

Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer. Sebelum data terdepan dihapus, head harus ditunjukkan ke node sesudahnya terlebih dahulu agar list tidak putus, sehingga node setelah head lama akan menjadi head baru (data terdepan yang baru).

Penghapusan Data Akhir

Penghapusan data akhir adalah proses menghilangkan/menghapus data yang ada di posisi terakhir.
Ada 3 kondisi yang harus diperhatikan ketika akan melakukan proses penghapusan data akhir yaitu:
  1. Kondisi linked list masih kosong,
  2. Kondisi linked list hanya berisi 1 data, dan 
  3. Kondisi linked list berisi data lebih dari 1 buah.

 Menghapus data dari belakang
  1. Membutuhkan pointer bantu dan hapus.
  2. Pointer hapus digunakan untuk menunjuk node yang akan dihapus, dan pointer bantu digunakan untuk menunjuk node sebelum node yang dihapus yang kemudian selanjutnya akan menjadi node terakhir.
  3. Pointer bantu akan digunakan untuk menunjuk ke nilai NULL.
  4. Pointer bantu akan selalu bergerak sampai sebelum node yang akan dihapus, baru kemudian
  5. pointer hapus diletakkan setelah pointer bantu.  Setelah itu pointer hapus akan dihapus, pointer bantu akan menunjuk ke NULL.
  6. Dibutuhkan dua buah variabel pointer: head dan tail 
  7. Head akan selalu menunjuk pada node pertama, sedangkan tail akan selalu menunjuk pada node terakhir.