linked list animasi

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