Double Linked List Non Circular

Double Linked List Non Circular adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut. Double Linked List Non Circular pointer next dan prev nya menunjuk ke NULL. Dengan adanya 2 pointer penunjuk, next dan prev, DLLNC sangat flexible dibandingkan dengan SLLNC.

BENTUK NODE DLLNC


Pengertian:
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.
Non-Circular : artinya pointer next dan prev-nya menunjuk ke NULL.


PEMBUATAN DOUBLE LINKED LIST NON CIRCULAR

Deklarasi node
Dibuat dari struct berikut ini:
typedef struct TNode
{
int data;
TNode *next;
Tnode *prev;
};
Penjelasan:
- Pembuatan struct bernama TNode yang berisi 3 field, yaitu field data bertipe integer dan field next & prev yang bertipe pointer dari TNode
- Setelah pembuatan struct, buat variabel haed yang bertipe pointer dari TNode yang berguna sebagai kepala linked list.

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;

- Untuk data pertama, pointer node baru yang prev dan next harus
menunjuk ke NULL

DOUBLE LINKED LIST NON CIRCULAR MENGGUNAKAN HEAD

- Menggunakan 1 pointer head
- Head selalu menunjuk node pertama


Deklarasi Pointer Head
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 LinkedList
void init()
{
head = NULL;
}

Function untuk mengetahui kosong tidaknya LinkedList
int isEmpty()
{
if(head == NULL) return 1;
else return 0;
}PENAMBAHAN DATA

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.
-
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 linked list void tampil() { TNode *bantu; bantu = head; if(isEmpty()==0) { while(bantu!=NULL) { cout<data<<" "; bantu=bantu->next;
}
cout<next != NULL)
{
hapus = head;
d = hapus->data;
head = head->next;
head->prev = NULL;
delete hapus;
}
else
{
d = head->data;
head = NULL;
}
cout<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<next;
delete hapus;
}
head = NULL;
}

DOUBLE LINKED LIST NON CIRCULAR MENGGUNAKAN 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 LinkedList
int isEmpty()
{
if(tail == NULL) return 1;
else return 0;
}

Pengkaitan node baru ke linked list di depan
Penambahan 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.
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<data<<" "; bantu=bantu->next;
}
cout<next != NULL)
{
hapus = head;
d = hapus->data;
head = head->next;
head->prev = NULL;
delete hapus;
}
else
{
d = head->data;
head = NULL;
tail = NULL;
}
cout<next != NULL)
{
hapus = tail;
d = tail->data;
tail = tail->prev;
tail->next = NULL;
delete hapus;
} else
{
d = head->data;
head = NULL;
tail = NULL;
}
cout<next;
delete hapus;
}
head = NULL;
tail = NULL;
}