Single Linked List merupakan modul ADT dari linked list yang hanya memiliki satu arah pointer.
List terdiri dari beberapa elemen yang saling berkaitan
suatu elemen pada single linked list memiliki bagian-bagian seperi berikut
info/data : berisikan info dari elemen tersebut
next : pointer sebagai penunjuk alamat elemen di depannya
gambar list pada single 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 elemen terakhir, next nya di assign dengan NULL
ADT
operasi-operasi ADT pada linked list
create list
alokasi data/info
insert ( insert first, insert last, insert after)
delete (delete first, delete last, delete after)
searching
print list
sekarang kita akan membuat ADT tipe data pada single linked list
(pseudocode version / versi algoritma)
------ single linked list dengan last -------
type address : pointer to elmList
type elmList : < info : int
next : address >
type List : < first : address
last : address >
------ single linked list tanpa last --------
type address : pointer to elmList
type elmList : < info : int
next : address >
type List : < first : address >
------ fungsi - prosedur single linked list ------------
keterangan:
*proc : prosedur
*funct : fungsi
*I : input
*O : output
*I/O : input output
* first(L) = L.first
* next(p) = p->next
* 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
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)
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
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
else
first(L) = p
--- insert after ----
proc insertAfter (I/O L:list, prec:address, p:address)
kamus data: -
algoritma:
next(p) = next(prec)
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
--- delete last dengan last ----
proc deleteLast (I/O L:List, O p:address)
kamus data:
q : address
algoritma:
if (first(L) != NULL) then
q = first(L)
while (next(q) != last(L)) do
q = next(q)
p = last(L)
next(q) = NULL
--- delete last tanpa last ----
proc deleteLast (I/O L:List, O p:address)
kamus data:
q : address
algoritma:
if (first(L) != NULL) then
q = first(L)
while (next(next(q)) != NULL) do
q = next(q)
p = next(q)
next(q) = NULL
--- delete after ----
proc deleteAfter (I/O L:list, I prec:address, O p:address)
kamus data: -
algoritma:
if (first(L) != NULL) then
p = next(prec)
next(prec) = next(p)
