Linked List (Senarai Berantai)

Pengertian Linked List

Linked list adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian Linked list juga merupakan suatu cara untuk menyimpan data dengan struktur sehingga dapat secara otomatis menciptakan suatu tempat baru untuk menyimpan data yangdiperlukan. Struktur ini lebih dinamis karena banyaknya elemen dengan mudah ditambah atau dikurangi, berbeda dengan array yang ukurannya tetap. berikut gambaran kecil mengenai linked list.

Jenis Linked List

       1. Linked List Circular

Double Linked List 
       Pengertian secara umumnya DLLC itu Linked list yang menggunakan pointer, dimana setiap node memiliki 3 field, yaitu:
1 field pointer yang menunjuk pointer berikutnya "next",
1 field menunjuk pointer sebelumnya " prev ", 
1 field yang berisi data untuk node tersebut .

Double Linked List Circular pointer next dan prev nya menunjuk kedirinya sendiri secara circular. Bentuk Node DLLC

• Single Linked List    

             Single Linked List Circular (SLLC) adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya

  

         2. Linked List Non Circular

Double Linked List Non Circular (DLLNC)

             adalah Double Linked List yang memiliki 2 buah pointer yaitu pointernext dan prev.
Pointer next menunjuk pada node setelahnya dan pointer prev menunjuk pada node sebelumnya.

Pengertian: 
Double : artinya field pointer-nya dua buah dan dua arah, ke node sebelum dan sesudahnya.
Linked List : artinya node-node tersebut saling terhubung satu sama lain.
Non Circular : artinya pointer prev dan next-nya akan menunjuk pada NULL. 

Single Linked List Non Circular (SLLNC)

             Adalah Linked List yang pointer nya selalu mengarah ke Node yang menampung *next bernilai NULL, jadi arahnya tidak menunjuk pointer didepannya sehingga tidak dapat kembali ke pointer - pointer sebelumnya. SLLNC ini juga memiliki 2 bagian, ada Tambah dan ada Hapus, masing - masing bagian ini juga masih meliputi 3 fungsi lain yaitu Belakang, Tengah, dan depan. untuk Contoh Tambah & Hapus 

Operasi pada Linked List

  Insert = Istilah  Insert berarti menambahkan  sebuah  simpul baru ke dalam  suatu linked  list.

  Konstruktor = Fungsi ini membuat sebuah  linked  list yang baru dan masih kosong. 

  IsEmpty = Fungsi ini menentukan apakah  linked list kosong atau  tidak.

  Find First = Fungsi ini mencari elemen pert ama dari linked  list 

  Find Next = Fungsi ini mencari elemen  sesudah elemen yang ditunjuk now. 

  Retrieve = Fungsi  ini  mengambil  elemen  yang  ditunjuk  oleh  now.

                       Elemen  tersebut  lalu dikembalikan oleh fungsi. 

  Update = Fungsi ini mengubah elemen yang ditunjuk oleh  now dengan  isi dari  sesuatu. 

           Delete Now = Fungsi  ini  menghapus  elemen  yang  ditunj uk  oleh  now.  J ika  yang  dihapus  adalah elemen pertama dari  linked  list (head), head akan berpindah ke elemen berikut.

Contoh Program Algoritma pada Linked List

#include
#include
struct dataMahasiswa {
char nim[11];
char nama[31];
float ipk;
} mahasiswa;
struct dataMahasiswa mhsTheologi;
void main()
{
strcpy( mahasiswa.nim, “0244500016” );
strcpy( mahasiswa.nama, “Chotimatul” );
mahasiswa.ipk = 3.123;
mhsTheologi = mahasiswa;
printf(“Cetak isi struct mahasiswa”);
printf(“\nNim mahasiswa : %s”,mahasiswa.nim);
printf(“\nNama mahasiswa : %s”,mahasiswa.nama);
printf(“\nIPK mahasiswa : %f”,mahasiswa.ipk);
}

Sumber:

-http://soalparna.blogspot.co.id/2014/10/pengertian-macam-macam-dan-     penggunaan.html

 -http://temanbukuku.blogspot.co.id/2016/01/operasi-operasi-dasar-single-dan-double.html

- http://bagusnugraha.blogspot.co.id/2009/06/linked-list.html

Soal Struktur Data

1. Seorang programmer yang baik harus mengetahui cara pembuatan program yang bagus. Berikan penjelasan tentang program yang bagus itu seperti apa!

JAWAB :

