makalah struktur data - double linked list circular

7/18/2019 Makalah Struktur Data - Double Linked List Circular

http://slidepdf.com/reader/full/makalah-struktur-data-double-linked-list-circular 1/33

BAB I

PENDAHULUAN

A. Latar Belakang Masalah

Kegiatan pembuatan makalah ini merupakan suatu kewajiban yang harus dilaksanakan oleh

mahasiswa/i sebagai pengganti Ujian Tengah Semester (UTS) dan akan di presentasikan saat Ujian

Akhir Semester (UAS) mata kuliah Struktur Data pada Semester Genap tahun ajaran !"#/!"$%

Dengan adanya pembuatan makalah ini& diharapkan para mahasiswa/i dapat memahami se'ara

pasti apa yang telah dibuat% ahasiswa/i mampu mempresentasikannya di depan dosen dan para

mahasiswa/i lainnya dengan rasa per'aya diri dan diharapkan dapat menjadi pengalaman untuk dunia

kerja yang sesungguhnya%

B. Rumusan Masalah

erdasarkan latar belakang masalah diatas& maka dapat dirumuskan permasalahan sebagai

berikut*"% agaimana pembagian tugas kelompok dalam menyusun makalah dengan judul +Double ,inked

,ist -ir'ular.% agaimana kami mendapatkan nilai yang maksimal dalam menyusun makalah dengan judul

+Double ,inked ,ist -ir'ular.0% agaimana kami mendapatkan nilai yang maksimal saat mempresentasikan makalah dengan judul

+Double ,inked ,ist -ir'ular.#% agaimana kami dapat memberikan gambaran yang jelas mengenai +Double ,inked ,ist -ir'ular.

kepada dosen dan mahasiswa/i lainnya

C. Alasan Pemilihan JudulDalam menyusun makalah ini& kami mengangkat judul +Double ,inked ,ist -ir'ular.& karena

memang adanya materi +Double ,inked ,ist -ir'ular. yang telah diberikan dosen untuk kami pahami&

1



rumuskan dan presentasikan dalam menempuh Ujian Tengah Semester (UTS) dan Ujian Akhir

Semester (UAS) mata kuliah Struktur Data pada Semester Genap tahun ajaran !"#/!"$%

D. Tuuan Penulisan

Tujuan dari penulisan makalah dan mempresentasikannya adalah*

"% Untuk memenuhi syarat penilaian pengganti Ujian Tengah Semester (UTS) dan Ujian Akhir

Semester (UAS) mata kuliah Struktur Data pada Semester Genap tahun ajaran !"#/!"$%

% Untuk memberikan gambaran yang jelas kepada dosen dan mahasiswa/i tentang +Double ,inked

,ist -ir'ular.%

0% endorong mahasiswa/i untuk mau berusaha dan mampu mempresentasikan dengan rasa per'aya

diri%

E. !istematika Penulisan

Sistematika penulisan yang disusun oleh kami adalah untuk memudahkan serta memberikan

gambaran singkat dan jelas mengenai +Double ,inked ,ist -ir'ular.%

Dalam penulisan makalah ini& kami akan menguraikan se'ara garis besar yang akan dibi'arakan&

yaitu*

A 1 234DA5U,UA4

Dalam bab ini kami ingin menguraikan tentang latar belakang masalah& rumusan masalah&

alasan pemilihan judul& tujuan penulisan dan sistematika penulisan%

A 11 1S1

Dalam bab ini se'ara garis besar menguraikan dan menjelaskan dengan detail 'ara

pembuatan& 'ara menambahkan data dan 'ara penghapusan data dalam +Double ,inked ,ist

-ir'ular.%

A 111 234UTU2

Dalam bab ini se'ara garis besar mengemukakan tentang kesimpulan dari pembahasan& kritik

dan saran& da6tar pustaka dan lampiran%

2



BAB II

I!I

A. D"u#le Linked List Cir$ular %DLLC&

Double ,inked ,ist -ir'ular (D,,-) adalah linked list dengan menggunakan pointer& dimana

setiap node memiliki 0 6ield& yaitu " 6ield pointer yang menunjuk pointer berikutnya (ne7t)& " 6ield

