SINGLE LINKED LIST

Single linked list atau biasa disebut linked list terdiri dari elemen-elemen individu, dimana masing-masing dihubungkan dengan pointer tunggal. Masing-masing elemen terdiri dari dua bagian, yaitu bagian data/informasi yang disimpan dan bagian pointer yang disebut dengan pointer next. Dengan menggunakan struktur two-member seperti ini, linked list dibentuk dengan cara mengarahkan pointer next dari suatu elemen ke elemen yang mengikutinya seperti gambar 2.2. Pointer next pada elemen terakhir merupakan NULL, yang menunjukkan akhir dari suatu list. Elemen pada awal suatu list disebut head, dan elemen terakhir dari suatu list disebut tail.

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 linked 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 terpencar-pencar lokasinya di memori seperti Gambar 2.3. Pointer dari elemen ke elemen (pointer next) berarti sebagai penjamin bahwa semua elemen dapat diakses.

Representasi Simpul (Node)
Struktur node pada linked list merupakan suatu simpul(node) yang berisi pointer ke suatu data yang merupakan data dirinya sendiri. Model struktur dari linked list tersebut dalam C adalah sebagai berikut:
typedef struct data_int Node;
struct data_int {
int data;
Node *next;
};
Dalam hal ini, tipe Node berisi :

‰ Informasi berupa data, serta

‰ Pointer bernama next yang menunjuk ke obyek bertipe Node
dilanjutkan dengan deklarasi global dari pointer ke struktur (pointer to struct) di atas sebagai
berikut:
Node *head = NULL;
Node *p;

Dengan adanya pendeklarasian head sebagai sebuah variabel bertipe pointer yang menunjuk ke obyek bertipe Node) melalui pernyataan:
Node *head = NULL;
maka head akan berisi NULL (artinya linked list belum memiliki simpul)

Catatan : NULL adalah konstanta yang didefinisikan pada file stdio.h

Selain itu juga dideklarasikan variabel p sebagai sebuah pointer to Node juga (tanpa inisialisasi) yang akan digunakan sebagai pointer yang menunjuk kepada simpul yang akan dibuat. Pembentukan simpul pertama dilakukan melaui serangkaian pernyataan berikut :

1) p = (Node *) malloc(sizeof(Node));
2) p->data = 11511;
3) p->next = NULL;
4) head = p;

Delete Dalam single LINKED LIST

Fungsi delete pada linked list meliputi :
- delete simpul pertama (head) dari linked list
- delete setelah simpul tertentu
- delete simpul terakhir


Penghapusan Simpul Pertama:
Algoritma:
• cari node yang akan di hapus dengan node hapus
• sambung linked list dengan mengarahkan head->next=hapus->next,sehingga linked list tidak putus
• hapus data denga free(hapus) dan set hapus=NULL.


Penghapusan Setelah Simpul Tertentu
Untuk melakukan delete setelah node tertentu dari linked list diperlukan dua buah pointer bantuan berupa pointer after sebagai penanda node yang akan dihapus setelahnya dan pointer hapus untuk menandai simpul yang akan dihapus.
Alogoritma:
• cari node yang akan dihapu dengan node hapus
• cek data terakhie dengan mengeset while(hapus->next!=NULL),jika hapus next->=NULL maka delete awal, jika tidak maka terus cek hingga ketemu hapus->next=NULL.
• set prev=hapus,agar saat looping prev menyimpan alamat hapus yang sebelumnya.
• sambung Linked List dengan prev->next=NULL,lalu hapus dengan free(hapus),hapus=NULL.

Penghapusan Simpul Terakhir
Untuk melakukan delete node terakhir dari linked list diperlukan dua buah pointer bantuan berupa pointer prevhapus sebagai penanda node yang akan dihapus setelahnya dan pointer hapus untuk menandai simpul yang akan dihapus.
Algoritma:
• cari node yang akan dihapus dengan variable x
• cek dimana tempat data x,jika di awal maka delete awal,jika akhir maka delete akhir.
• jika x ketemu di tengah,tandai dengan pointer hapus dan arahkan pointer prev->next=hapus->next agar linked list tidak terputus.
• lalu hapus dengan free(hapus) dan mengeset hapus=NULL.