Program yang bagus maupun baik adalah program yang mudah penggunaannya dan bisa memudahkan penggunanya untuk menyelesaikan masalah – masalah yang dihadapinya. Dalam membuat program yang baik seperti ini, seorang programmer tidak hanya membutuhkan keahlian untuk berkomunikasi dengan komputer saja, tetapi seorang programmer juga harus bisa berkomunikasi dan mendefinisikan masalah yang sedang dihadapi oleh kliennya, sehingga program tersebut bisa berfungsi dengan baik dan sesuai dengan permintaan kliennya. Setelah tahap pendefinisian masalah selesai, yang harus dilakukan oleh programmer selanjutnya adalah melakukan perencanaan tentang program yang akan dibuat. Apabila masalah yang telah didefinisikan tidak sesuai dengan bidang yang dikuasai oleh sang programmer, maka proses perencanaan tidak akan berjalan lancar. Karena itu, usahakan untuk bekerja sama dengan seseorang yang menguasai bidang dari permasalahan tersebut, sehingga perencanaan program bisa lebih mudah dan terstruktur. Bentuk rencana ini bisa dituangkan kedalam bentuk flowchart ataupun pseudo code. Setelah rencana berhasil dibuat, implementasikan rencana ini dalam sebuah source code, yang nantinya akan dijalankan. Disini keahlian dalam melakukan coding cukup penting, supaya bisa menghemat tenaga dan waktu. Setelah program berhasil dibuat, lakukan dokumentasi bila perlu. Dokumentasi berfungsi untuk programmer di masa depan apabila code – code dalam program tersebut ingin disisipkan ke dalam program yang baru, programmer tersebut tidak perlu susah – susah mencari atau membuat lagi. Dalam tahap akhir, lakukan testing terhadap program secara teliti, dan apabila ditemukan bug atau error, segeralah untuk menyelesaikannya.

2. Struktur data merupakan suatu cara untuk menyimpan dan mengatur sebuah data supaya dapat digunakan secara efektif dan efisien. Sebutkan dan jelaskan jenis-jenis struktur data secara umum.

JAWAB :

1. Struktur Data Sederhana
   1. Array(Larik)
      Larik adalah struktur data statik yang menyimpan sekumpulan elemen yang bertipe sama. Setiap elemen diakses langsung melalui indeksnya. Indeks larik harus tipe data yang menyatakan keterurutan misalnya integer atau karakter. Banyaknya elemen larik harus sudah diketahui sebelum program dieksekusi. Tipe elemen larik dapat berupa tipe sederhana, tipe terstruktur, atau tipe larik lain. Nama lain array adalah Larik, tabel, atau vektor
   2. Record(Catatan)
      ADT adalah definisi tipe dan sekumpulan primitif (operasi dasar) terhadap tipe tersebut. Tipe diterjemahkan menjadi tipe terdefinisi dalam bahasa pemrograman yang bersangkutan.
2. Struktur Data Majemuk
   1. Linier
      1. Stack(Tumpukan)
         Stack (tumpukan) adalah list linier yang dikenali elemen puncaknya (top), aturan penyisipan dan penghapusan elemennya tertentu (penyisipan selalu dilakukan “di atas” (top), penghapusan selalu dilakukan pada top). Karena aturan penyisipan dan penghapusan semacam itu, topadalah satu-satunya alamat tempat terjadi operasi. Elemen yang ditambahkan paling akhir akan menjadi elemen yang akan dihapus. Dikatakan bahwa elemen stack akan tersusun secara LIFO (Last In First Out).

1. 1. 1. Queue(Antrian)
         Queue (antrian) adalah list linier yang dikenali elemen pertama (head) dan elemen terakhirnya (tail); Aturan penyisipan dan penghapusan elemennya disefinisikan sebagai penyisipan selalu dilakukan setelah elemen terakhir, penghapusan selalu dilakukan pada elemen pertama; Satu elemen dengan elemen lain dapat diakses melalui informasi next.
      2. List dan Multi-List (Daftar)
         List linier adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari 2 bagian. sebuah list linier dikenali dengan (1) elemen pertamanya, biasanya melalui alamat elemen pertama yang disebut (first); (2) Alamat elemen berikutnya (suksesor), jika kita mengetahui alamat sebuah elemen, yang dapat diakses melalui field next; (3) Setiap elemen mempunyai alamat, yaitu tempat elemen disimpan dapat diacu. Untuk mengacu sebuah elemen, alamat harus terdefinisi. Dengan alamat tersebut informasi yang tersimpan pada elemen list dapat diakses; (4) Elemen terakhirnya.
   2. Non-Linier
      1. Binary Tree (Pohon Biner)
         Sebuah pohon biner (binary tree) adalah himpunan terbatas yang mungkin kosong atau terdiri dari sebuah simpul yang disebut sebagai akar dan dua buah himpunan lain yang disjoint yang merupakan pohon biner yang disebut sebagai sub pohon kiri (left) dan sub pohon kanan (right) dari pohon biner tersebut. Pohon biner merupakan tipe yang sangat penting dari struktur data dan banyak dijumpai dalam berbagai terapan. Karakteristik yang dimiliki oleh pohon biner adalah bahwa setiap simpul paling banyak hanya memiliki dua buah anak, dan mungkin tidak punya anak. Istilah-istilah yang digunakan sama dengan istilah pada pohon secara umum.
      2. Graph (Graf)
         Graph merupakan struktur data yang paling umum. Jika struktur linier memungkinkan pendefinisian keterhubungan sekuensial antara entitas data, struktur data tree memungkinkan pendefinisian keterhubungan hirarkis, maka struktur graph memungkinkan pendefinisian keterhubungan tak terbatas antara entitas data.

