Struktur Data

Kembali ke => Kumpulan mata kuliah Teknik Informatika

STRUKTUR DATA

Suatu cara menyajikan Abstract Data Type (ADT) / Tipe Data Abstrak dalam bentuk tipe data dan operator yang didukung bahasa pemograman

Struktur Data (SD) digunakan untuk : (1) menyajikan model Matematika dalam format tipe data abstrak (ADT) yang mengoleksi sejumlah variable, (2) beberapa type data yang mungkin berbeda, dan (3) hubungan diantaranya dengan berbagai langkah algoritama.

Pemilihan SD yang tepat dapat meningkatkan efektivitas dan efisiensi dari sebuah program

Abstract Data Type (ADT)

Adalah sebuah model matematika bersama-sama dengan bermacam operasi di definisikan dalam sebuah model.

Contoh ADT List operasi yang dibutuhkan dalam List : Newclr, dengan langkah-langkah sebagai berikut :

  1. Buatlah sebuah list kosong
  2. Ambil anggota pertama dari list dan kembalikan “NULL” jika list sudah kosong
  3. Ambil anggota list berikutnya dan kembalikan “NULL” jika tidak ada lagi anggota list berikutnya
  4. Masukan sebuat integer kedalam list

SD dapat digunakan untuk mengimpelementasikan ADT list diatas sehingga menjadi efisien & efektif, dengan langkah-langkah sebagai berikut :

  1. MAKE NULL (Newclr);
  2. W:=FIRST (Newclr);
  3. W:=NEXT (Newclr);
  4. Insert (V,Newclr);

Contoh ADT Graph

  1. Get the first uncolored vertex
  2. Test whether these is an edge between two vertex
  3. Make a vertex colored
  4. Get the next uncolored vertex

Contoh ADT Set :

  1. Buat set A kosong
  2. Lakukan Union antara set A dan set B, serta hasil variannya diberikan ke set C
  3. Tentukan setnya dengan A

Tipe data dari sebuah variable adalah sejumlah nilai yang bias diasumsikan pada variable tersebut.

Contoh :

Variabel dengan type Boolean, dapat diasumsikan menerima nilai “True”/”T” atau “False”/”F” tetapi tidak dengan nilai yang lain

Tipe data dalam Pascal :

  1. Tipe sederhana
    1. Tipe ordinal                                                Ukuran                                 Batasan nilai

­   Integer                                 16 bit / 2 byte                    – 32768 s/d 32767

­   Short Int                              8 bit / 1 byte                       – 128 s/d 127

­   Logint                                    32 bit                                     – 2147483648 s/d 2147483647

­   Boolean                               1 bit                                       – True atau False

­   Char                                       8 bit                                       – 0 s/d 255

­   Byte                                       8 bit                                       – 0 s/d 255

­   Word                                     16 bit                                     – 0 s/d 65535

­   Subrange

­   Enumerated

  1. Tipe Real                                      48 bit / 6 byte                    2.9E-39 s/d 1.738

­   Single                                    32 bit                                     1.5E-45 s/d 3.4E38

­   Double                                 64 bit                                     5.0E-324 s/d 1.7E308

­   Extended                            80 bit                                     1.9E-4951 s/d 1.1E493

­   Comp.                                   64 bit                                     -2E-63+1 s/d 2E63

  1. Type String                                         8 bit                                       1 s/d 255
  2. Type terstruktur 65.520 byte
    1. Array
    2. Record
    3. Set
    4. File
    5. Type pointer

Tipe data dasar dalam pemograman Java

No Tipe Ukuran Batasan Nilai
1 Boolean 1 bit True atau False
2 Char 16 bit Unicode character
3 Byte 8 bit -128 s/d 127
4 Short 16 bit -32768 s/d 32767
5 Int 32 bit -2147483648 s/d 2147483647
6 Long 64 bit -9223372036854775808 s/d 9223372036854775808
7 Float 32 bit 3.4E-38 s/d 3.4E38
8 Double 64 bit -1.7E308 s/d 1.7E308

Type data (primitip) yang digunakan oleh bahasa C

No

Satuan Type Data

Buku penulisan bahasa C

Jumlah byte yang diperlukan

Jangkauan nilai numerik

1 Character Char atau signed char

1

-128 s/d 127
Atau unsigned char

1

0 s/d 255
2 Integer Int atau singned Int

2

-32768 s/d 32767
Unsigned Int

2

0 s/d 65535
Long atau long int

4

-2147483648 s/d 2147483647
Unsigned long Int