menunjuk pointer sebelumnya (pre8)& serta sebuah 6ield yang berisi data untuk node tersebut% Double

,inked ,ist -ir'ular pointer ne7t dan pre8 nya menunjuk ke dirinya sendiri se'ara 'ir'ular%

entuk 4ode Double ,inked ,ist -ir'ular (D,,-)*

3



2engertian*

Double * Artinya 6ield pointer9nya terdiri dari dua buah dan dua arah& yaitu pre8 dan ne7t%

,inked ,ist * Artinya node9node tersebut saling terhubung satu sama lain%

-ie'ular * Artinya pointer pre8 dan ne7t9nya menunjuk ke dirinya sendiri%

Sehingga elemen double link list terdiri dari tiga bagian*

a% agian data in6ormasi

b% 2ointer pre8 yang menunjuk ke elemen sebelumnya%

'% 2ointer ne7t yang menunjuk ke elemen berikutnya%

5al9hal yang harus diperhatikan *

a% Double ,inked list selalu memiliki pointer petunjuk yang selalu menunjuk pada awal dari list yang

disebut 5ead%

b% Double ,inked list juga selalu memiliki pointer petunjuk menunjuk pada akhir dari list yang

disebut Tail%

'% Setiap simpul yang terbentuk selalu memiliki nilai 41,& ke'uali jika simpul tersebut sudah ditunjuk

oleh simpul yang lainnya (Double ,ink ,ist belum terhubung)%

d% 2osisi simpul terakhir pada Doube linked list selalu bernilai 41, karena ia tidak menunjuk pada

simpul yang lainnya& ke'uali bentuk 'ir'ular%

e% :perasi yang dapat dilakukan pada Double ,inked ,ist diantaranya adalah*

• enambah Simpul (di Depan& elakang dan Tengah)%

• enghapus Simpul (di Depan& elakang dan Tengah)%

• emba'a isi link list (emba'a maju dan mundur)%

Se'ara umum& sebuah list bertipe T adalah sebuah barisan elemen9elemen bertipe T beserta

operasi9operasinya yang meliputi*

a% embuat list (menginisialisasi list)& yaitu membuat list menjadi kosong% b% enentukan apakah status list kosong atau tidak%

4



'% enentukan apakah status list penuh atau tidak%

d% engetahui panjang (jumlah elemen) list%

e% engetahui sebarang node dari list (menghapus node)%

6% engakses sebarang node dalam list& dengan memba'a nilai atau menganti nilai yang ada dengan

nilai yang baru%

g% enyisipkan node baru ke dalam list di sebarang lokasi%

'. Linked List Dengan P"inter

2as'al menyediakan prosedur standar untuk membuat dan menghapus sebuah 8ariable dinamis&

yaitu new dan dispose% ;ika p telah dideklarasikan sebagai sebuah 8ariable pointer bertipe node& maka

pernyataan new(p) akan men'iptakan sebuah 8ariable dinamis baru bertipe node dan menandai

lokasinya dengan pointer p% Sedangkan pernyataan dispose (p) akan mengembalikan ruang yang

digunakan pada lokasi yang ditunjuk p ke sistem komputer& pointer p menjadi tidak terde6inisi lagi%

Kadang9kadang sebuah pointer tidak menunjuk ke suatu 8ariable dinamis%

Kondisi ini harus ditandai dengan mengisi pointer tersebut dengan nilai standar nil% 5al ini

dapat dilakukan dengan pernyataan p*<nil= dan pada kesempatan lain kondisi ini dapat diperiksa

dengan pernyataan i6 p < nil>atau i6 p ?@nil>Kata nil merupakan kata ter'adang dalam pas'al% 4il

merupakan nilai generi' dan dapat diisikan ke sebarang 8ariable pointer dengan tipe apapun%

Double ,inked ,ist dipilih bila banyak operasi yang memerlukan predesesor% Sebagaimana

yang telah kita pelajari& untuk menghapus elemen senarai perlu alamat predesesornya& begitu juga

untuk menyisipkan elemen% Untuk menghindari pen'arian predesesor& maka pada setiap elemen

