Algoritma Pemrograman & Struktur Data

MODUL PERKULIAHAN

Algoritma Pemrograman & Struktur Data Linked List

Fakultas

Program Studi

Fakultas Ilmu Komputer

Informatika

Tatap Muka

03

Kode MK

Disusun Oleh

87042

Rinto Priambodo, ST, MTI

Abstract

Kompetensi

Penjelasan mengenai linked list dan penggunaannya

Memahami definisi linked list dan penggunaannya dalam pemrograman

Pembahasan Linked List Sebuah linked list merupakan sebuah rangkaian elemen di mana setiap elemen menunjuk pada elemen berikutnya. Setiap elemen memiliki variabel penyimpan data dan variabel penyimpan alamat dari elemen berikutnya.

Gambar 1 Ilustrasi linked list Apabila kumpulan elemen dalam sebuah array menempati alamat memori yang berurutan, maka linked list dapat menempati alamat memori yang tidak berurutan. Karena tiap elemen telah menyimpan alamat memori dari elemen berikutnya. Dengan demikian alokasi memori untuk sebuah linked list menjadi lebih mudah untuk linked list dibandingkan dengan array. Selain itu linked list juga memiliki beberapa kelebihan lain dibandingkan array. Sehingga dalam beberapa kasus pengolahan tipe data berelemen banyak maka penggunaan linked list lebih efektif dibandingkan array. Memory

Array

Linked List Gambar 2 Contoh penempatan array dan linked list dalam memory

Model penempatan linked list yang lebih fleksibel daripada array membuatnya lebih efektif dalam penggunaan memori karena tidak harus mencari blok memori berurutan. Namun karena tiap elemen harus membawa informasi yang lebih banyak (data dan alamat elemen berikutnya) maka tiap elemen akan membutuhkan alokasi yang lebih besar dibandingkan array.

2014

2

Algoritma Pemrograman dan Struktur Data Rinto Priambodo, ST, MTI

Pusat Bahan Ajar dan eLearning http://www.mercubuana.ac.id

Array vs Linked List Jika dibandingkan, array dan linked list memiliki beberapa perbedaan seperti berikut. 1. Cara mengakses tiap elemen a. Array Untuk mengetahui alamat memori dari sebuah elemen dalam sebuah array, yang dibutuhkan hanyalah alamat memori dari indeks pertama (alamat memori dari array tersebut), indeks elemen yang dicari dan besar memori yang dibutuhkan oleh tiap elemen. Jadi jika alamat memori dari array adalah x, indeks yang dicari adalah y dan besar memori tiap elemen adalah z, maka alamat memori dari elemen yang dicari adalah x + y * z. Dengan demikian waktu yang dibutuhkan untuk mengakses elemen mana pun adalah sama. b. Linked List Untuk mengetahui alamat memori dari sebuah elemen dalam sebuah linked list, kita harus mencari alamat tersebut satu persatu dari tiap elemen. Misalnya, kita ingin mencari alamat memori dari elemen ke-x, maka kita harus melihat dulu pointer pada elemen pertama untuk menemukan alamat memori dari elemen kedua. Setelah menemukan elemen kedua kita harus melihat pointer pada elemen kedua untuk menemukan alamat memori dari elemen ketiga. Seterusnya hingga kita mencapai elemen ke-x. Dengan demikian waktu yang dibutuhkan untuk mengakses tiap elemen adalah berbeda-beda. Makin besar indeksnya maka makin besar pula waktu yang dibutuhkan untuk menemukannya. 2. Kebutuhan memori a. Array Untuk mengalokasikan sebuah array dalam memori dibutuhkan ukuran yang tetap. Misalnya, untuk mengalokasikan sebuah array dengan lima elemen maka dibutuhkan memori sebesar lima kali ukuran tiap elemen. Hanya saja biasanya kita tidak selalu menggunakan keseluruh elemen yang disediakan sehingga ada kemungkinan dari seluruh alokasi memori ada bagian yang tidak terpakai. Selain itu juga apabila ingin dialokasikan array dalam jumlah besar ada kemungkinan tidak tersedia sisa memori yang berurutan dalam ukuran yang cukup besar untuk kebutuhan tersebut. b. Linked List Sebuah linked list hanya membutuhkan memori sebesar yang digunakannya sehingga tidak ada alokasi memori yang tidak terpakai. Hanya saja tiap