4

0 s/d 4294967245
3 Floating pint Float

4

-3.4E-38 s/d 3.4E38
Single procession Float

4

-3.4E-38 s/d 3.4E38
4 Double procession Double

8

1.7E-38 s/d 1.7E38
Long Double

10

3.4E-4932 s/d 11.14932

Tipe data dalam bahasa C juga memiliki tipe data enumilasi, untuk membuat tipe data baru di bahasa C menggunakan keyword “typedef”, bentuk umum sebagai berikut :

Typedef<tipe data lama><tipe data baru>

Contoh :               Typedef int angka;

Typedef char huruf;

Struktur data sederhana adalah tipe struktur data yang mempunyai komponen matriks 100 (kolom) x 5 (baris) dan setiap komponen mempunyai tipe data yang sama.. Posisi masing-masing komponen dalam array dinyatakan sebagai nomor index. Bentuk umum dari deklarasi struktur data array dalam bahasa pemograman Pascal :

Contoh :               Type vek : array[1…100] of integer;

Type Tbl : array[1…100,1…5] of real;

Bentuk umum dari deklarasi struktur data array dalam bahasa C :

Int                          vek                                         [100];

(Tipe data)          (nama variable)                                (nomor index mulai 0 s/d 99)

Int                          tbl                                           [100][5]

Bentuk umum dari deklarasi struktur data array dalam bahasa Java :

Int [ ]     vek                         = now int [100]

Nama variable                   nomor index 0 s/d 99

Record (rekaman) adalah tipe data yang membuat kumpulan data yang komponennya dalam jumlah berbeda dan tipe data yang berbeda satu sama lainnya. Bentuk umum deklarasi record dalam bahasa Pascal :

Type siswa = record

Nama:string[25];

Alamat:string[40];

Kelamin:[L.P];

Kelas:1…6

End;

Bentuk umum deklarasi record dalam bahasa C dengan keyword “struct”

typedef struct siswa

{ char nama [25];

Char alamat [40];

Char kelamin [1];

Int kelas;

};

Bentuk umum deklarasi record dalam bahasa Java dengan keyword “class”

Class siswa

{string nama;

String alamat;

String kelamin;

Int kelas;

Siswa (string n.a.k.int 5)

{nama=n;alamat=a;kelamin=k;kelas=5}

}

Penggunaan struct siswa dalam bahasa C dengan membuat variable siswa1 & siswa2

Siswa siswa1;siswa2;

Penggunaan struct siswa dalam bahasa C dengan membuat variable array m

Siswa                                     m                                            [100]

Struktur data record       variable array

Aktivitas struktur data ada 2 yaitu :

  1. Mendeskripsikan kumpulan objek data yang sudah sesuai dengan tipe data yang ada
  2. Mewujudkan mekanisme kerja operasi-operasinya

Contoh : integer (-32768 s/d 32767), jenis operasi yang diperbolehkan adalah +,-,/,*, mod,call, floor,<,>,!,=,dsb.

Struktur data = objek data + [operasi manipulasi data}

Obyek data adalah kumpulan element yang mungkin untuk suatu tipe data tertentu

Hubungan struktur data dengan algoritma

Dengan pemilihan struktur data yang baik maka masalah yang kompleks dapat diselesaikan sehingga algoritma dapat digunakan secara efisien, operasi-operasi penting dapat dieksekusikan dengan sumber daya yang lebih kecil memory yang lebih kecil dan waktu eksekusi yang lebih cepat.

Ciri algoritma yang baik :

  1. Input : ada minimal 0 input/lebih
  2. Output :ada minimal 1 output/lebih
  3. Define : ada kejelasan apa yang dilakukan
  4. Efective : langkah yang dikerjakan harus efektif.

Terminate : langkah harus dapat berhenti (stop) secara jelas

Bahasa pemograman bisa memiliki tipe data

  1. Built in : sudah tersedia oleh bahasa pemograman tersebut tidak berorientasi pada persoalan yang dihadapi
  2. UDT (User Defined Type) dibuat oleh pembuat program (pemograman) mendekati penyelesaian yang dihadapi. Contoh : record pada pascal, struct pada C dan Class pada Java.
  3. ADT (Abstract Data Type), memperluas konsep UDT dengan menambahkan pengkapsulan/enkapulasi berisi sifat-sifat dan operasi-operasi yang bisa dilakukan terhadap kelas tersebut

Contoh : Class pada Java

Printif(“Data anda : In”)

Printif(“Nim :%In”,mhs.nim)

