linked list animasi
TRANSCRIPT
Linked List
Entin Martiana
Malloc
• Memory Allocation (malloc) adalah sebuah fungsi fasilitas untuk memesan tempat secara berurutan untuk tipe data dinamis(pointer)
• Nilai balik dari memory allocation adalah void *
Problem
• Bagaimana jika kita pesan 50000 alamat berurutan?– Akan selalu gagal.– Untuk itu kita lakukan memory allocation untuk
setiap satu data.• Bagaimana agar data pertama tetap
berhubungan dengan data kedua?– Kita gunakan pointer untuk menghubungkan
The Linked List data structure
[0] [1] [2]array
A B CArray
linked
A B CLinked list
Linked lists are unbounded(maximum number of items limited only by memory)
node
Array vs Linked List
Linked lists are unbounded(maximum number of items limited only by memory)
Array : int A[3] Linked List : struct list *A;
A[2]
A[1]
A[0]
A(data 3)
A(data 2)
A(data 1)
Deklarasi
struct simpul{
char nama[25];int nrp;struct simpul *next;
};struct simpul *ujung;
nama
nrp
next
simpul
data
pointer yg menunjuk simpul lain
Membangun Linked List
Apa yang harus dilakukan?1. Deklarasi2. Memory allocation3. Mengisi data4. Menyiapkan untuk dihubungkan dengan
data baru berikutnya
Bagaimana?1. struct simpul *ujung;2. ujung=(struct simpul*)malloc(sizeof(struct simpul));3. printf("Nama :");scanf("%s",&ujung->nama);4. printf("NRP :");scanf("%d",&ujung->nrp);5. if(j==0)
{ujung->next=NULL;tampung=ujung;
} nama1
nrp1next
ujungtampung
NULL
Selanjutnya1. ujung=(struct simpul*)malloc(sizeof(struct simpul));2. printf("Nama :");scanf("%s",&ujung->nama);3. printf("NRP :");scanf("%d",&ujung->nrp);4. if(j<>0)
{ujung->next=tampung;tampung=ujung;
}
nama2
nrp2next
ujung
nama1
nrp1next NULL
tampung
nama2
nrp2next
ujung tampung
Selanjutnya1. ujung=(struct dtnilai*)malloc(sizeof(struct dtnilai));2. printf("Nama :");scanf("%s",&ujung->nama);3. printf("NRP :");scanf("%d",&ujung->nrp);4. if(j<>0)
{ujung->next=tampung;tampung=ujung;
}
nama3
nrp3next
ujung
nama1
nrp1next NULL
tampung
nama2
nrp2next
nama3
nrp3next
ujung tampung
Sampai iterasi keempat
nama1
nrp1next NULL
tampung
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
Membaca (Menampilkan)
nama1
nrp1next NULL
tampil
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
tampil = ujung;
while (tampil<>NULL)
// fungsi menampilkan
tampil = tampil -> next;
tampil tampil tampil tampil
Mencari simpul ttt.
nama1
nrp1next NULL
cari
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
cari = ujung;
while (cari->nama!=nama2)
{
cari = cari->next;
}
cari cari
Menyisipkan sebagai simpul terakhir
nama1
nrp1next
cari
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
cari = ujung
while (cari->next !=NULL)
cari = cari->next;
cari->next=baru;
namax
nrpxnext
baru
NULL
cari cari cari
NULL
Menghapus simpul ttt.
nama1
nrp1next NULL
hapus
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
hapus = ujung;
Menghapus simpul ttt.
nama1
nrp1next NULL
hapus
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
while (hapus->nama != nama2)
{
sbl = hapus;
hapus=hapus->next;
}
Menghapus simpul ttt.
nama1
nrp1next NULL
hapus
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
while (hapus->nama != nama2)
{
sbl=hapus;
hapus=hapus->next;
}
sbl
Menghapus simpul ttt.
nama1
nrp1next NULL
hapus
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
while (hapus->nama != nama2)
{
sbl=hapus;
hapus=hapus->next;
}
sbl
Menghapus simpul ttt.
nama1
nrp1next NULL
hapus
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
sbl->next=hapus->next;
sbl
Menghapus simpul ttt.
nama1
nrp1next NULL
nama3
nrp3next
nama4
nrp4next
ujung
free(hapus);
sbl
Menyisipkan setelah simpul ttt.
nama1
nrp1next NULL
cari
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
cari = ujung namax
nrpxnext
baru
Menyisipkan setelah simpul ttt.
nama1
nrp1next NULL
cari
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
while (cari->nama!=nama3)
cari = cari->next;
baru->next = cari->next;
namax
nrpxnext
baru
Menyisipkan setelah simpul ttt.
nama1
nrp1next NULL
cari
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
cari->next = baru;namax
nrpxnext
baru
Menyisipkan sebelum simpul ttt.
nama1
nrp1next NULL
cari
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
cari = ujung namax
nrpxnext
baru
Menyisipkan sebelum simpul ttt.
nama1
nrp1next NULL
stl
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
cari = ujung;
while (cari->nama!=nama1)
stl=cari;
cari=cari->next;
namax
nrpxnext
baru
cari
Menyisipkan sebelum simpul ttt.
nama1
nrp1next NULL
stl
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
cari = ujung;
while (cari->nama!=nama1)
stl=cari;
cari=cari->next;
namax
nrpxnext
baru
cari
Menyisipkan sebelum simpul ttt.
nama1
nrp1next NULL
stl
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
cari = ujung;
while (cari->nama!=nama1)
stl=cari;
cari=cari->next;
namax
nrpxnext
baru
cari
Menyisipkan sebelum simpul ttt.
nama1
nrp1next NULL
stl
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
baru->next = cari; namax
nrpxnext
baru
cari
Menyisipkan sebelum simpul ttt.
nama1
nrp1next NULL
stl
nama2
nrp2next
nama3
nrp3next
nama4
nrp4next
ujung
stl->next = baru; namax
nrpxnext
baru
cari