2014

3



elemen dari linked list akan membutuhkan memori ekstra untuk menyimpan variabel pointer. Selain itu juga karena linked list tidak membutuhkan alamat memori yang berurutan, tiap elemen dapat ditempatkan di alamat memori mana pun. Dengan demikian jika hanya tersedia sisa memori dalam ukuran yang kecil-kecil maka linked list lebih mudah ditempatkan. 3. Waktu yang dibutuhkan untuk insert dan delete a. Array Berikut ini adalah langkah-langkah yang dibutuhkan untuk melakukan insert dan delete dalam array: -

Insert/delete di awal 5

3

1

4

2

5

3

1

4

Untuk dapat menyisipkan nilai 2 di awal harus lebih dulu memindahkan angka 5, 3, 1 dan 4 ke indeks yang lain satu persatu. Dengan demikian makin banyak jumlah elemen yang harus dipindahkan maka makin lama waktu yang dipindahkan untuk memindahkan seluruh nilai. Begitu pula kebutuhan waktu untuk menghapus elemen pertama seperti berikut: 2

5

3

1

5

3

1

4

4

Demikian pula untuk menyisipkan sebuah nilai di tengahtengah sebuah array. Besar waktu yang dibutuhkan adalah sebanding dengan jumlah elemen. Makin banyak elemen yang dimiliki, maka makin banyak elemen yang harus dipindahkan agar nilai yang baru dapat disisipkan. -

Insert/delete di akhir jika array belum penuh 5

3

Jika

masih

7

1

4

ada

elemen

yang

kosong

dalam

array,

menyisipikan atau menghapus sebuah elemen di akhir array bisa langsung dilakukan menggunakan indeksnya. Jadi

2014

4



berapapun panjang arrays maka untuk menyisipkan nilai baru di akhir array akan membutuhkan waktu yang sama. Begitu pula

untuk

menghapus

bagian

akhir

dari

array akan

membutuhkan waktu yang sama berapa pun panjang array tersebut. -

Insert/delete di akhir jika array telah penuh 5

3

1

4

5

3

1

4

7

Apabila array telah penuh dan kita ingin menambahkan sebuah elemen baru di akhir, maka kita harus membuat lebih dulu array baru dengan panjang yang lebih besar. Kemudian semua nilai yang ada di array pertama harus dipindahkan satu persatu ke dalam array yang baru tersebut. Dengan demikian nilai yang baru dapat dimasukkan ke akhir array. Jadi untuk menambahkan sebuah nilai baru ke dalam array yang telah penuh dibutuhkan waktu sesuai jumlah elemen dari array yang dipindahkan. Makin banyak elemen maka makin banyak pula waktu yang dibutuhkan. b. Linked List Berikut ini adalah langkah-langkah yang dibutuhkan untuk melakukan insert dan delete dalam linked list: -

Insert/delete di awal 5

3

1

4

2 Untuk dapat menyisipkan elemen bernilai 2 di awal maka terlebih dahulu dibuat elemen baru yang memiliki nilai 2. Kemudian pointer dari elemen baru tersebut diarahkan ke alamat memori elemen pertama dari linked list. Dengan demikian berapapun jumlah elemen yang ada, waktu yang dibutuhkan untuk menambahkan sebuah elemen di awal adalah sama.

2014

5



-

Insert/delete di akhir 5

3

1

4 2

Untuk dapat menyisipkan sebuah elemen baru di akhir linked list kita harus mengganti pointer dari elemen terakhir agar mengarah ke alamat memori dari elemen yang baru tersebut. Hanya saja untuk dapat menemukan elemen yang terakhir kita harus menyusuri satu persatu dari elemen pertama hingga menemukan elemen terakhir yang memiliki pointer NULL. Dengan demikian untuk menambahkan sebuah elemen baru di akhir linked list akan membutuhkan waktu yang bergantung pada banyaknya elemen. Makin banyak elemen yang dimiliki makin besar waktu yang dibutuhkan untuk menambahkan elemen baru tersebut. Begitu pula untuk menghapus elemen terakhir, kita juga harus menyusuri tiap elemen hingga menemukan elemen terakhir yang memiliki pointer NULL. Kemudian elemen sebelumnya kita ubah pointernya menjadi NULL sehingga elemen terakhir tadi tidak lagi berada di dalam linked list. -