Printif(“Nama:%In”, mhs.nama)

Printif(“IPK :%fIn”, mhs,IPK)

getch();

}

//Program bahasa C

#include <studio.h>

#include<contoh.h>

Typedef               struct mahasiswa {

Char nim [10]

Char nama [25]

Float IPK

}

Void main ()

[mahasiswa mhs;

Clrscr();

Printf(“nim=”);scan f(“%5”,mhs.nim);

Printf(“nama=”;scan f(“%5”,mhs.nama);

Printf(“IPK=”);scan f(“%f”,mhs.ink);

STACK (Tumpukan)

Stack adalah jenis SD liniear sederhana. Stack adalah suatu daftar dimana seluruh pemasukan dan penghapusan dilakukan pada suatu ujung yang bernama puncak (TOP) tumpukan.

Prinsip/Konsep proses struktur data stack adalah LIFO (Last In First Out), yang terakhir masuk yang pertama keluar, atau yang pertama masuk yang terahir keluar.

PUSH : menambahkan/untuk siapa/masuk/tulis/insert satu item pada tumpukan

POP : memindahkan/untuk ambil/keluar/delete/baca/hapus dari tumpukan.

Contoh :

Bayangkan tumpukan baki/piring dikantin, selama jam makan pelanggan mengambil baki/piring dari puncak (top) tumpukan dan pegawai kantin mengembalikan baki/piring pada tumpukan baki/piring yang paling akhir diletakan dalam tumpukan adalah baki/piring yang pertama diambil. Baki/piring di dasar tumpukan adalah baki/piring yang paling awal diletakan dan paling akhir digunakan.

Pemakaian Stack (Tumpukan)

  1. Penyusunan tumpukan sub program (Procedure/Function). Procedure/Function/Sub Program A, B & C dimana A memanggil B dan B memanggil C

Procedure C {

Xxxxx

}

Procedure B {

Xxxxx

Call C

Xxxxx

}

Function A {

Xxxxx

Call A

Xxxxx

}

*/Program Utama

{

Xxxxx

D:=A

Xxxxx

}

  1. Membalikan urutan. Keuntungan struktur data stack dari pendekatan operasionalnya ada 3 yaitu :
    1. Flexibility of Implementation

Bila kita telah menggunakan struktur/fungsi maka hanya definisi tipe struktur dan pernyataan fungsi yang perlu dirubah

  1. Clarity of Program

Penampilan PUSH & POP akan mengingatkan pembaca program tentang apa yang sedang dikerjakan (di eksekusi)

  1. Top-Down Design

Memisahkan penggunaan struktur data dari penerapannya akan membantu kita mengembangkan rancangan Top Down baik struktur data maupun program

Contoh Ilustrasi Stack untuk penjumlahan berikut :

592

3784 +

4376

/*Prosedur Push*/

Procedure Push (Var T:Tumpakan;Var Penuh:Boolean;x:integer);

Begin

If T.Atas=MaxElemen then

{*Tumpukan sudah penuh*}

Penuh:=true

Else

Begin

Penuh:+False;

T.Atas:=inc(T.Atas);

T.Isi[T.Atas]:=x

End

End;

/*Prosedur Pop*/

Procedure POP (Var T:Tumpukan);

Begin

If T.Atas=0 then

Writeln(‘Tumpukan sudah kosong’);

Else

T.Atas:=T.Atas-1

End;

Contoh program Pascal untuk membalikan kalimat

Program Balik_Kalimat;

Uses crt;

const elemen=255; {batas maksimum karakter}

type s255=string[elemen];

tumpukan=record

isi:s255;

atas:0..elemen;

end;

var T:Tumpukan; {nama tumpukan}

I:Integer; {increment/pencacah}

kalimat:s255; {kalimat yang dibalik}

Procedure awalan(var t:tumpukan);

begin

T.Atas:=0;

end;

Procedure Push(var t:tumpukan;x:char);

begin

T.Atas:=T.Atas+1;

T.Isi[T.Atas]:=x

end;

Function POP (Var T:tumpukan):char;

begin

POP:=T.Isi[T.Atas];

T.Atas:=T.Atas-1

end;

{Program Utama}

Begin

clrscr;

awalan (T);

writeln(‘Tumpukan untuk membalik kalimat’);

writeln(‘——————————-‘);

writeln;

{Kalimat yang akan dibalik}

write(‘Isikan sembarang kalimat :’);

readln(kalimat);

clrscr;

writeln(‘Kalimat Asli :’);writeln(kalimat);

writeln;writeln(‘Setelah dibalik :’);

for I:=1 to length(kalimat) do

push(T,Kalimat[I]);

for I:=1 to length(kalimat) do

write(POP(T));

writeln;

end.

LINKED LIST

ARRAY : Struktur Data yang sangat membantu dalam pemograman, tetapi array memiliki 2 keterbatasan

  1. Mengubah ukuran array, harus membuat array baru dan meng-copy semua data dari array dengan ukuran lama ke array dengan ukuran baru. (penambahan/penghapusan data di array tidak mungkin dapat dilakukan, demikian pula menghapus array adalah tidak mungkin)
  2. Data dalam array merupakan berurutan (sequential) berikutnya ke setiap data yang lainnya didalam memory sehingga menyisipkan sebuat item ke dalam array membutuhkan pemindahan data lain dalam array ini (statis)

Keterbatasan ini dapat diatasi dengan menggunakan struktur data linked list

Sejarah linked list :

  1. Dikembangkan tahun 1955-1956 oleh Allen Newel, Cliff Shaw dan Herbert Simon di Rand Corporation, sebagai struktur data utama untuk bahasa information processing language (IPL). IPLS dibuat untuk mengembankan program artificial intelligence, seperti pembuatan chess solver.
  2. Victor Yngve di Massachussetts Institute of Technology (MIT) juga menggunakan Linked List pada natural language processing dan machine transitions pada bahasa pemograman commit.

Linked list adalah salah satu bentuk struktur data berisi kumpulan data (node) yang tersusun secara sekuensial, saling sambung menyambung, dinamis dan terbatas. Linked List disebut juga senarai berantai. Struktur Linked List adalah sejumlah node yang menyampaikan data dan menghubungkan (Links) ke node yang lain.

Node (simpul) dapat dialokasikan ke bebarapa tempat/lokasi di memory dan melewatkan (pass) dari node struktur linked list yang satu ke node yang lain dengan menyimpan refrensi ke node yang lainnya dalam struktur linked list.

Linked list saling terhubungkan dengan variable pointer. Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memory secara dinamis dan biasanya berupa struct (dalam bahasa C/C++) atau Record (dalam bahasa Pascal) atau Class (dalam bahasa Java) yang terdiri dari beberapa field. Bentuk umum node single linked list :

Menempati alamat memory tertentu

Ilustrasi single list dari bilangan bulat (integral)

Deklarasi Node dalam bahasa C :

Typedef stmct TNode {

Int data;

TNode * Next;

};

Keterangan :

–          Pembuatan STMCT bernama TNode yang berisi 2 field, yaitu field data bertipe integer dan field next yang bertipe pointer dari TNode

–          Setelah pembuatan struct, buat variable head yang bertipe pointer dari TNode yang berguna sebagai kepala Linked List.

Deklarasai node dalam bahasa Pascal :

Type perubah = ^simpul;

Simpul = record

Info : tipe;

Berikut : perubah

End;

Dimana perubah adalah nama variable yang bertipe pointer

Simpul : nama simpul (Node)

Info : nama medan dari data yang bisa bertipe sembarang

Tipe : tipe data masing-masing medan (bisa integer, float, dsb)

Berikut : nama medan yang bertipe data pointer

Penerapan Linked List dalam bahasa Java

//***SL Node Java***

//Deklarasi class node

Public Class SLLNode <T> next;

Public SLL Node () {

Next=null;

}

Public SLLNode (Tel) {

Info=el;next=null;

}

Public SLLNode (Tel,

SLLNode <T>ptr{

Info=el;next=ptr;

}

}

//***SLL.JAVA***

//Proses Linked List

Public Class SLL<T>{

Protected SLLNode<T>head, tail;

Public SLL(){

Head=tail=null;//deklarasi head&tail

}

Public Boolean is empty () {

Return head==null;

}

Public boid add To Head (Tel) {

Head=new SLLNode<T>(el,head);

If (tail==null)

Tail=head;//Tambah node dari depan

}

Public boid add To Tail (Tel) {

If (!isEmpty()) {

Tail.next=new SLLNode<T> (el);

Tail=tail.next; //tambah node dari belakang

}

Else head=tail=new SLLNode<T>(el);

}

Public T delete Form Head () {

If (IsEmpty())

Return null;

Tel=head.info;

If (head==fail)

Head=tail=null;

Else head=head.next;

Return el;

}

Public TdeleteFromTaill() }

If (IsEmpty ())

Return null;

Tel=tail.info;

If (head==tail)

Head=tail=null;

Else {

SLLNode<T>tmp;

For (tmp=head;temp.next!=fail;tmp=tmp.next);

Tail=tmp;

Tail.next=null;

}

Return el;

}

Public void delete(Tel){

If (!IsEmpty())

If (head==tail&&el==head.info)

Head=tail=null;

Else if (el==head.info)

Head=head.next;

Else {

SLLNode<T>pred,tmp;

For(pred=head,temp=head.next;tmp!null&&temp.info!=el;pred=pred.next,tmp=tmp.next);

If (tmp!=null) {

Pred.next=tmp.next;

If (tmp==tail)

Tail=pred

}

}

}

Public Boolean IslnList (Tel) {

SLLNode <T> tmp;

For (tmp=head;tmp!=null&&tmp.info!=el;tmp=tmp.next);

Return tmp!=null;

}

}

