double linked list

67
Double Linked List Entin Martiana

Upload: gita

Post on 31-Jan-2016

52 views

Category:

Documents


0 download

DESCRIPTION

Double Linked List. Entin Martiana. Operasi Double Linked List. Membangun Double Linked List Membaca list, dalam dua arah. Mencari simpul tertentu Menghapus simpul tertentu Menyisipkan sebagai simpul pertama Menyisipkan simpul di tengah. Double Linked List. 0. 1. 2. 3. 4. tail. - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: Double Linked List

Double Linked List

Entin Martiana

Page 2: Double Linked List

Operasi Double Linked List

• Membangun Double Linked List

• Membaca list, dalam dua arah.dalam dua arah.

• Mencari simpul tertentu

• Menghapus simpul tertentu

• Menyisipkan sebagai simpul pertama

• Menyisipkan simpul di tengah

Page 3: Double Linked List

Double Linked List

head

0 1 2 3 4

tail

Page 4: Double Linked List

Deklarasi

struct simpul{

char nama[25];int nrp;struct simpul *before;struct simpul *next;

};

struct simpul *baru;

nama

nrp

before

simpul

data

pointer yg menunjuk simpul sebelumnya

nextpointer yg menunjuk simpul berikutnya

Page 5: Double Linked List

Membangun Linked List

Apa yang harus dilakukan?

1. Deklarasi

2. Memory allocation

3. Mengisi data

4. Menyiapkan untuk dihubungkan dengan data baru berikutnya

Page 6: Double Linked List

Bagaimana?

1. struct simpul *baru;

2. baru=(struct simpul*)malloc(sizeof(struct simpul));

3. printf("Nama :");scanf("%s",&baru->nama);

4. printf("NRP :");scanf("%d",&baru->nrp);

5. if(pertama)

