Struktur Data Dan Algoritma - Universitas Indonesia

Struktur Data dan AlgoritmaImplementasi ADT: Linked - ListSuryana Setiawan, Ruli Manurung & Ade Azurat(acknowledgments: Denny) Fasilkom UISUR – HMM – AAFasilkom UI - IKI20100/ IKI80110P2009/2010 – Ganjil – Minggu 6

Outline Linked Lists vs. ArrayLinked Lists dan IteratorsVariasi Linked Lists: Doubly Linked ListsCircular Linked ListsSorted Linked ListsSUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 62

Tujuan Memahami struktur data linked-list Memahami kompleksitas dari operasioperasi pada ADT linked-list antara laininsert, delete, read Dapat mengimplementasikan linked-listSUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 63

Linked ListsA0A1A2A3 Menyimpan koleksi elemen secara noncontiguously. Elemen dapat terletak pada lokasi memory yangsaling berjauhan. Bandingkan dengan arraydimana tiap-tiap elemen akan terletak pada lokasimemory yang berurutan. Mengizinkan operasi penambahan ataupenghapusan elemen ditengah-tengah koleksidengan hanya membutuhkan jumlahperpindahan elemen yang konstan. Bandingkan dengan array. Berapa banyak elemenyang harus dipindahkan bila akan menyisipielemen ditengah-tengah array?SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 64

Iterate the Linked List Items are stored in contiguous array://step through array a, outputting each itemfor (int index 0; index a.length; index ) System.out.println (a[index]); Items are stored in a linked list noncontiguously :// step through List theList, outputting each itemfor (ListNode p theList.first; p ! null; p p.next) System.out.println (p.data);A0A1firstSUR – HMM – AAA2A3lastFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 65

Implementasi: Linked Lists Sebuah list merupakan rantai dari object bertipeListNode yang berisikan data dan referensi (pointer)kepada ListNode selanjutnya dalam list. Harus diketahui dimana letak elemen pertama!ListNodeA0A1firstSUR – HMM – AAA2A3lastFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 66