3. Jelaskan beberapa aplikasi perangkat lunak komputer yang menggunakan struktur data sebagai dasar pengembangannya.

JAWAB :

Antrian pada kasir pada sebuah bank.

Ketika seorang pelanggan datang, akan menuju ke belakang dari antrian. Setiap pelanggan dilayani, antrian yang berada didepan akan maju. Jika kita ada di antrian kedua, maka kita akan menunggu antrian pertama melakukan prosesnya. Ketika selesai proses dari antrian pertama dia akan pergi, dan giliran kita untuk maju untuk melakukan proses. Begitu juga arti dari antrian dalam bahasan kali ini, jika pengantri pertama datang maka dia juga yang akan keluar pertama kali atau FIFO(First In First Out) dan FCFS (First Come First Serve).

Pembelian tiket kereta api, tiket pesa1at, tiket kapal laut, pembayaran tiket tol, pembayaran listrik, pembayaran air, dan lain sebagainya. 

Saat mengantri di loket untuk membeli tiket. Istilah yang cukup sering dipakaiseseorang masuk dalam sebuah antrian adalah DeQueue. Dalam suatu antrian, yang datang terlebih dahulu akan dilayani lebih dahulu. Istilah yang sering dipakai bila seseorang keluar dari antrian adalah deQueue.

Antrian Mobil di pintu Tol.

Ketika sebuah mobil datang, dari belakang akan menuju kedepandari antrian. Setelah mobil mendapatkan karcis tol, antrian yang berada didepan akan maju. Pada saat menempatkan data pada ujung (tail) dari queue disebut dengan Enqueue. Pada saat memindahkan data dari kepala(head) sebuah queue disebut dengan dequeue.

4. Abstract Data Type (ADT) merupakan cara untuk melihat struktur data, dengan fokus pada apa yang dilakukan dan mengabaikan proses yang terdapat didalamnya saat menjalankan eksekusi. Buatlah algoritma yang menganalogikan abstraksi perangkat elektronik.

JAWAB :

Program Tiket_Di_Bioskop

Algoritma:

          type tiketBioskop: < nama_film : string,

                                                         kode_film : string,

                                                         jadwal_film : string,

                                                         harga_tiket : string,

                                                         quota : integer >

          T : array [1..4] of tiketBioskop

          type datapembeli: < nama_pembeli : string,

                                                         kode_pembelian : string >

          D : array [1..9999] datapembeli

          jumlah_pembeli : integer

          pilihan : integer;

          procedure lihatBioskop()

          procedure beliTiket()

          function  buatKodePembelian( T : tiketBioskop) -> string

5. Berikan penjelasan dan bandingkan beberapa pendekatan yang dapat digunakan untuk merancang sebuah algoritma.

JAWAB :

Terdapat dua pendekatan secara umum yang bisa digunakan dalam merancang algoritma, yakni pendekatan secara Top-Down, dan pendekatan secara Bottom-up

Top-Down

pendekatan perancangan secara top-down dimulai dengan cara membagi algoritma yang kompleks menjadi satu atau lebih dari satu modul. Modul yang terbagi ini masih bisa diuraikan lagi menjadi beberapa sub-modal, dan proses ini dilakukan berulang-ulang hingga kompleksitas modul yang diinginkan terpenuhi. Metode perancangan top-down merupakan bentuk perbaikan secara bertahap yang dimulai dengan modul paling atas kemudian secara bertahap menambah modul lain yang dipanggil.

Bottom-up