{

baru->before=NULL;

nama1

nrp1

before

baru

nama1

nrp1

before

baru

next

next

NULL

Page 7: Double Linked List

Bagaimana?

1. struct simpul *baru;

2. baru=(struct simpul*)malloc(sizeof(struct simpul));

3. printf("Nama :");scanf("%s",&baru->nama);

4. printf("NRP :");scanf("%d",&baru->nrp);

5. if(pertama)

{

baru->before=NULL;

baru->next=NULL;

nama1

nrp1

before

NULL

baru

nama1

nrp1

before

baru

next

next

NULL

Page 8: Double Linked List

Bagaimana?

1. struct simpul *baru;

2. baru=(struct simpul*)malloc(sizeof(struct simpul));

3. printf("Nama :");scanf("%s",&baru->nama);

4. printf("NRP :");scanf("%d",&baru->nrp);

5. if(pertama)

{

baru->before=NULL;

baru->next=NULL;

head=baru;

nama1

nrp1

before

NULL

head

nama1

nrp1

before

baru

next

next

NULL

baru

Page 9: Double Linked List

Bagaimana?

1. struct simpul *baru;

2. baru=(struct simpul*)malloc(sizeof(struct simpul));

3. printf("Nama :");scanf("%s",&baru->nama);

4. printf("NRP :");scanf("%d",&baru->nrp);

5. if(pertama)

{

baru->before=NULL;

baru->next=NULL;

head = baru;

tail = baru;

}

nama1

nrp1

before

NULL

head

nama1

nrp1

before

baru

next

next

NULL

barutail

Page 10: Double Linked List

Selanjutnya

1. baru=(struct simpul*)malloc(sizeof(struct simpul));

2. printf("Nama :");scanf("%s",&baru->nama);

3. printf("NRP :");scanf("%d",&baru->nrp);

4. if(bukanpertama)

{

baru->next=NULL;

nama2

nrp2

before

NULL

baru

nama1

nrp1

before

head

nama2

nrp2

before

baru

next

next nextNULL

NULL

tail

Page 11: Double Linked List

Selanjutnya

1. baru=(struct simpul*)malloc(sizeof(struct simpul));

2. printf("Nama :");scanf("%s",&baru->nama);

3. printf("NRP :");scanf("%d",&baru->nrp);

4. if(bukanpertama)

{

baru->next=NULL;

tail->next=baru;

nama2

nrp2

before

NULL

baru

nama1

nrp1

before

head

nama2

nrp2

before

baru

next

next nextNULL

tail

Page 12: Double Linked List

Selanjutnya

1. baru=(struct simpul*)malloc(sizeof(struct simpul));

2. printf("Nama :");scanf("%s",&baru->nama);

3. printf("NRP :");scanf("%d",&baru->nrp);

4. if(bukanpertama)

{

baru->next=NULL;

tail->next=baru;

baru->before=tail;

nama2

nrp2

before

NULL

baru

nama1

nrp1

before

head

nama2

nrp2

before

baru

next

next nextNULL

tail

Page 13: Double Linked List

Selanjutnya

1. baru=(struct simpul*)malloc(sizeof(struct simpul));

2. printf("Nama :");scanf("%s",&baru->nama);

3. printf("NRP :");scanf("%d",&baru->nrp);

4. if(j<>0)

{

baru->next=NULL;

tail->next=baru;

baru->before=tail;

tail=baru;

}

nama2

nrp2

before

NULL

tail

nama1

nrp1

before

head

nama2

nrp2

before

baru

next

next nextNULL

Page 14: Double Linked List

Sampai iterasi keempat

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

Page 15: Double Linked List

Membaca (FIFO)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

bacaFIFO = head;

bacaFIFO

Page 16: Double Linked List

Membaca (FIFO)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

while (bacaFIFO!=NULL)

// fungsi menampilkan

bacaFIFO = bacaFIFO -> next;

bacaFIFO

Page 17: Double Linked List

Membaca (FIFO)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

while (bacaFIFO!=NULL)

// fungsi menampilkan

bacaFIFO = bacaFIFO -> next;

bacaFIFO

Page 18: Double Linked List

Membaca (FIFO)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

while (bacaFIFO!=NULL)

// fungsi menampilkan

bacaFIFO = bacaFIFO -> next;

bacaFIFO

Page 19: Double Linked List

Membaca (FIFO)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

while (bacaFIFO<>NULL)

// fungsi menampilkan

bacaFIFO = bacaFIFO -> next;

bacaFIFO

Page 20: Double Linked List

Membaca (LIFO)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

bacaLIFO = tail;

bacaLIFO

Page 21: Double Linked List

Membaca (LIFO)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

while (bacaLIFO<>NULL)

// fungsi menampilkan

bacaLIFO = bacaLIFO -> before;

bacaLIFO

Page 22: Double Linked List

Membaca (LIFO)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

while (bacaLIFO<>NULL)

// fungsi menampilkan

bacaLIFO = bacaLIFO -> before;

bacaLIFO

Page 23: Double Linked List

Membaca (LIFO)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

while (bacaLIFO<>NULL)

// fungsi menampilkan

bacaLIFO = bacaLIFO -> before;

bacaLIFO

Page 24: Double Linked List

Membaca (LIFO)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

while (bacaLIFO<>NULL)

// fungsi menampilkan

bacaLIFO = bacaLIFO -> before;

bacaLIFO

Page 25: Double Linked List

Mencari Simpul Tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

cari = head;

cari

Page 26: Double Linked List

Mencari Simpul Tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

while (cari->nama!=nama3)

cari = cari -> next;

cari

Page 27: Double Linked List

Mencari Simpul Tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

while (cari->nama!=nama3)

cari = cari -> next;

cari

Page 28: Double Linked List

Mencari Simpul Tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

while (cari->nama!=nama3)

cari = cari -> next;

cari

Page 29: Double Linked List

Menghapus Simpul Tertentu (Simpul Depan)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

cari = head;

cari

Page 30: Double Linked List

Menghapus Simpul Tertentu (Simpul Depan)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

cari = head;

if(cari->nama==nama1)

head=head->next;

cari

Page 31: Double Linked List

Menghapus Simpul Tertentu (Simpul Depan)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

cari = head;

if(cari->nama==nama)

head=head->next;

head->before=NULL;

cari NULL

Page 32: Double Linked List

Menghapus Simpul Tertentu (Simpul Depan)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

cari = head;

if(cari->nama==nama)

head=head->next;

head->before=NULL;

free(cari);

cari NULL

Page 33: Double Linked List

Menghapus Simpul Tertentu (Simpul Depan)

nama4

nrp4

before

NULL

tailhead

next

nama2

nrp2

before

next

nama3

nrp3

before

next

cari = head;

if(cari->nama==nama)

head=head->next;

head->before=NULL;

free(cari);

NULL

Page 34: Double Linked List

Menghapus Simpul Tertentu (Simpul Akhir)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

cari=tail;

cari

Page 35: Double Linked List

Menghapus Simpul Tertentu (Simpul Akhir)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

tail=tail->before;

cari

Page 36: Double Linked List

Menghapus Simpul Tertentu (Simpul Akhir)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

tail=tail->before;

tail->next=NULL;

cari

Page 37: Double Linked List

Menghapus Simpul Tertentu (Simpul Akhir)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

tail=tail->before;

tail->next=NULL;

free(cari);

cari

Page 38: Double Linked List

Menghapus Simpul Tertentu (Simpul Akhir)

NULL

tail

nama1

nrp1

before

head

next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

Page 39: Double Linked List

Menghapus Simpul Tertentu (Di Tengah)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

cari=head;

cari

Page 40: Double Linked List

Menghapus Simpul Tertentu (Di Tengah)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

while (cari->nama!=nama3)cari = cari -> next;

cari

Page 41: Double Linked List

Menghapus Simpul Tertentu (Di Tengah)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

while (cari->nama!=nama3)cari = cari -> next;

cari

Page 42: Double Linked List

Menghapus Simpul Tertentu (Di Tengah)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

while (cari->nama!=nama3)cari = cari -> next;

cari

Page 43: Double Linked List

Menghapus Simpul Tertentu (Di Tengah)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

cari->before->next=cari->next;

cari

Page 44: Double Linked List

Menghapus Simpul Tertentu (Di Tengah)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

cari->next->before=cari->before;

cari

Page 45: Double Linked List

Menghapus Simpul Tertentu (Di Tengah)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

free(cari);

cari

Page 46: Double Linked List

Menghapus Simpul Tertentu (Di Tengah)

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

nextNULL

Page 47: Double Linked List

atau

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

while (cari->nama!=nama3)

cari = cari -> next;

sbl=cari->before;

stl=cari->next;

carisbl stl

Page 48: Double Linked List

Menghapus Simpul Tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

sbl->next=stl;

carisbl stl

Page 49: Double Linked List

Menghapus Simpul Tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

sbl->next=stl; stl->before=sbl;

carisbl stl

Page 50: Double Linked List

Menghapus Simpul Tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

nextNULL

cari->before->next = cari->next;

cari->next->before = cari->before;

free(cari);

Page 51: Double Linked List

Menyisipkan sebagai simpul pertama

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

namax

nrpx

before

sisip

next

Page 52: Double Linked List

Menyisipkan sebagai simpul pertama

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

namax

nrpx

before

sisip

next

sisip->before=NULL;

NULL

Page 53: Double Linked List

Menyisipkan sebagai simpul pertama

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

namax

nrpx

before

sisip

next

sisip->next=head;

NULL

Page 54: Double Linked List

Menyisipkan sebagai simpul pertama

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

next

namax

nrpx

before

sisip

next

head->before=sisip;

NULL

Page 55: Double Linked List

Menyisipkan sebagai simpul pertama

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

next

namax

nrpx

before

sisip

next

head=sisip;

NULL

Page 56: Double Linked List

Menyisipkan stl. simpul tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

namax

nrpx

before

sisip

next

Page 57: Double Linked List

Menyisipkan stl. simpul tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

namax

nrpx

before

sisip

next

stl=head;

while(stl->nama!=nama3)

stl=stl->next;

stl

Page 58: Double Linked List

Menyisipkan stl. simpul tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

namax

nrpx

before

sisip

next

sisip->before=stl;

stl

Page 59: Double Linked List

Menyisipkan stl. simpul tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

namax

nrpx

before

sisip

next

sisip->before=stl;

sisip->next=stl->next;

stl

Page 60: Double Linked List

Menyisipkan stl. simpul tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

namax

nrpx

before

sisip

next

sisip->before=stl;

sisip->next=stl->next;

stl->next->before=sisip;

stl

Page 61: Double Linked List

Menyisipkan stl. simpul tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

namax

nrpx

before

sisip

next

sisip->before=stl;

sisip->next=stl->next;

stl->next->before=sisip;

stl->next=sisip;

stl

Page 62: Double Linked List

Menyisipkan sbl. simpul tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

namax

nrpx

before

sisip

next

Page 63: Double Linked List

Menyisipkan sbl. simpul tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

namax

nrpx

before

sisip

next

sbl=head;

while(sbl->nama!=nama3)

sbl=sbl->next;

sbl

Page 64: Double Linked List

Menyisipkan sbl. simpul tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

namax

nrpx

before

sisip

next

sisip->next=sbl;

sbl

Page 65: Double Linked List

Menyisipkan sbl. simpul tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

namax

nrpx

before

sisip

next

sisip->next=sbl;

sisip->before=sbl->before;

sbl

Page 66: Double Linked List

Menyisipkan sbl. simpul tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

namax

nrpx

before

sisip

next

sisip->next=sbl;

sisip->before=sbl->before;

sbl->before->next=sisip;

sbl

Page 67: Double Linked List

Menyisipkan sbl. simpul tertentu

nama4

nrp4

before

NULL

tail

nama1

nrp1

before

head

next next

nama2

nrp2

before

next

nama3

nrp3

before

nextNULL

namax

nrpx

before

sisip

next

sisip->next=sbl;

sisip->before=sbl->before;

sbl->before->next=sisip;

sbl->before=sisip;

sbl