Double Linked List Non Circular

  • DLLNC adalah Double Linked List yang memiliki 2 buah pointer yaitu pointer next 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.

Ilustrasi DLLNC

  • Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya & ke node sebelumnya
  • Untuk pembentukan node baru, mulanya pointer next dan prev akan menunjuk ke nilai NULL.
  • Selanjutnya pointer prev akan menunjuk ke node sebelumnya, dan pointer next akan menunjuk ke node selanjutnya pada list.

Deklarasi dan node baru DLLNC

Deklarasi node

Dibuat dari struct berikut ini:

typedef struct TNode{

int data;

TNode *next;

Tnode *prev;

};

Pembentukan node baru

Digunakan keyword new yang berarti mempersiapkan sebuah node baru berserta alokasi memorinya.

  • TNode *baru;
  • baru = new TNode;
  • baru->data = databaru;
  • baru->next = NULL;
  • baru->prev = NULL;

DLLNC dengan HEAD

  • Dibutuhkan satu buah variabel pointer: head
  • Head akan selalu menunjuk pada node pertama

Deklarasi Pointer Penunjuk Kepala Double Linked List

  • Manipulasi linked list tidak bisa dilakukan langsung ke node yang dituju, melainkan harus melalui node pertama dalam linked list.  Deklarasinya sebagai berikut:
  • TNode *head;
  • Fungsi Inisialisasi Single LinkedList Circular
  • void init(){
    • head = NULL;
  • }

