struktur double linked list hampir sama dengan single linked list, hanya yang membedakan double linked list memiliki dua arah pointer, yaitu next dan prev
gambar list double linked list
dari gambar diatas, sebuah list memiliki
pointer first : untuk menunjuk alamat dari elemen pertama sebuah list
pointer last : untuk menunjuk alamat dari elemen terakhir sebuah list ( ada juga list yang tidak memiliki last )
setiap next dari elemen menunjuk ke elemen di depannya
setiap prev dari elemen menunjuk elemen sebelumnya
setiap elemen terakhir, next nya di assign dengan NULL
setiap elemen pertama, prev nya di assign dengan NULL
ADT
ADT double linked list juga hampir mirip dengan single, hanya penambahan pointer prev saja yang membedakan
sekarang kita akan membuat ADT tipe data pada double linked list
(pseudocode version / versi algoritma)
------ double linked list dengan last -------
type address : pointer to elmList
type elmList : < info : int
next : address
prev : address >
type List : < first : address
last : address >
------ single linked list tanpa last --------
type address : pointer to elmList
type elmList : < info : int
next : address
prev : address >
type List : < first : address >
------ fungsi - prosedur double linked list ------------
keterangan:
*proc : prosedur
*funct : fungsi
*I : input
*O : output
*I/O : input output
* first(L) = L.first
* next(p) = p->next
* prev(p) = p->prev
* info(p) = p->info
--- create list ----
proc CreateList (I/O L : List)
kamus data : -
algoritma:
first(L) = NULL
--- alokasi data/info ----
funct Alokasi (data: int) → address
kamus data :
p : address
algoritma:
p = new elmList
info(p) = data
next(p) = NULL
prev(p) = NULL
return p
--- insert first ----
proc insertFirst (I/O L:List, I p:address)
kamus data: -
algoritma:
if (first(L) == NULL) then
first(L) = p
else
next(p) = first(L)
prev(first(L)) = p
first(L) = p
--- insert Last dengan last ----
proc insertLast (I/O L:List, I p:address)
kamus data: -
algoritma:
if (first(L) != NULL) then
next(last(L)) = p
prev(p) = last(L)
last(L) = p
else
first(L) = p
--- insert last tanpa last ----
proc insertLast (I/O L:List, I p:address)
kamus data:
q:address
algoritma:
if (first(L) != NULL) then
q = first(L)
while (next(q) != NULL) do
q = next(q)
next(q) = p
prev(p) = q
else
first(L) = p
--- insert after ----
proc insertAfter (I/O L:list, prec:address, p:address)
kamus data: -
algoritma:
next(p) = next(prec)
prev(p) = prec
prev(next(prec)) = p
next(prec) = p
--- delete first ----
proc deleteFirst (I/O L:List, O p:address)
kamus data : -
algoritma:
if (first(L) != NULL) then
p = first(L)
first(L) = next(p)
next(p) = NULL
