1

Pertemuan 4Doubly Linked List

Matakuliah : T0026/Struktur DataTahun : 2005Versi : 1/1

2

Learning Outcomes

Pada akhir pertemuan ini, diharapkan mahasiswa akan mampu :• Mahasiswa dapat menghasilkan program

modular dengan doubly linked list

3

Outline Materi

• Pengertian doubly linked list• Deklarasi node doubly LL• Operasi-operasi doubly linked list• contoh program doubly linked list• insert data dalam doubly LL• delete data dalam doubly LL

4

Abstract Model of a List Object

fro n t b ack

5

Circular Doubly Linked Lists

• Implemented on a Computer it might look something like this.

head er23 4 9

The 4 node is the front() node & the 2 node is the back() node

begin() returns an iterator to the 4 node

end() returns an iterator to he header node

6

Updating a Doubly Linked List

p r e v n e x t

head er

B efo re In s ert : E m p t y lis t

p r e v n e x t

head er

n ew N o d e

A ft er Iin s ert : L is t w it h o n e elem en t

7

Inserting a Node at a Position

ne xt pre v

pre vN ode = c urr -> pre vp rev item n ex t

143 2 c ur r

n ew N o d e// insert newNode before curr

newNode->prev = curr->prev;newNode->next = curr;curr->prev->next = newNode;curr->prev = newNode;

8

Deleting a Node at a Position

pre v ne xt

s uc c N o de = c urr->ne xt

1

2

//////

//

pre vN o de = c ur r->pre v c ur r

// unlink the node (*curr) from the list

curr->prev->next = curr->next;curr->next->prev = curr->prev;

delete curr;

99 Main Index Contents

Deleting a Node at a Position

pre v ne xt

s uc c N o de = c ur r->ne xt

1

2

//////

//

pre vN o de = c ur r->pre v c ur r

// unlink the node (*curr) from the list

curr->prev->next = curr->next;curr->next->prev = curr->prev;

delete curr;