Insert/delete pada posisi tertentu 5

3

1

4

2 Untuk menyisipkan sebuah elemen baru ke dalam sebuah linked list pada posisi tertentu kita harus menemukan terlebih dahulu alamat memori dari elemen yang akan disisipi. Caranya adalah dengan menyusuri satu persatu tiap elemen hingga mencapai posisi elemen yang diinginkan. Lalu elemen tersebut kita ganti pointernya menjadi alamat dari elemen yang baru dan alamat yang sebelumnya tersimpan dalam pointer tersebut dipindahkan ke pointer dari elemen yang baru. Dengan demikian elemen yang baru menjadi bagian dari linked list pada posisi di tengah-tengah linked list (tidak 2014

6



diujung). Karena harus menyusuri tiap elemen satu persatu maka waktu yang dibutuhkan untuk operasi ini sangat bergantung pada jumlah elemen yang harus ditelurusi. Makin banyak elemennya makin lama pula waktu yang dibutuhkan. 4. Kemudahan dalam penggunaan Array lebih mudah digunakan dibandingkan dengan linked list karena array sudah memiliki indeks yang bisa langsung digunakan untuk mengakses elemen-elemen yang ada. Sementara itu penggunaan linked list masih sangat mengandalkan pembacaan pointer alamat memori sehingga masih sangat rawan terjadi kesalahan. Berikut ini adalah rangkuman dari perbandingan antara array dan linked list Array

Linked List

Cara mengakses tiap elemen Membutuhkan waktu konstan: O(1)

Waktunya berbeda-beda untuk tiap elemen: O(n)

Kebutuhan memori

- Ukuran memori yang digunakan tetap - Ada kemungkinan memori yang sudah dialokasikan yang tidak terpakai - Ada kemungkinan tidak mendapat alokasi memori yang cukup karena harus langsung satu blok besar

- Tak ada alokasi memori yang tak terpakai - Butuh memori ekstra di tiap elemen untuk variabel pointer - Alokasi memori lebih mudah didapat karena butuhnya dalam blok-blok kecil

Waktu yang dibutuhkan untuk insert dan delete

- Di awal: O(n) - Di akhir: O(1) jika array tidak penuh, O(n) jika array penuh - Di posisi tertentu: O(n)

- Di awal: O(1) - Di akhir: O(n) - Di posisi tertentu: O(n)

Kemudahan dalam penggunaan

Mudah

Lebih berisiko

Dari perbandingan di atas terlihat bahwa linked list lebih unggul ketika digunakan untuk kondisi di mana insert dan delete lebih banyak digunakan.

2014

7



Double-linked List Tiap elemen pada double-linked list memiliki dua pointer. Pointer pertama menyimpan alamat elemen berikutnya dan pointer kedua menyimpan alamat elemen sebelumnya. NULL

5

3

1

2

NULL

Gambar 3 Double-linked list Untuk menyisipkan sebuah elemen baru, kita harus menemukan dulu lokasi penempatan dengan menyusuri elemen satu-persatu. Kemudian pointer pertama dari elemen baru diisi dengan alamat elemen berikutnya dan pointer kedua diisi alamat dari elemen sebelumnya. Begitu pula dengan pointer pada elemen berikutnya dan sebelumnya juga harus diubah sehingga berisi alamat dari elemen yang baru. NULL

5

3

1

2

NULL

7 Gambar 4 Insert elemen baru ke dalam double-linked list

Tree Sebuah metode pencarian menggunakan linked list bernama Binary Tree menggunakan dua buah pointer pada setiap elemennya. Setiap elemen memiliki pointer kiri dan kanan yang masing-masing menyimpan alamat elemen subtree yang kiri dan kanan. lemon

NULL

apple

NULL

pear

grape NULL