Function untuk mengetahui kosong tidaknya DLLNC

  • int isEmpty(){
  • if(head == NULL) return 1;
  • else return 0;
  • }

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 pada head nya.
  • Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan.  Untuk menghubungkan node terakhir dengan node terdepan dibutuhkan pointer bantu.

DLLNC menggunakan Head

  • void insertDepan(int databaru){
  • TNode *baru;
  • baru = new TNode;
  • baru->data = databaru;
  • baru->next = NULL;
  • baru->prev = NULL;
  • if(isEmpty()==1){
  • head=baru;
  • head->next = NULL;
  • head->prev = NULL;
  • }
  • else {
  • baru->next = head;
  • head->prev = baru;
  • head = baru;
  • }
  • cout<<”Data masuk\n”;
  • }

Penambahan data di belakang

  • Penambahan data dilakukan di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya.
  • Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan data baru.  Untuk mengetahui data terbelakang perlu digunakan perulangan.
  • void insertBelakang (int databaru){
  • TNode *baru,*bantu;
  • baru = new TNode;
  • baru->data = databaru;
  • baru->next = NULL;
  • baru->prev = NULL;
  • if(isEmpty()==1){
  • head=baru;
  • head->next = NULL;
  • head->prev = NULL;
  • }
  • else {
  • bantu=head;
  • while(bantu->next!=NULL){
  • bantu=bantu->next;
  • }
  • bantu->next = baru;
  • baru->prev = bantu;
  • }
  • cout<<“Data masuk\n”;
  • }

Function untuk menampilkan isi DLLNC

  • void tampil(){
  • TNode *bantu;
  • bantu = head;
  • if(isEmpty()==0){
  • while(bantu!=NULL){
  • cout<<bantu->data<<” “;
  • bantu=bantu->next;
  • }
  • cout<<endl;
  • } else cout<<“Masih kosong\n”;
  • }