ditambahkan 6ield pre8 dan 6ield ne7t yang membuat operasi pada senarai ini lebih kompleks%

5



,inked ,ist (:ne ay ,ist) adalah suatu kumpulan elemen data (yang disebut sebagai node)

dimana urutannya ditentukan oleh suatu pointer%

Setiap elemen (node) dari suatu linked list terdiri atas dua bagian& yaitu*

•

14B:& berisi in6ormasi tentang elemen data yang bersangkutan%• 43CT (,ink Bield/4e7t 2ointer Bield)& berisi alamat dari elemen (node) selanjutnya yang

dituju%

2ada node ke9# 6ield 43CT9nya berisi 4U,,& artinya node ke9# tersebut adalah node terakhir%

4ode9node dalam linked list tidak harus selalu digambarkan paralel seperti pada gambar diatas% ,inked

list pada 'ontoh diatas dapat pula digambarkan seperti berikut ini*

Ada dua hal yang menjadi kerugian dengan representasi suatu data dengan linked list ini& yaitu*

a% Diperlukan ruang tambahan untuk menyatakan/tempat 6ield pointer%

b% Diperlukan waktu yang lebih banyak untuk men'ari suatu node dalam linked list%

Sedangkan keuntungannya adalah*

a% ;enis data yang berbeda dapat di9link% b% :perasi 3:E3 atau 14S3T hanya dilakukan dengan mengubah pointer9nya saja%

(. )*erasi Dasar Pada Linked List

Ada beberapa aturan yang dide6inisikan pada operasi didalam linked list% ;ika 2 adalah suatu

8ariabel pointer& maka nilainya adalah alamat atau lokasi dari 8ariabel lain yang dituju%

:perasi yang dide6inisikan pada suatu 8ariabel pointer adalah*

6



a% Test apakah sama dengan 4U,,%

b% Test untuk kesamaan dengan 8ariabel pointer lain%

'% enetapkan sama dengan 4U,,%

d% enetapkan menuju ke node lain%

4otasi yang dide6inisikan sehubungan dengan operasi diatas adalah*

a% 4:D3(2)& artinya node yang ditunjuk oleh pointer 2%

b% 14B:(2)& artinya nilai 14B: dari node yang ditunjuk pointer 2%'% 43CT(2)& artinya hubungan (link) selanjutnya dari node yang ditunjuk oleh pointer 2%

B. Pem#uatan D"u#le Linked List Cir$ular

2ada praktiknya sebuah struktur data memiliki elemen yang digunakan untuk saling menyimpan

rujukan antara satu dengan lainnya sehingga membentuk sebuah da6tar abstrak& tiap9tiap elemen yang

terdapat pada da6tar abstrak ini seringkali disebut sebagai node karena mekanisme rujukan yang saling

terkait inilah disebut sebagai da6tar berantai (linked list)% Sedangkan 'ir'ular double linked list sendiri

merupakan jenis linked list dimana rujukan pada node terakhir akan merujuk pada node pertama& dan

rujukan pada node pertama akan merujuk pada node terakhir bila yang digunakan sebagai dasar

implementasi adalah da6tar bertaut ganda ('ir'ular double linked list)%

Deklarasi 4ode dibuat dari stru't berikut ini*

2enjelasan*

7



• 2embuatan stru't bernama T4ode yang berisi 0 6ield& yaitu 6ield data bertipe integer dan 6ield

ne7t F pre8 yang bertipe pointer dari T4ode%

• 2embuatan stru't& buat 8ariabel haed yang bertipe pointer dari T4ode yang berguna sebagai

kepala linked list%

2embentukan node baru menggunakan keyword new yang berarti mempersiapkan sebuah node

baru berserta alokasi memorinya& pointer pre8 dan ne7t menunju ke dirinya sendiri%

C. D"u#le Linked List Cir$ular Menggunakan Head+

enggunakan " pointer head

• 5ead selalu menunjuk node pertama

Deklarasi 2ointer 5ead dengan manipulasi linked list tidak bisa dilakukan langsung ke node yang

dituju& melainkan harus melalui node pertama dalam linked list% Deklarasinya sebagai berikut*

