Double Link List adalah elemen-elemen yang
dihubungkan dengan dua pointer dalam satu elemen dan list dapat melintas baik
di depan atau belakang.
Elemen double link list terdiri dari tiga
bagian:
- Bagian data informasi
- Pointer next yang menunjuk ke elemen
berikutnya
- Pointer prev yang menunjuk ke elemen
sebelumnya
Untuk menunjuk head dari double link list,
pointer prev dari elemen pertama menunjuk NULL. Sedangkan untuk menunjuk tail,
pointer next dari elemen terakhir menunjuk NULL.
Contoh Membuat TDA(Tipe Data Abstrak) dari
Double Linked Circular List tersebut.
Instan :
Double Linked Circular List
Operasi :
Buat_node(char x) : membuat node baru
dengan informasi x
Tambah_elemen_didepan() : menambah elemen
paling depan (pointernya menunjuk
elemen pertama link list)
Tambah_elemen_dibelakang() : menambah
elemen paling belakang (pointer elemen
yang baru menunjuk elemen pertama)
Hapus_elemen_() : Menghapus elemen
(pointer menunjuk elemen yang akan dihapus)
Cetak () : menelusuri elemen satu demi dan
menampilkan informasinya.
Ada 2 jenis Double Linked List yaitu :
•
Double Linked List Circular
•
Double Linked List Non Circular
1.
Double Linked List Circular
Pengertian secara umumnya DLLC itu Linked
list yang menggunakan pointer, dimana setiap node memiliki 3 field, yaitu:
1 field pointer yang menunjuk pointer
berikutnya “next“,
1 field menunjuk pointer sebelumnya ” prev
“,
1 field yang berisi data untuk node
tersebut .
Double Linked List Circular pointer next
dan prev nya menunjuk kedirinya sendiri secara circular. Bentuk Node DLLC
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 nilai NULL
Selanjutnya pointer prev akan menunjuk ke
node sebelumnya , dan pointer next akan menunjuk ke node selanjutnya pada list.
2.
Double Linked List Non Circular
DLLNC "Double linked list non
circular" adalah Double Linked List yang memiliki 2 buah pointer yaitu
pointer next dan prev.
Pointer next menunjuk pada node setelahnya
dan pointer prev menunjuk pada node sebelumnya.
Pengertian:
Double : artinya field pointer-nya dua
buah dan dua arah, ke node sebelum dan sesudahnya.
Linked List : artinya node-node tersebut
saling terhubung satu sama lain.
Non Circular : artinya pointer prev dan
next-nya akan menunjuk padaNULL.
Ilustrasi DLLNC
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 nilai NULL
Selanjutnya pointer prev akan menunjuk ke
node sebelumnya , dan pointer next akan menunjuk ke node selanjutnya pada list.
Deklarasi dan node baru DLLNC
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 = NULL;
baru -> prev = NULL;
Berikut saya lampirkan satu contohnya:
#include <iostream>
using namespace std;
template <class T>
struct Node
{
T data;
Node * next;
Node(T data) : data(data), next(NULL) {}
};
template <class T>
class CircularLinkedList
{
public:
CircularLinkedList() : head(NULL) {}
~CircularLinkedList();
void addNode(T data);
void deleteNode(T data);
template <class U>
friend std::ostream & operator<<(std::ostream & os, const
CircularLinkedList<U> & cll);
private:
Node<T> * head;
};
template <class T>
CircularLinkedList<T>::~CircularLinkedList()
{
if (head)
{
Node<T> * tmp = head;
while (tmp->next != head)
{
Node<T> * t = tmp;
tmp = tmp->next;
delete(t);
}
delete tmp;
head = NULL;
}
}
template <class T>
void
CircularLinkedList<T>::addNode(T data)
{
Node<T> * t = new Node<T>(data);
if (head == NULL)
{
t->next = t;
head = t;
return;
}
Node<T> * tmp = head;
while (tmp->next != head)
{
tmp = tmp->next;
}
tmp->next = t;
t->next = head;
}
template <class T>
void
CircularLinkedList<T>::deleteNode(T data)
{
Node<T> * tmp = head;
Node<T> * prev = NULL;
while (tmp->next != head)
{
if (tmp->data == data) break;
prev = tmp;
tmp = tmp->next;
}
if (tmp == head)
{
while (tmp->next != head)
{
tmp = tmp->next;
}
tmp->next = head->next;
delete head;
head = tmp->next;
}
else
{
prev->next = tmp->next;
delete tmp;
}
}
template <class U>
std::ostream &
operator<<(std::ostream & os, const CircularLinkedList<U> &
cll)
{
Node<U> * head = cll.head;
if (head)
{
Node<U> * tmp = head;
while (tmp->next != head)
{
os << tmp->data << " ";
tmp = tmp->next;
}
os << tmp->data;
}
return os;
}
int main()
{
CircularLinkedList<int> cll;
cll.addNode(1);
cll.addNode(2);
cll.addNode(3);
cll.addNode(4);
cll.addNode(5);
cout << cll << endl;
cll.deleteNode(3);
cll.deleteNode(1);
cll.deleteNode(5);