Bagaimana cara membaca data list secara terbalik?

  • Function untuk menghapus data di depan:
  • void hapusDepan (){
  • TNode *hapus;
  • int d;
  • if (isEmpty()==0){
  • if(head->next != NULL){
  • hapus = head;
  • d = hapus->data;
  • head = head->next;
  • head->prev = NULL;
  • delete hapus;
  • } else {
  • d = head->data;
  • head = NULL;
  • }
  • cout<<d<<” terhapus\n”;
  • } else cout<<“Masih kosong\n”;
  • }
  • Function untuk menghapus node terbelakang
  • void hapusBelakang(){
  • TNode *hapus;
  • int d;
  • if (isEmpty()==0){
  • if(head->next != NULL){
  • hapus = head;
  • while(hapus->next!=NULL){
  • hapus = hapus->next;
  • }
  • d = hapus->data;
  • hapus->prev->next = NULL;
  • delete hapus;
  • } else {
  • d = head->data;
  • head = NULL;
  • }
  • cout<<d<<” terhapus\n”;
  • } else cout<<“Masih kosong\n”;
  • }
  • Tidak diperlukan pointer bantu yang mengikuti pointer hapus yang berguna untuk menunjuk ke NULL
  • Karena pointer hapus sudah bisa menunjuk ke pointer sebelumnya dengan menggunakan elemen prev ke node sebelumnya, yang akan diset agar menunjuk ke NULL setelah penghapusan dilakukan.
  • Function untuk menghapus semua elemen
  • void clear(){
  • TNode *bantu,*hapus;
  • bantu = head;
  • while(bantu!=NULL){
  • hapus = bantu;
  • bantu = bantu->next;
  • delete hapus;
  • }
  • head = NULL;
  • }

DLLNC dengan HEAD dan TAIL

  • Dibutuhkan dua buah variabel pointer: head dan tail
  • Head akan selalu menunjuk pada node pertama, sedangkan tail akan selalu menunjuk pada node terakhir.

Inisialisasi DLLNC

  • TNode *head, *tail;

Fungsi Inisialisasi DLLNC

  • void init(){
    • head = NULL;
    • tail = NULL;
  • }

Function untuk mengetahui kosong tidaknya DLLNC

  • int isEmpty(){
  • if(tail == NULL) return 1;
  • else return 0;
  • }
  • Tambah Depan
  • void insertDepan (int databaru){
  • TNode *baru;
  • baru = new TNode;
  • baru->data = databaru;
  • baru->next = NULL;
  • baru->prev = NULL;
  • if(isEmpty()==1){
  • head=baru;
  • tail=head;
  • head->next = NULL;
  • head->prev = NULL;
  • tail->prev = NULL;
  • tail->next = NULL;
  • }
  • else {
  • baru->next = head;
  • head->prev = baru;
  • head = baru;
  • }
  • cout<<“Data masuk\n”;
  • }

Penambahan node di belakang

Penambahan node di belakang akan selalu dikaitkan dengan tail dan kemudian

node baru tersebut akan menjadi tail

  • void insertBelakang(int databaru){
  • TNode *baru;
  • baru = new TNode;
  • baru->data = databaru;
  • baru->next = NULL;
  • baru->prev = NULL;
  • if(isEmpty()==1){
  • head=baru;
  • tail=head;
  • head->next = NULL;
  • head->prev = NULL;
  • tail->prev = NULL;
  • tail->next = NULL;
  • }
  • else {
  • tail->next = baru;
  • baru->prev = tail;
  • tail = baru;
  • tail->next = NULL;
  • }
  • cout<<“Data masuk\n”;
  • }
  • Function untuk menampilkan isi linked list
  • void tampil(){
  • TNode *bantu;
  • bantu = head;
  • if(isEmpty()==0){
  • while(bantu!=tail->next){
  • cout<<bantu->data<<” “;
  • bantu=bantu->next;
  • }
  • cout<<endl;
  • } else cout<<“Masih kosong\n”;
  • }
  • Function untuk menghapus data di data terdepan
  • void hapusDepan(){
  • TNode *hapus;
  • int d;
  • if (isEmpty()==0){
  • if(head->next != NULL){
  • hapus = head;
  • d = hapus->data;
  • head = head->next;
  • head->prev = NULL;
  • delete hapus;
  • } else {
  • d = head->data;
  • head = NULL;
  • tail = NULL;
  • }
  • cout<<d<<” terhapus\n”;
  • } else cout<<“Masih kosong\n”;
  • }
  • Function untuk menghapus node terbelakang
  • void hapusBelakang(){
  • TNode *hapus;
  • int d;
  • if (isEmpty()==0){
  • if(head->next != NULL){
  • hapus = tail;
  • d = tail->data;
  • tail = tail->prev;
  • tail->next = NULL;
  • delete hapus;
  • } else {
  • d = head->data;
  • head = NULL;
  • tail = NULL;
  • }
  • cout<<d<<” terhapus\n”;
  • } else cout<<“Masih kosong\n”;
  • }
  • Pointer hapus tidak perlu di loop untuk mencari node terakhir.  Pointer hapus hanya perlu menunjuk pada pointer tail saja.
  • Karena pointer hapus sudah bisa menunjuk ke pointer sebelumnya dengan menggunakan elemen prev, maka pointer prev hanya perlu diset agar menunjuk ke NULL.  Lalu pointer hapus didelete.
  • Function untuk menghapus semua elemen LinkedList
  • void clear(){
  • TNode *bantu,*hapus;
  • bantu = head;
  • while(bantu!=NULL){
  • hapus = bantu;
  • bantu = bantu->next;
  • delete hapus;
  • }
  • head = NULL;
  • tail = NULL;
  • }
  • Menggunakan pointer bantu yang digunakan untuk bergerak sepanjang list, dan menggunakan pointer hapus yang digunakan untuk menunjuk node-node yang akan dihapus.
  • Pada saat pointer hapus menunjuk pada node yang akan dihapus, pointer bantu akan bergerak ke node selanjutnya, dan kemudian pointer hapus akan didelete.

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.
  • Pengertian:
    • Single : artinya field pointer-nya hanya satu buah saja dan satu arah.
    • Linked List : artinya node-node tersebut saling terhubung satu sama lain.
    • Circular : artinya pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar

Ilustrasi SLLC

  • Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data.
  • Pada akhir linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar.

Deklarasi dan node baru SLLC

Deklarasi node

Dibuat dari struct berikut ini:

typedef struct TNode{

int data;

TNode *next;

};

Pembentukan node baru

Digunakan keyword new yang berarti mempersiapkan sebuah node baru

berserta alokasi memorinya.

TNode *baru;

baru = new TNode;

baru->data = databaru;

baru->next = baru;

SLLC dengan 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 melalui node pertama dalam linked list.  Deklarasinya sebagai berikut:

TNode *head;

Fungsi Inisialisasi Single LinkedList Circular

void init(){

head = NULL;

}

Function untuk mengetahui kosong tidaknya SLLC

int isEmpty(){

if(head == NULL) return 1;

else return 0;

}

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 pada head nya.
  • Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan.  Untuk menghubungkan node terakhir dengan node terdepan dibutuhkan pointer bantu.

void insertDepan(int databaru){

TNode *baru,*bantu;

baru = new TNode;

baru->data = databaru;

baru->next = baru;

if(isEmpty()==1){

head=baru;

head->next=head;

}

else {

bantu = head;

while(bantu->next!=head){

bantu=bantu->next;

}

baru->next = head;

head = baru;

bantu->next = head;

}

printf(“Data masuk\n“);

}

Penambahan data di belakang

  • Penambahan data dilakukan di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya.
  • Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan data baru.  Untuk mengetahui data terbelakang perlu digunakan perulangan.

void insertBelakang (int databaru){

TNode *baru,*bantu;

baru = new TNode;

baru->data = databaru;

baru->next = baru;

if(isEmpty()==1){

head=baru;

head->next=head;

}

else {

bantu = head;

while(bantu->next != head){

bantu=bantu->next;

}

bantu->next = baru;

baru->next = head;

}

printf(“Data masuk\n“);

}

Function untuk menampilkan isi single linked list

void tampil(){

TNode *b;

b = head;

if(isEmpty()==0){

do{

printf(“%d “,b->data);

b=b->next;

}while(b!=head);

printf(“\n”);

} else printf(“Masih kosong\n“);

}

void hapusDepan (){

TNode *hapus,*bantu;

if (isEmpty()==0){

int d;

hapus = head;

d = head->data;

if(head->next != head){

bantu = head;

while(bantu->next!=head){

bantu=bantu->next;

}

head = head->next;

delete hapus;

bantu->next = head;

}else{

head=NULL;

}

printf(“%d terhapus\n“,d);

} else printf(“Masih kosong\n“);

}

void hapusBelakang(){

TNode *hapus,*bantu;

if (isEmpty()==0){

int d;

hapus = head;

if(head->next == head){

head = NULL;

}else{

bantu = head;

while(bantu->next->next != head){

bantu = bantu->next;

}

hapus = bantu->next;

d = bantu->data;

bantu->next = head;

delete hapus;

}

printf(“%d terhapus\n“,d);

} else printf(“Masih kosong\n“);

}

