LINGKED LIST (NON CIRCULAR)

,

LINKED LIST

(NON CIRCULAR)

Linked list

• Daftar item tertaut diatur secara berurutan

• Ukuran perubahan daftar yang ditautkan sebagai item

disisipkan atau dihapus

• Alokasi memori dinamis sering digunakan

dalam implementasi daftar terkait

• Sepuluh fungsi dasar digunakan

memanipulasi daftar tertaut (lihat buku teks).

Definisi Linked

List Pengolahan data yang kita lakukan menggunakan komputer seringkali mirip dengan ilustrasi di atas, yang antara lain berupa penyimpanan data dan pengolahan lain dari sekelompok data yang telah terorganisir dalam sebuah urutan tertentu. Salah satu cara untuk menyimpan sekumpulan data yang kita miliki adalah menggunakan larik. Telah kita bicarakan dalam Bab 1, keuntungan dan kerugian pemakaian larik untuk menyimpan sekelompok data yang banyaknya selalu berubah dan tidak diketahui dengan pasti kapan penambahan atau penghapusan akan berakhir

Fundamental

• Daftar tertaut adalah urutan item yang diatur satu

sesudah yang lain.

• Setiap item dalam daftar terhubung ke item berikutnya melalui a

Link

• Setiap item ditempatkan bersama dengan tautan ke

item berikutnya, menghasilkan komponen sederhana yang disebut a

simpul.

Mendeklarasikan Kelas untuk Node

struct Node

{

               typedef ganda Item;

               Data barang; // data disimpan dalam node

               Tautan Node *; // arahkan ke simpul berikutnya

};

Sebuah struct adalah jenis kelas khusus di mana semua anggotanya berada

publik. Dalam hal ini ada dua anggota masyarakat

variabel: data, tautan.

Setiap kali sebuah program perlu merujuk ke jenis barang, kami

dapat menggunakan ekspresi Node :: Item.

Kepala Pointer, Tail Pointer

Biasanya, program tidak benar-benar menyatakan

variabel node. Sebaliknya, daftar itu diakses

melalui satu atau lebih pointer ke node.

Struct Node

{

typedef ganda Item;

Data barang;

Tautan Node *;

};

Node * head_ptr;

Node * tail_ptr;

Single linked list

• Simpul terakhir dalam daftar tertaut tidak

arahkan ke simpul berikutnya.

• Jika tautan tidak menunjuk ke suatu simpul, nilainya adalah

diatur ke NULL.

• NULL adalah konstanta C ++ khusus, dari

fasilitas perpustakaan standar <stdlib.h>

• Penanda NULL sering ditulis 0 (nol).

Penggunaan penunjuk NULL di node terhubung terakhir

daftar:

Untuk mengakses elemen dalam linked list, dimulai dari head dan menggunakan pointer next dari elemen selanjutnya untuk berpindah dari elemen ke elemen berikutnya sampai elemen yang diminta dicapai. Dengan single linke list, list dapat dilintasi hanya satu arah dari head ke tail karena masing-masing elemen tidak terdapat link dengan elemen sebelumnya. Sehingga, apabila kita mulai dari head dan berpindah ke beberapa elemen dan berharap dapat mengakses elemen sebelumnya, kita harus mulai dari head.

Secara konseptual, linked list merupakan deretan elemen yang berdampingan. Akan tetapi, karena elemen-elemen tersebut dialokasikan secara dinamis (menggunakan malloc), sangat penting untuk diingat bahwa kenyataannya, linked list akan terpencarpencar di memori Pointer dari elemen ke elemen berarti sebagai penjamin bahwa semua elemen dapat diakses.

Alokasi Simpul

Ketika sebuah variabel dideklarasikan, terlebih dahulu harus diinisialisasi. Demikian juga dengan pengalokasian secara dinamis. Sehingga, fungsi untuk mengalokasikan sebuah node baru, fungsi allocate_node() menggunakan malloc() untuk mendapatkan memori aktual, yang akan menginisialisasi suatu field data. next selalu diinisialisasi sebagai NULL.

 Untuk melihat kemungkinan alokasi memori gagal, maka fungsi allocate_node menghasilkan 0, bila berhasil maka menghasilkan 1. Untuk membebaskan node digunakan fungsi free_node. Fungsi dari alokasi node adalah sebagai berikut :

int allocate_node(int data, list *new)

{

new = (list) malloc (sizeof(node));

if(new==NULL)

return 0;

new->datalist = data;

new->next=NULL;

return 1;

}

Memasukkan Node di List Head

Void list_head_insert (Node * head_ptr, const Node :: Item & entri)

{

// Prekondisi: head_ptr adalah penunjuk kepala ke daftar tertaut

// Postcondition: node baru ditambahkan ke depan daftar yang berisi entri, dan

// head_ptr diatur ke titik di node baru.

Node *insert_ptr;

insert_ptr = new Node;

insert_ptr->data = entry; 

insert_ptr->link = head_ptr; 

head_ptr = insert_ptr; }

Mencari Daftar untuk Item

Node* list_search(Node* head_ptr, const Node::Item& target) 

{ 

// Prekondisi: head_ptr adalah penunjuk kepala ke daftar tertaut

// Postcondition: nilai kembalian adalah pointer ke node pertama yang berisi

// target yang ditentukan. Mengembalikan NULL jika tidak ditemukan simpul yang cocok.

Node *cursor; 

for(cursor = head_ptr; cursor != NULL; cursor = cursor->link) 

               if(target == cursor->data) 

                               return cursor; 

return NULL; 

}

Menghapus Node di List Head

void list_head_remove(Node* head_ptr)

{

// Prekondisi: head_ptr adalah penunjuk kepala ke daftar tertaut

// Postcondition: node pertama dihapus dari daftar depan, dan

// head_ptr diatur untuk menunjuk pada head_ptr-> tautan. Node yang dihapus dihapus

Node *remove_ptr; 

remove_ptr = head_ptr; 

head_ptr = head_ptr->link; 

delete remove_ptr; 

}

Menghapus bukan Node di List Head

void list_remove(Node* previous_ptr)

{

// Prekondisi: previous_ptr adalah pointer ke node dalam daftar tertaut

// Postcondition: node dihapus dari daftar depan, dan

// dihapus node dihapus

Node *remove_ptr;

remove_ptr = previous_ptr->link;

previous_ptr->link = remove_ptr->link;

delete remove_ptr;

}

Daftar pustaka:

Kruse and Ryba Textbook.”Lngked List” from cs.bu.edu/fac/gkollios/cs113/Slides/linkedlist.pdf

Martiana,E,K.(2009). “Senarai berantai (linked list)” from entin.lecturer.pens.ac.id