pendekatan perancangan bottom-up merupakan kebalikan dari pendekatan top-down. Dimana dalam pendekatan ini dimulai dengan pembuatan modul paling dasar, kemudian dilanjutkan ke perancangan modul tingkat yang lebih tinggi. Modul yang memiliki tinggkat lebih tinggi diimplementasikan menggunakan operasi yang dilakukan ikeh modul tingkat lebih rendah. Dengan demikian sub-modul pada pendekatan ini dikelompokkan secara bersama untuk membentuk tingkat modul yang lebih tinggi. Semua modul tingkat yang lebih tinggi  dikumpulkan bersama-sama untuk membentuk modul tingkat yang lebih tinggi. Proses ini diulang hingga desain algoritma yang lengkap terpenuhi.

6. Sebuah program dapat memiliki lebih satu algoritma. Rancang algoritma untuk program kalkulator yang dapat melakukan operasi penjumlahan dan pengurangan.

JAWAB :

   x,y       : integer

   hasil     : real

operator        : char
begin
Input(x)
Input(operator)
Input(y)

if operator = ‘+’ {jika operator adalah +}
then
hasil ← x+y
else
if operator = ‘-‘ {jika operator adalah -}
then
hasil ← x-y
endif
endif
{menampilkan penginputan oleh user}
Output(x,operator,y)
{menampilkan hasil penghitungan}
Output(hasil)

7. Ukurlah kompleksitas algoritma yang Anda rancang menggunakan notasi Big O!

JAWAB :

            input : x, y dan operator

            if  operator = ‘+’  then

               hasil ← x+y

            else

              operator = ‘-‘ then

              hasil ← x-y

            endif

            //output : nilai hasiln

endfunction

Referensi :

https://www.dictio.id/t/bagaimana-cara-membuat-program-yang-baik/12809/2

http://www.academia.edu/26340400/MAKALAH_STRUKTUR_DATA_Aplikasi_Struktur_Data_Queue_Semester_2

https://bayubayyz.blogspot.co.id/2014/03/program-kalkulator-sederhana.html

http://danangdprasetyo.blogspot.co.id/2013/02/contoh-algoritma-adt-tugas-kelompok.html

Pengertian Struktur Data dan Jenisnya

Struktur data adalah suatu koleksi atau kelompok data yang dapat dikarakterisasikan oleh organisasi serta operasi yang didefinisikan terhadapnya.

Data dapat dikategorikan menjadi :

1. Type data sederhana, terdiri atas :
   1. Data sederhana tunggal, misal : Integer, Real, Boolean & Karakter
   2. Data sederhana majemuk, misal : string

(tipe data ini diorganisasikan menjadi berbagai struktur data)

1. Struktur Data, terdiri atas :
   1. Struktur data sederhana, misal : Array & record
   2. Struktur data majemuk, terdiri atas :

–         Linier, misal : Stack, Queque & linear linked list

–         Non linier, misal : Binary tree

Kategori tersebut digunakan pada storage utama. Sedangkan untuk storage tambahan, struktur data dikenal sebagai organisasi file.

Organisasi file terdiri dari :

1. Organisasi Sequential,
2. Organisasi Relative
3. Organisasi Indexed Sequential
4. Organisasi Multikey

Dua buah struktur data sederhana adalah array atau larik dan record atau rekaman.

–      Array adalah struktur data yang terurut dan homogen, terdiri dari item yang sama typenya.

–      Record adalah Struktur data yang boleh terdiri atas keterangan dari berbagai type data.

1. 1. TIPE DATA SEDERHANA

Suatu jenis data tertentu akan disimpan didalam variabel yang sesuai jenisnya. Jenis variabel menentukan rangkaian nilai yang dibutuhkan sewaktu program dilaksanakan.

1. a. Bilangan Integer

Integer adalah Bilangan bulat yang tidak mengandung pecahan dan biasanya disajikan dalam memori komputer sebagai angka bulat.

Dalam aritmatika komputer integer disajikan dengan rumus :

N <= 2^n-1 – 1

n merupakan jumlah bit didalam memori yang bersangkutan.

Ada 5 tipe data yang termasuk dalam kelompok ini antara lain :

Tipe	Batas Nilai	Ukuran dlm Byte
Byte	0…255	1
Shortint	-128…127	1
Integer	-32768…32767	2
Word	0…65535	2
Longint	-2147483648…2147483647	4

Tipe data juga menentukan macam operasi yang bisa dilaksanakan. Operator – operator yang bisa dikerjakan dengan integer antara lain :

Operator	Kegunaan
+	Penjumlahan
–	Pengurangan
*	Perkalian
Div	Pembagian
Mod	Sisa Pembagian

Pada operator Div, operasi pembagian dengan pemenggalan, hal ini berarti bagian pecahan akan hilang.

Contoh :

3 div 4 = 0 seharusnya 0,75