ListNode: Definisipublic class ListNode {Object element;// data yang disimpanListNode next;// constructorsListNode (Object theElement, ListNode n) { element theElement;next n;}ListNode (Object theElement) { this (theElement, null);}ListNode () { this (null, null);}}SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 67

Catatan Penting! Yang disimpan dalam ListNode adalahreference dari object-nya, BUKAN object-nyaitu sendiri atau salinan dari object-nya !!!SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 68

Linked List: Insertionabcdcurrent Menyisipkan X pada lokasi setelah current.axcurrentxSUR – HMM – AAbFasilkom UI – IKI20100/IKI80110Pcd2009/2010 – Ganjil – Minggu 69

Langkah-langkah menyisipkan Menyisipkan elemen baru setelah posisicurrent// Membuat sebuah nodetmp new ListNode( );// meletakkan nilai x pada field elementmp.element x;// node selanjutnya dari x adalah node btmp.next current.next;// node selanjutnya dari a adalah node xcurrent.next tmp;acurrentbxtmpSUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 610

Langkah-langkah menyisipkan yang lebih efisientmp new ListNode (x, current.next);acurrentbxcurrent.next tmp;acurrentSUR – HMM – AAbxFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 611

Linked List: menambahkan elemen diakhir list menambahkan X pada akhir list// last menyatakan node terakhir dalam linked listlast.next new ListNode();last last.next; // adjust lastlast.element x; // place x in the nodelast.next null; // adjust nextabcxdlastlast lebih singkat:last last.next new ListNode (x, null);SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 612

Linked Lists: menghapus elemen Proses menghapus dilakukan denganmengabaikan elemen yang hendak dihapusdengan cara melewati pointer (reference)dari elemen tersebut langsung pada elemenselanjutnya.Elemen x dihapus dengan meng-assign fieldnext pada elemen a dengan alamat b.axbcurrentabcurrentSUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 613

Langkah-langkah menghapus elemen Butuh menyimpan alamat node yang terletaksebelum node yang akan dihapus. (padagambar node current, berisi elemen a) current.next current.next.next;axbcurrentKapan node x dihapus? Oleh siapa?SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 614

Langkah-langkah menghapus elemenaxbcurrent Tidak ada elemen lain yang menyimpanalamat node x. Node x tidak bisa diakses lagi. Java Garbage Collector akan membersihkanalokasi memory yang tidak dipakai lagi atautidak bisa diakses. Dengan kata lain, menghapus node x.SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 615

Pertanyaan: Selama ini contoh menyisipkan danmenghapus elemen dengan asumsi ada nodecurrent yang terletak sebelumnya. Bagaimana menambahkan node pada urutanpertama pada linked list?Bagaimana menghapus elemen pertama padalinked list?SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 616

Header Node Menghapus dan menambahkan elemen pertamamenjadi kasus khusus.Dapat dihindari dengan menggunakan header node; Tidak berisikan data, digunakan untuk menjaminbahwa selalu ada elemen sebelum elemenpertama yang sebenarnya pada linked list. Elemen pertama diperoleh dengan: current header.next; Empty list jika: header.next null;Proses pencarian dan pembacaan mengabaikanheader node.ABCHeaderSUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 617

Linked Lists: List interfacepublic interface List{/**Test if the list is logically empty.@return true if empty, false otherwise.*/boolean isEmpty ();/**Make the list logically empty.*/void makeEmpty ();}SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 618

Linked Lists: List implementationpublic class LinkedList implements List{// friendly data, so LinkedListItr can have accessListNode header;/**Construct the list*/public LinkedList () {header new ListNode (null);}/**Test if the list is logically empty.@return true if empty, false otherwise.*/public boolean isEmpty( ) {return header.next null;}SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 619

Linked Lists: List implementation/**Make the list logically empty.*/public void makeEmpty( ) {header.next null;}}SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 620

Latihan Buatlah sebuah method untuk menghitungjumlah elemen dalam sebuah linked list!public static int listSize (LinkedList theList) {}SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 621

Diskusi Apakah implementasi tersebut benar? Bila kita hendak menambahkan method lainpada sebuah List, haruskah kita mengaksesfield next dari object node dan objectcurrent dari object list? Dapatkah kita memiliki interface yang lebihbaik, dan lebih seragam serta lebihmemudahkan untuk mengembangkanmethod-method lain?SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 622

Iterator Class Untuk melakukan sebagian besar operasi-operasi padaList, kita perlu menyimpan informasi posisi saat ini.(current position).Kelas List menyediakan method yang tidakbergantung pada posisi. Method tersebut antara lain:isEmpty, dan makeEmpty.List iterator (ListItr) menyediakan method-methodyang umum digunakan untuk melakukan operasi padalist antara lain: advance, retrieve, first.Internal struktur dari List di encapsulasi oleh Listiterator.Informasi posisi current disimpan dalam objectiterator.SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 623

Iterator Class// Insert x after current positionvoid insert (x);// Remove xvoid remove (x);// Remove item after current positionvoid removeNext( );// Set current position to view xboolean find( x );// Set current position to prior to firstvoid zeroth ();// Set current position to firstvoid first( );// Set current to the next nodevoid advance ();// True if at valid position in listboolean isInList ();// Return item in current positionObject retrieve() Exceptions thrown for illegal access, insert, or remove.SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 624

Contoh Sebuah method static untuk menghitungjumlah elemen dalam sebuah list.public static int listSize (List theList) {int size 0;ListItr itr new ListItr (theList);for (itr.first(); itr.isInList(); itr.advance()){size ;}return size;}SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 625

Java Implementations Sebagian besar cukup mudah; seluruhmethod relatif pendek.ListItr menyimpan reference dari objectlist sebagai private data.Karena ListItr is berada dalam packageyang sama dengan List, sehingga jika fielddalam List adalah (package) friendly,maka dapat di akses oleh ListItr.SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 626

LinkedListItr implementationpublic class LinkedListItr implements ListItr/** contains List header. */protected LinkedList theList;/** stores current position. */protected ListNode current;/**Construct the list.As a result of the construction, the current position isthe first item, unless the list is empty, in which casethe current position is the zeroth item.@param anyList a LinkedList object to which this iterator ispermanently bound.*/public LinkedListItr( LinkedList anyList ) {theList anyList;current theList.isEmpty( ) ? theList.header :theList.header.next;}SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 627

/**Construct the list.@param anyList a LinkedList object to which this iterator ispermanently bound. This constructor is provided forconvenience. If anyList is not a LinkedList object, aClassCastException will result.*/public LinkedListItr( List anyList ) throws ClassCastException{this( ( LinkedList ) anyList );}/*** Advance the current position to the next node in the list.* If the current position is null, then do nothing.* No exceptions are thrown by this routine because in the* most common use (inside a for loop), this would require the* programmer to add an unnecessary try/catch block.*/public void advance( ){if( current ! null ) current current.next;}SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 628

/*** Return the item stored in the current position.* @return the stored item or null if the current position* is not in the list.*/public Object retrieve( ) { return isInList( ) ? current.element : null;}/*** Set the current position to the header node.*/public void zeroth( ) { current theList.header;}/*** Set the current position to the first node in the list.* This operation is valid for empty lists.*/public void first( ) { current theList.header.next;}SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 629

/*** Insert after the current position.* current is set to the inserted node on success.* @param x the item to insert.* @exception ItemNotFound if the current position is null.*/public void insert( Object x ) throws ItemNotFound{if( current null ) throw new ItemNotFound( "Insertion error" );ListNode newNode new ListNode( x, current.next );current current.next newNode;}SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 630

/*** Set the current position to the first node containing an item.* current is unchanged if x is not found.* @param x the item to search for.* @return true if the item is found, false otherwise.*/public boolean find( Object x ) {ListNode itr theList.header.next;while( itr ! null && !itr.element.equals( x ) ) itr itr.next;if( itr null ) return false;current itr;return true;}SUR – HMM – AAFasilkom UI – IKI20100/IKI80110P2009/2010 – Ganjil – Minggu 631