Algoritma Struktur Data - Single Linked List

Algoritma dan Struktur Data

Single Linked List

Oleh

Nama          : Gusnia Syukriyawati

NIM            : 115090607111036

Program Teknologi Informasi dan Ilmu Komputer

Universitas Brawijaya

Malang

2012

BAB I

Pendahuluan

I.1 Dasar Teori

Array merupakan variable yang bersifat statis (ukuran dan urutannya sudah pasti). Selain itu, ruang memori yang dipakai olehnya tidak dapat dihapus bila array tersebut sudah tidak digunakan lagi pada saat program dijalankan. Untuk memecahkan masalah di atas, dengan menggunakan variabel pointer. Tipe data pointer bersifat dinamis, variabel akan dialokasikan hanya pada saat dibutuhkan dan sesudah tidak dibutuhkan dapat direlokasikan kembali. Setiap ingin menambahkan data, selalu menggunakan variabel pointer yang baru, akibatnya akan membutuhkan banyak sekali pointer. Oleh karena itu, ada baiknya jika hanya menggunakan satu variabel pointer saja untuk menyimpan banyak data dengan metode yang disebut Linked List.

Linked list adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang
setiap elemennya terdiri dari dua bagian. 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. Perhatikan ilustrasi berikut untuk lebih jelasnya.

Masing-masing komponen disebut sebagai simpul atau node. Setiap simpul 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.

Inti dari linked list adalah proses (tambah, edit, hapus) dari gerbong / node dan bagaimana menyambungkan antar gerbong / node tersebut.

ARRAY VS LINKED LIST

PEMBUATAN SINGLE LINKED LIST

- Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data bertipe integer dan field next yang bertipe pointer dari Tnode

 - Setelah pembuatan struct, buat variabel haed yang bertipe pointer dari Tnode yang berguna sebagai kepala linked list.

Pembentukan node baru

Digunakan keyword new yang berarti mempersiapkan sebuah node baru berserta alokasi
memorinya, kemudian node tersebut diisi data dan pointer nextnya ditunjuk ke NULL

SINGLE LINKED LIST MENGGUNAKAN HEAD

- Dibutuhkan satu buah variabel pointer: head

- Head akan selalu menunjuk pada node pertama

Deklarasi Pointer Penunjuk Kepala Single Linked List. Manipulasi linked list tidak bisa dilakukan langsung ke node yang dituju, melainkan harus menggunakan suatu pointer penunjuk ke node pertama dalam linked list (dalam hal ini adalah head).

Function untuk mengetahui kosong tidaknya Single LinkedList.  Jika pointer head tidak menunjuk pada suatu node maka kosong

PENAMBAHAN DATA

Penambahan data di depan

Penambahan node baru akan dikaitan di node paling depan, namun pada saat
pertama kali (data masih kosong), maka penambahan data dilakukan dengan cara head ditunjukkan ke node baru tersebut. Pada prinsipnya adalah mengkaitkan node baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan 

ilustrasi:

 

MENAMPILKAN DATA 

Function untuk menampilkan isi single linked list (non circular)

- Function di atas digunakan untuk menampilkan semua isi list, di mana linked list ditelusuri satu-persatu dari awal node sampai akhir node. 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.

PENGHAPUSAN DATA

Function untuk menghapus data terdepan

Function di atas akan menghapus data teratas (pertama) yang ditunjuk oleh head pada linked list

- Penghapusan  node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penggunakan suatu pointer lain yang digunakan untuk menunjuk node yang akan dihapus, misalnya pointer hapus dan barulah kemudian menghapus pointer hapus dengan menggunakan perintah delete.

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

- Jika head masih NULL maka berarti data masih kosong.

BAB II

Pembahasan

II.1 Source Code

package Prak4;

class Node {

      int data;

      Node next;

}

public class SingleLinkedList {

      private Node pointer;

     

      //constructor LL

      public SingleLinkedList(){

            pointer = null;

      }

      //membuat suatu node baru

      public void buatNode(int dt){

            Node nodeBaru = new Node();

            nodeBaru.data = dt;

            nodeBaru.next = pointer;

            pointer = nodeBaru;

      }

      public void SisipAwal(int data){

        Node baru = new Node();

        baru.data=data;

        baru.next=pointer;

        pointer=baru;

      }

     

      public void SisipAkhir (int data){

            Node pSblAkhir, pAkhir;

            pSblAkhir = null;

            pAkhir = pointer;

            Node baru = new Node();

            baru.data = data;

            baru.next = null;

            while (pAkhir != null){

                  pSblAkhir = pAkhir;

                  pAkhir = pAkhir.next;

            }

            pSblAkhir.next = baru;

      }

     

      public void insertAtIndex(int data, int index) {

          if (index == 0) {

              SisipAwal(data);

          }

          else {

              Node cari = pointer;

              Node a = new Node();

              a.data = data;

              Node temp = pointer;

              int n = 0;

              while (n < index) {

                  temp = cari;

                  cari = cari.next;

                  n++;

              }

             a.next = cari;

             temp.next = a;

          }

      }

     

     

      //secara normal data di hapus di depan

      public int HapusDepan (){

            Node hapus = pointer;

            pointer = pointer.next;

            return hapus.data;

      }

      public void HapusAkhir(){

            Node hapus = pointer;

            int a = 0;

            while (hapus != null){

                  hapus = hapus.next;

                  a ++;

            }

            hapus = pointer;

            for (int i = 1; i < a - 1; i++){

                  hapus=hapus.next;

            }

            hapus.next=null;

      }

      public void cetak (String kom){

            System.out.println(kom);

            Node n = pointer;

            while (n != null){

                  System.out.print(n.data + " -> ");

                  n = n.next;

            }

            System.out.println("....");

      }

     

      public static void main (String [] args){

            SingleLinkedList l = new SingleLinkedList();

            l.buatNode(4);

            l.buatNode(9);

            l.buatNode(9);

            l.buatNode(1);

            l.buatNode(8);

            l.buatNode(0);

            l.buatNode(4);

            l.buatNode(2);

            l.cetak("l : LL Asal");

           

            l.SisipAwal(8);

            l.cetak("\nl : LL sisip Data di awal : ");

           

            l.SisipAkhir(7);

            l.cetak("\nl : LL sisip Data di akhir : ");

           

            l.insertAtIndex(3, 3);

          l.cetak("\nl : Linkedlist setelah disisipi angka 3 pada index ke-3 :");

         

          l.HapusDepan();

            l.cetak("\nl : LL setelah dihapus di depan: ");

           

          l.HapusAkhir();

          l.cetak("\nl : LL setelah dihapus di akhir: ");

      }

}

II.2 Output