1. b. Bilangan Real

Bilangan Real adalah Bilangan numerik yang terdiri dari bilangan Pecahan dan bilangan Tak rasional. Jenis data rela ditulis menggunakan titik atau koma desimal.

Bilangan real disimpan ke dalam memori komputer memakai sistem Floating Point Merupakan versi yang disebut notasi ilmiah atau Scientific notation.

Penyajian data terdiri atas dua bagian : mantissa (pecahan) dan index yang disebut eksponen atau karakter yang menetapkan tempat dari titik radix terhadap digit tersebut.

Secara umum bilangan real (X) memiliki rumus :

X = M * R ^E

Dimana M dijadikan pecahan, R adalah radixnya dan E merupakan eksponennya.

Dua kesukaran yang mungkin timbul di dalam aritmatika bilangan real ialah :

1. Pembatalan dua bilangan dekat tetapi tidak sama, dari tanda yang berlawanan sebagai hasil dari suatu penambahan (disebut kehilangan arti)
2. Kelebihan bilangan karena proses pembagian diakibatkan oleh bilangan pembagi yang kecil.

Ada 5 macam data yang terdapat dalam bilangan real antara lain :

Tipe	Batasan Nilai	Digit	Ukuran dlm byte
Real	2.9 x 10-39…1.7 x 1038	11 – 12	6
Single	1.5 x 10-45…3.4 x 1038	7 – 8	4
Double	5.0 x 10-324…1.7 x 10308	15 – 16	8
Extended	1.9 x 10-4951…1.1 x 104932	19 – 20	10
Comp	-263 + 1 … 263 – 1	19 – 20	8

Operator yang bisa dioperasikan pada tipe data real adalah :

Operator	Kegunaan
+	Penjumlahan
–	Pengurangan
*	Perkalian
/	Pembagian

1. c. Boolean

Suatu variabel boolean atau logikal hanya dapat berisikan nilai true dan false, yang kerap kali dinyatakan pula sebagai 1 dan 0. Oleh karena itu sebuah satuan data dapat cukup berisi satu bit saja.

Beberapa macam tipe data boolean antara lain :

Tipe	Range	Ukuran dalam byte
Boolean	Byte-sized	1 (8 bit)
ByteBool	Byte-sized	1 (8 bit)
WordBool	Word-sized	2 (16 bit)
LongBool	LongInt-sized	4 (32 bit)

Operator yang digunakan pada tipe data Boolean adalah Operator Relasional. Operator Relasional tersebut antara lain :

Operator	Kegunaan
=	Sama Dengan
<	Lebih Kecil dari
>	Lebih Besar dari
<=	Lebih Kecil atau sama dengan
>=	Lebih besar atau sama dengan
<>	Tidak sama dengan

1. d. Karakter

Karakter adalah tipe data yang didefinisikan merupakan himpunan karakter yang dikenal komputer dan biasanya tersaji dalam tabel ASCII.

Karakter yang dikenal dalam komputer biasanya mencakup :

1. 26 Huruf Besar Latin
2. 26 Huruf Kecil Latin
3. 10 Digit Arab
4. Karakter Khusus ( aritmatika, tanda baca, dll )
5. Ruang Kosong atau Blank
6. Karakter Pengendali

Tipe data Karakter hanya dapat menampung satu karakter saja dan mengalokasikan satu byte memori.

Default dari variabel yang dideklarasikan dalam tipe data karakter adalah 256 kecuali ditentukan terlebih dahulu

Contoh :

Var

Kalimat        : String;

Nama           : String[25]

Alamat         : String[30]

Operasi yang berlaku terhadap string / karakter antara lain :

1. Len (String)

Adalah Operasi untuk menghitung length atau panjang String.

1. Concat(S₁, S₂)

Adalah Operasi Concatenation atau penyambungan 2 buah string

1. SubStr(S, i, j )

Adalah Operasi untuk membuat suatu string baru dengan cara mengambil beberapa karakter berurutan dari suatu string yang diketahui.

Dimana S = String, i = Mulai Pengambilan string, j = Jumlah string yang diambil

1. Insert(S₁, S₂, j)

Adalah Operasi yang menyisipkan string S₂, Di dalam String S₁.

Sedemikian sehingga karakter pertama dari S₂ mengantikan posisi karakter ke j dari S₁, Selesai dengan seluruh karakter string S₂ dilanjutkan lagi dengan sisa string S_1.

1. Delete(S, i, j)

Adalah Operasi yang berfungsi untuk menghapus substring yang panjangnya j, bermula dari posisi ke i dari S

Referensi : https://aghygp.wordpress.com/2010/02/19/struktur-data/