Double Linked List Circular

 

•   Double: artinya field pointer-nya terdiri dari dua buah dan dua arah, yaitu prev dan next

• Linked List: artinya node-node tersebut saling terhubung satu sama lain.

•  Circular: artinya pointer next dan prev-nya menunjuk ke dirinya sendiri

•  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          dirinya sendiri.

•  Jika sudah lebih dari satu node, maka pointer prev akan menunjuk ke node sebelumnya, dan pointer next akan menunjuk ke node sesudahnya.

       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 = baru;

baru->prev = baru;

·         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.

         Ada tida macam kunjungan pada pohon biner, yaitu kunjungan PreOrder, InOrder, dan  PostOrder. Selain itu ada kunjungan LevelOrder, yaitu yang berdasarkan kedudukan tiap simpul dalam pohon. Keempat kunjungan itu dibagi menjadi orientasi, yaitu left to right oriented (LRO) atau kunjungan dilakukan di cabang kiri dulu baru ke cabang kanan dan right to left oriented (RLO) atau kunjungan dilakukan di cabang kanan dulu baru ke cabang kiri.



1. Kunjungan PreOrder
Kunjungan PreOrder LRO atau sering disebut dengan depth first order
menggunakan urutan sebagai berikut :
Cetak isi simpul yang dikunjungi.
Kunjungi cabang kiri.
Kunjungi cabang kanan.

Prosedur kunjungan PreOrder dapat dilakukan dengan cara rekursif atau non rekursif. Prosedur kunjungan secara PreOrder LRO dengan rekursif disajikan berikut ini :

Procedure PreOrder (Root:Pohon);
Begin
If Root <> nil then
Begin
Write (Root^.Info);
PreOrder (Root^.kiri);
PreOrder (Root^.kanan);
End;
End;

2. Kunjungan InOrder

Kunjungan InOrder LRO atau sering disebut dengan symmetric order,menggunakan urutan sebagai berikut :

Kunjungi cabang kiri.
Cetak isi simpul yang dikunjungi.
Kunjungi cabang kanan.


Seperti pada kunjungan PreOrder, prosedur kunjungan InOrder dapat dilakukan
dengan cara rekursif atau non rekursif.
Prosedur kunjungan secara InOrder LRO dengan rekursif disajikan berikut ini :

Procedure InOrder (Root:Pohon);
Begin
If Root <> nil then
Begin
InOrder (Root^.kiri);
Write (Root^.Info);
InOrder (Root^.kanan);
End;
End;

3. Kunjungan PostOrder

Kunjungan PostOrder LRO menggunakan urutan sebagai berikut :
Kunjungi cabang kiri.
Kunjungi cabang kanan.
Cetak isi simpul yang dikunjungi.

Seperti halnya PreOrde dan InOrder, prosedur kunjungan PostOrder juga dapat
dilakukan dengan cara rekursif atau non rekursif.
Prosedur kunjungan secara PostOrder LRO dengan rekursif disajikan berikut ini :

Procedure PostOrder (Root:Pohon);
Begin
If Root <> nil then
Begin
PostOrder (Root^.kiri);
PostOrder (Root^.kanan);
Write (Root^.Info);
End;

End;

          Seperti yang telah dijelaskan pada bagian sebelumnya, instruksi atomik adalah satu atau sekelompok instruksi yang tidak dapat diberhentikan sampai instruksi tersebut selesai. Kita telah memakaiinstruksi ini pada method testAndSet. Instruksi yang dimaksud di sini adalah instruksi-instruksi padahigh-level programming, bukanlah pada tingkat instruksi mesin yang memang sudah bersifatatomik. Sebagai contoh: i++ pada suatu bahasa pemrograman akan diinterpertasikan beberapainstruksi mesin yang bersifat atomik sebagai berikut