Function untuk menghapus semua elemen Linked List

void clear(){

TNode *bantu,*hapus;

bantu = head;

while(bantu->next!=head){

hapus = bantu;

bantu = bantu->next;

delete hapus;

}

head = NULL;

}

  • Dibutuhkan dua buah variabel pointer: head dan tail
  • Head akan selalu menunjuk pada node pertama, sedangkan tail akan selalu menunjuk pada node terakhir.

SLLC dengan HEAD dan TAIL

Inisialisasi SLLC

TNode *head, *tail;

Fungsi Inisialisasi SLLC

void init(){

head = NULL;

tail = NULL;

}

Function untuk mengetahui kosong tidaknya SLLC

int isEmpty(){

if(tail == NULL) return 1;

else return 0;

}

Pengkaitan node baru ke linked list di depan

Penambahan data baru di depan akan selalu menjadi head.

void insertDepan(int databaru){

TNode *baru;

baru = new TNode;

baru->data = databaru;

baru->next = baru;

if(isEmpty()==1){

head=baru;

tail=baru;

head->next=head;

tail->next=tail;

}

else {

baru->next = head;

head = baru;

tail->next = head;

}

printf(“Data masuk\n“);

}

void tambahBelakang(int databaru){

TNode *baru;

baru = new TNode;

baru->data = databaru;

baru->next = baru;

if(isEmpty()==1){

head=baru;

tail=baru;

head->next=head;

tail->next=tail;

}

else {

tail->next = baru;

tail = baru;

tail->next = head;

}

cout<<“Data masuk\n”;

}

Function untuk menampilkan isi linked list:

void tampil(){

TNode *b;

b = head;

if(isEmpty()==0){

do{

printf(“%d”,b->data);

b=b->next;

}while(b!=tail->next);

printf(“\n”);

} else printf(“Masih kosong\n“);

}

Function untuk menghapus data di depan

void hapusDepan(){

TNode *hapus;

if (isEmpty()==0){

int d;

hapus = head;

d = head->data;

if(head != tail){

hapus = head;

head = head->next;

tail->next = head;

delete hapus;

}else{

head=NULL;

tail=NULL;

}

printf(“%d terhapus\n“,d);

} else printf(“Masih kosong\n“);

}

  • Function di atas akan menghapus data terdepan (pertama) yang ditunjuk oleh head pada linked list
  • Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penunjukkan terlebih dahulu dengan variabel hapus pada head, kemudian dilakukan pergeseran head ke node berikutnya sehingga data setelah head menjadi head baru,  kemudian menghapus variabel hapus dengan menggunakan perintah delete.
  • Jika tail masih NULL maka berarti data masih kosong!

Function untuk menghapus data di belakang:

void hapusBelakang(){

TNode *hapus,*bantu;

if (isEmpty()==0){

int d;

if(head == tail){

d = tail->data;

head = NULL;

tail = NULL;

}else{

bantu = head;

while(bantu->next != tail){

bantu = bantu->next;

}

hapus = tail;

tail = bantu;

d = hapus->data;

tail->next = head;

delete hapus;

}

printf(“%d terhapus\n“,d);

} else printf(“Masih kosong\n“);

}

  • Function di atas akan menghapus data terbelakang (terakhir) yang ditunjuk oleh tail pada linked list
  • Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penunjukkan terlebih dahulu dengan variabel hapus pada tail, kemudian dibutuhkan pointer bantu untuk membantu pergeseran dari head ke node berikutnya sampai sebelum tail, sehingga tail dapat ditunjukkan ke bantu tersebut, dan bantu tersebut akan menjadi tail yang baru.  Setelah itu hapus variabel hapus dengan menggunakan perintah delete.
  • Jika tail masih NULL maka berarti data masih kosong!

Function untuk menghapus semua elemen LinkedList

void clear(){

TNode *bantu,*hapus;

if(isEmpty() == 0){

bantu = head;

while(bantu->next!=head){

hapus = bantu;

bantu = bantu->next;

delete hapus;

}

head = NULL;

tail = NULL;

}

}

  • Menggunakan pointer bantu yang digunakan untuk bergerak sepanjang list, dan menggunakan pointer hapus yang digunakan untuk menunjuk node-node yang akan dihapus.
  • Pada saat pointer hapus menunjuk pada node yang akan dihapus, pointer bantu akan bergerak ke node selanjutnya, dan kemudian pointer hapus akan didelete.

SELESAI

Kembali ke => Kumpulan mata kuliah Teknik Informatika

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s