Bungsi inisialisasi linked list*

8



Bungsi untuk mengetahui kosong atau tidaknya linked list*

'. Penam#ahan Data DLLC Head

Penam#ahan Data DLLC Head Di De*an

2enambahan node baru akan dikaitan di node paling depan& namun pada saat pertama kali (data

masih kosong)& maka penambahan data dilakukan pada head nya% 2ada prinsipnya adalah mengkaitkan

data baru dengan head& kemudian head akan menunjuk pada data baru tersebut sehingga head akan

tetap selalu menjadi data terdepan% Dibutuhkan pointer bantu yang digunakan untuk menunjuk node

terakhir (head9@pre8) yang akan digunakan untuk mengikat list dengan node terdepan%

1lustrasinya*

"% ,ist masih kosong (head<4U,,)

% asuk data baru& misalnya $

9



0% Datang data baru& misalnya !

#% Datang data baru& misalnya 0!

Penam#ahan Data DLLC Head Di Belakang

2enambahan data dilakukan di belakang& namun pada saat pertama kali data langsung ditunjuk

pada head9nya% 2enambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk

mengetahui data terbelakang& namun tidak diperlukan loop karena untuk mengetahui node terbelakang

hanya perlu menunjuk pada head9@pre8 saja% Kemudian dikaitkan dengan data baru% Untuk mengetahui

data terbelakang perlu digunakan perulangan%

10



1lustrasinya*



0% Datang data baru& misalnya ! (penambahan di belakang)