NULL

orange NULL

Gambar 5 Binary Tree

2014

8



NULL

plum NULL

Dalam Gambar 5 yang merupakan contoh binary tree untuk menyimpan sejumlah kata secara berurutan berdasarkan abjad. Tiap elemen memiliki dua pointer. Pointer kiri menunjuk ke elemen di subtree kiri yang menyimpan kata dengan abjad yang lebih kecil. Sedangkan pointer kanan menunnjuk ke elemen subtree kanan yang menyimpan kata dengan abjad yang lebih besar dan seterusnya hingga elemen paling bawah yang tidak memiliki subtree maka memiliki pointer NULL. Linked list bentuk binary tree seperti contoh tersebut berguna ketika kita ingin membuat sebuah program pencarian. Proses pencarian menuggunakan tree bisa lebih cepat dibandingkan dengan linked list atau array yang berurutan. Sebagai contoh, kita ingin mencari kata “orange” dalam binary tree di Gambar 5. Maka langkah-langkah pencariannya adalah sebagai berikut: -

Pertama kita bandingkan “orange” dengan “lemon” yang berada di root atau puncak

-

Karena “orange” > “lemon” maka kita akan mengambil subtree sebelah kanan dan menemukan “pear”

-

Lalu kita bandingkan “orange” dengan “pear”

-

Karena “orange” < “pear” maka kita akan mengambil pointer kiri dan menemukan “orange”

-

Jadilah kita

menemukan “orange” tanpa harus mengecek satu persatu semua

elemen Berikut ini adalah algoritma untuk menyisipkan sebuah elemen ke dalam binary tree sesuai kriteria urutan abjad seperti pada contoh dalam Gambar 5: 1. Jika ini adalah null tree (atau subtree) maka buatlah satu elemen tree dengan kata tersebut 2. Jika elemen tersebut telah mengandung kata yang dimaksud, jangan lakukan apaapa 3. Tapi jika tidak, masukkan kata ke dalam subtree kiri atau kanan, tergantung perbandingan kata tersebut Langkah-langkah dalam algoritma tersebut berhenti pada dua kondisi: 1. Kata yang sama ditemukan 2. Menemukan elemen null Jika tidak maka kita akan memasukkan kata ke dalam subtree.

2014

9



Sebagai contoh, kita ingin memasukkan kata “fig” ke dalam tree pada Gambar 5. Langkahlangkahnya adalah sebagai berikut: -

Pertama kita bandingkan kata “fig” dengan “lemon”

-

Karena “fig” lebih kecil maka kita akan melihat elemen berisi kata “apple”

-

Lalu kita bandingkan “fig” dengan “apple”

-

Karena “fig” lebih besar maka kita akan melihat elemen berisi kata “grape”

-

Lalu kita bandingkan “fig” dengan “grape”

-

Karena “fig” lebih kecil maka kita akan melihat elemen di sebelah kiri dari “grape”

-

Karena tidak ada elemen lain atau NULL maka kita akan membuat elemen baru di sebelah kiri “grape” yang memuat kata “fig”

2014

10



Contoh Soal 1. Buatlah program dalam bahasa C++ untuk membuat linked list, menambahkan elemen baru dan menampilkannya! #include struct node { int x; node *next; }; int main() { node *root; // This won't change, or we would lose the list node *conductor; // This will point to each node as it traverses root = new node; // Sets it to actually point to something root->next = 0; // Otherwise it would not work well root->x = 12; conductor = root; // The conductor points to the first node if ( conductor != 0 ) { while ( conductor->next != 0) conductor = conductor->next; } conductor->next = new node; // Creates a node at the end of list conductor = conductor->next; // Points to that node conductor->next = 0; // Prevents it from going any further conductor->x = 42;

}

conductor = root; if ( conductor != 0 ) { // Makes sure there is a place to start while ( conductor->next != 0 ) { cout<< conductor->x; conductor = conductor->next; } cout<< conductor->x; }

2014

11



Daftar Pustaka Oualline, S. (1995), Practical C+ Programming,O’Reilly & Associates, Inc.

2014

12



Algoritma Pemrograman & Struktur Data

Recommend Documents