4. Datang data baru, misalnya 25 (penambahan di belaang!

11



(. Menam*ilkan Data DLLC Head

• Bun'tion di atas digunakan untuk menampilkan semua isi list& di mana linked list ditelusuri

satu9persatu dari awal node sampai akhir node% 2enelusuran ini dilakukan dengan menggunakan

suatu 8ariabel node bantu& karena pada prinsipnya 8ariabel node head yang menjadi tanda awal

list tidak boleh berubah/berganti posisi%

12



• 2enelusuran dilakukan terus sampai node terakhir ditemukan menunjuk ke head lagi% ;ika belum

sama dengan head& maka node bantu akan berpindah ke node selanjutnya dan memba'a isi

datanya dengan menggunakan 6ield ne7t sehingga dapat saling berkait%

• ;ika head masih 4U,, berarti data masih kosong

,. Pengha*usan Data DLLC Head

Pengha*usan Data DLLC Head Di De*an

13



• Bun'tion di atas akan menghapus data teratas (pertama) yang ditunjuk oleh head pada linked list

• 2enghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer& maka

harus ditampung dahulu pada pointer hapus dan barulah kemudian menghapus pointer hapus

dengan menggunakan perintah delete%

• ;ika head masih 4U,, maka berarti data masih kosong

Pengha*usan Data DLLC Head Di Belakang

• Diperlukan pointer bantu yang mengikuti pointer hapus yang berguna untuk menunjuk ke node

sebelum terakhir%

14



• Kemudian pointer hapus ditunjukkan ke node setelah pointer bantu& kemudian hapus pointer

hapus dengan perintah delete%

Pengha*usan !emua Data DLLC Head

15



D. D"u#le Linked List Cir$ular Menggunakan Head - Tail

• Dibutuhkan dua buah 8ariabel pointer* head dan tail

• 5ead akan selalu menunjuk pada node pertama& sedangkan tail akan selalu menunjuk pada node

terakhir%

Deklarasinya sebagai berikut*

Bungsi inisialisasi linked list*

Bungsi untuk mengetahui kosong atau tidaknya linked list*

16



'. Penam#ahan Data DLLC Head - Tail

Penam#ahan Data DLLC Head - Tail Di De*an

2enambahan 2enambahan node baru akan selalu dikaitan di node paling depan& namun pada saat

pertama kali (data masih kosong)& maka penambahan data dilakukan pada tail/head nya% Sedangkan

jika tidak kosong& data akan ditambahkan didepan head& kemudian node baru akan berubah menjadi

head%

1lustrasinya*

17



"% ,ist masih kosong (head<tail<4U,,)

% asukan data baru& misalnya $

3. Datang data baru, misalnya 20 (di depan!

Penam#ahan Data DLLC Head - Tail Di Belakang

18



2enambahan node di belakang akan selalu dikaitkan dengan tail dan kemudian node baru tersebut

akan menjadi tail%

1lustrasinya*


19




0% Datang data baru& misalnya ! (penambahan di belakang)

#% Datang data baru& misalnya $ (penambahan di belakang)

20



(. Menam*ilkan Data DLLC Head - Tail

3. Pengha*usan Data DLLC Head - Tail

Pengha*usan Data DLLC Head - Tail Di De*an

21



• Bun'tion di atas akan menghapus data teratas (pertama) yang ditunjuk oleh head pada linked list

• 2enghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer& maka

harus ditampung dahulu pada 8ariabel hapus dan barulah kemudian menghapus 8ariabel hapus

dengan menggunakan perintah delete%

• ;ika tail masih 4U,, maka berarti data masih kosong

Pengha*usan Data DLLC Head - Tail Di Belakang

22



• 2ointer hapus tidak perlu di loop untuk men'ari node terakhir% 2ointer hapus hanya perlu

menunjuk pada pointer tail saja%• Karena pointer hapus sudah bisa menunjuk ke pointer sebelumnya dengan menggunakan

elemen pre8 ke node sebelumnya% Kemudian pointer tail akan berpindah ke node sebelumnya%

23



Pengha*usan !emua Data DLLC Head Tail

BAB III

PENUTUP

A. Penutu*

Demikian yang dapat kami paparkan mengenai materi yang menjadi pokok bahasan dalam

makalah ini& tentunya masih banyak kekurangan dan kelemahannya& karena terbatasnya pengetahuan

dan kurangnya re6erensi yang berhubungan dengan Double ,inked ,ist -ir'ular% Semoga makalah ini

berguna bagi kami& khususnya juga para pemba'a yang budiman pada umumnya%

24



B. esim*ulan

Keberhasilan diberbagai bidang merupakan hasil dari pada kemajuan teknologi yang dapat

meningkatkan tara6 hidup manusia% Dengan adanya kemajuan ini kita perlu menyesuaikan diri% Untuk

itu kami berusaha dengan sepenuh hati dalam pembuatan makalah ini%

Setelah membuat makalah ini& kami menjadi lebih mengerti apa itu +Double ,inked ,ist

-ir'ular.& 'ara pembuatan& 'ara menambahkan data dan 'ara menghapus data yang ada pada Double

,inked ,ist -ir'ular.%

C. ritik Dan !aran

Kami banyak berharap para pemba'a yang budiman untuk memberikan kritik dan saran yang

membangun kepada kami demi sempurnanya makalah ini dan penulisan makalah di kesempatan9

kesempatan berikutnya%

25



D. Da/tar Pustaka

a'hmat& Antonius (!"")% Double Linked List Circular. Brom

http*//www%slideshare%net/hiteshwagle/Hdouble9linked9list9'ir'ular & April !"$

ikipedia (!"$)% Doubly Linked List. Brom http*//en%wikipedia%org/wiki/DoublyIlinkedIlist& April

!"$

;ohan& Shandy (!")% Struktur Data: Double Linked List Circular. Brom

http*//brawly8on6abre%blogspot%'om& April !"$

AJiJ& Abe (!")% Struktur Data: Double Linked List. Brom http*//abeaJis%blogspot%'om& April !"$

26

http://www.slideshare.net/hiteshwagle/9double-linked-list-circular

http://en.wikipedia.org/wiki/Doubly_linked_list

http://brawlyvonfabre.blogspot.com/

http://abeazis.blogspot.com/

http://en.wikipedia.org/wiki/Doubly_linked_list

http://brawlyvonfabre.blogspot.com/

http://abeazis.blogspot.com/

http://www.slideshare.net/hiteshwagle/9double-linked-list-circular



E. Lam*iran

-ontoh 'oding dan hasil 'ompile +Double ,inked ,ist -ir'ular. sederhana*

27



28



29



30



31



32



33

makalah struktur data - double linked list circular

Documents