Linked List

Linked list

Linked List merupakan istilah untuk menjelaskan tentang penyusunan objek data yang dirangkai / disusun secara linear. Di dalam linked list tidak menempatkan elemen list dalam lokasi yang berurutan di memori serta dalam linked list kapasitas penyimpanannya dapat ditambah. Jadi dalam suatu linked list minimal harus memiliki 2 bagian, yaitu bagian yang menangani data dan bagian yang menangani referensi ke elemen list berikutnya.
Di dalam ilmu komputer, linked list merupakan data struktur yang terdiri atas urutan rekor data (data records) itu seperti itu di masing-masing rekor ada bidang yang berisi surat keterangan (i.e., link) sampai ekor berikutnya di urutan.

Linked List merupakan bangunan data yang paling sederhana dan paling biasa, dan dipergunakan untuk melaksanakan banyak struktur data abstrak yang penting, seperti stacks (tumpukan-tumpukan), queues (antrian), hash tables, symbolic expressions, skip list (melewati daftar), dan banyak lagi.

Kelebihan linked list dengan array konvensional yaitu apabila perintah data yang dimaksudkan berbeda dengan perintah data yang disimpan di memori atau di disk, linked list membolehkan sisipan dan pemindahan nodes di titik yang mana pun di daftar, dengan jumlah terus-menerus pelaksanaan. Di pihak yang lain, linked list sendiri tidak membolehkan akses acak ke data, atau bentuk yang mana pun untuk mengindeks. Dengan begitu, banyak dasar pelaksanaan — seperti mendapatkan data yang terakhir dari node daftar, atau menemukan node itu berisi data yang dimasukan, atau menemukan tempat di mana node baru sebaiknya dimasukkan — mungkin diperlukan untuk memindai semua elemen daftar.

Linked List bisa dilaksanakan di kebanyakan bahasa,seperti Lisp (pelat) dan Scheme (siasat) yang menyebabkan struktur data tambahan dibuat, serta pelaksanaan sampai akses linked list. Prosedur atau bahasa yang diorientasikan dengan benda seperti C, C++, dan Java biasanya mengandalkan referensi untuk membuat linked list.

Membuat Simpul Awal

Algoritma :

Void Awal()

{

First = P;

Last = P;

P -> Link = NULL;

}

Syarat:

1. Linked list belum ada
2. Sudah ada simpul yang akan dijadikan simpul awal

4.1 Insert Simpul ke Linked List

INSERT :
KANAN/AKHIR
KIRI/AWAL
TENGAH

Syarat

1. List sudah ada
2. Sudah ada simpul yang akan ditambahkan ke Linked List

Insert Simpul ke Linked List -1

INSERT KANAN/AKHIR
Algoritma :

Void Ins_Akhir()
{

Last -> Link = P;
Last = P;
P -> Link = NULL;
}

Insert Simpul ke Linked List -2

INSERT KIRI/AWAL

Algoritma :

void Ins_Awal()

{

P -> Link = First;

First = P;

}

Insert Simpul ke Linked List -3

INSERT TENGAH

Algoritma :

void Ins_Tengah()

{

P -> Link = Q -> Link;

Q -> Link = P;

}

5.1 Delete Simpul dari Linked List

DELETE :

KANAN/AKHIR

KIRI/AWAL

TENGAH

Syarat

1. Linked list sudah ada

Delete Simpul dari Linked List -1

DELETE KANAN/AKHIR

Algoritma :

void Del_Akhir()

{

Free(last);

Last = Q;

Last -> Link = NULL;

}

5.3 Delete Simpul dari Linked List -2

DELETE KIRI/AWAL

Algoritma :

void Del_Awal()

{

Q = First;

First = Q -> Link;

free(q);

}

5.4 Delete Simpul dari Linked List -3

DELETE TENGAH

Algoritma :

void Del_Tengah()

{

R = Q -> Link ;

Q -> Link = R -> Link;

free(R);

}

Pembuatan Single Linked List dapat menggunakan 2 metode:

1. LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
2. FIFO (First In First Out), aplikasinya : Queue (Antrean)

LIFO ( Last In First Out)

Lifo adalah suatu metode pembuatan Linked List di mana data yang masuk paling akhir adalah data yang keluar paling awal. Hal ini dapat dianalogikan (dalam kehidupan sehari-hari) dengan saat Anda menumpuk barang seperti digambarkan dibawah ini. Pembuatan sebuah simpul dalam suatu linked list seperti digambarkan dibawah ini. Jika linked list dibuat dengan metode LIFO, terjadi penambahan / Insert simpul di belakang, dikenal dengan istilah INSERT.

FIFO (Fisrt In Fisrt Out)

FIFO adalah suatu metode pembuatan Linked List di mana data yang masuk paling awal adalah data yang keluar paling awal juga. Hal ini dapat di analogikan (dalam kehidupan sehari-hari), misalnya saat sekelompok orang yang datang (ENQUEUE) mengantri hendak membeli tiket di loket. Jika linked list dibuat dengan metode FIFO, terjadi penambahan / Insert simpul didepan

Operasi-Operasi yang ada pada Linked List

IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.

Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.

Find First
Fungsi ini mencari elemen pertama dari linked list

Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now

Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.

Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu\

Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.

Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.

Clear
Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.

Linear Singly dan Linear Doubly-Linked Lists

Linear Singly-Linked List
Merupakan linked list yang hanya menggunakan 1 variabel pointer saja untuk menyimpan banyak data.

Ilustrasi


Linear Doubly-Linked List
Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergeraksatu arah saja, maju/ mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, anda dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.

Linear doubly linked list adalah linked list yang menggunakan pointer ganda sehingga dapat mengatasi kelemahan yang dimiliki oleh single linked list yang hanya dapat bergerak satu arah saja.

Circular Singly dan Circular Doubly-Linked List

Circular Singly-Linked List

Circular singly linked list adalah double linked list yang simpul terakhirnya menunjuk ke simpul awal dan simpul awalnya menunjuk ke simpul akhir sehingga membentuk seperti suatu lingkaran.



Circular Doubly-Linked List

Circular doubly linked list adalah linked list yang simpul terakhirnyamenunjuk ke simpul awalnya, simpul awal menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.

Dalam Circular Doubly-Linked List , semua node berisi dan saling berhubungan ke node berikutnya, bidang hubungan kedua yang menunjuk kepada yang sebelumnya pada urutan di node. Kedua hubungan bisa maju (S) dan mundur.

nodes berisi tiga bidang: nilai bilangan bulat, bagian depan hubungan node ke yang berikutnya, dan hubungan terbelakang ke yang sebelumnya pada node.

Contoh Algoritma Doubly linked list

#include
#include

typedef struct CELL {
struct CELL *prev;
struct CELL *next;
int value;
} cell;

cell head;


/*
Nama: list_init
Fungsi: inisialisasi list
*/

void list_init()
{
head.prev=head.next=&head;
}

/*

Nama: fatal_error
Fungsi: menampilkan error message, kemudian exit
Input: error message

*/

void fatal_error(char *s)
{

fprintf(stderr,s);
exit(1);
}

/*

Nama: cell_insert
Fungsi: menambahkan sel baru ke list
Input : value dari sel yang akan ditambahkan

*/

void cell_insert(int a)
{
cell *p, *new_cell;

// Selesaikan bagian ini
}

/*
Nama: cell_delete
Fungsi: menghapus sel dari list
Input: value dari sel yang akan dihapus
*/


void cell_delete(int a)
{
cell *p;


p=head.next;
while (p!=&head && p->value != a) p=p->next;
if(p!=&head) {
p->prev->next = p->next;
p->next->prev = p->prev;
free(p);
}
else printf("Sel yang ingin dihapus tidak dapat ditemukan\n");

}
/*
Nama: print_list
Fungsi: menampilkan isi (address dan isi) list
Input: tidak ada
*/


void print_list()
{
cell *p;

printf("\n");
printf("\t\tAddressList head: %p\n",&head);
printf("\t\tIsi\t[previous cell\tcurrent cell\tnext cell]\n\t\t------------------------------------------------\n");
for(p=head.next;p!=&head;p=p->next) printf("\t\t%d\t[%p\t%p\t%p]\n",p->value,p->prev,p,p->next);
printf("\n");
}

/*
Main
*/


main()
{

int mode,value;

list_init();
printf("*****************************\n\t Doubly linked list\n*****************************\n");
printf("Pilihlah operasi yang dilakukan: 1:menambahkan sel \t2:menghapus sel \t3:selesai\t");
while(scanf("%d",&mode)){
switch(mode){
case 1: printf("Operasi yang dipilih�Fmenambahkan sel\n");
printf("Value dari sel yang akan ditambahkan: \t");
scanf("%d",&value);
cell_insert(value);

break;
case 2: printf("Operasi yang dipilih�Fmenghapus sel\n");
printf("Value dari sel yang akan dihapus: \t");
scanf("%d",&value);
cell_delete(value);
break;
case 3: exit(0);
default: break;
}
print_list();
printf("Pilihlah operasi yang dilakukan: 1:menambahkan sel \t2:menghapus sel \t3:selesai\t");

}
}


Contoh Algoritma linear singly linked list

#include
#include

struct CELL {
struct CELL *next;
int value;
};

typedef struct CELL cell; // selanjutnya deklarasi sel cukup dengan "cell", tidak perlu menulis lengkap "struct CELL"

cell header;

/*
Nama fungsi: fatal_error
Fungsi: menampilkan error message, kemudian exit
Input: error message
*/

void fatal_error(char *s)
{

fprintf(stderr,s);
exit(1);
}

/*
Nama fungsi: cell_insert
Fungsi: menambahkan sel baru ke linked list
Input: value (nilai) sel yang ingin dimasukkan
*/

void cell_insert(int a)
{
cell *p, *q, *new_cell;

p=header.next;
q=&header;

while((p!=NULL)&&(p->value
q=p;
p=p->next;
}
if((new_cell=(cell*)malloc(sizeof(cell)))==NULL) fatal_error("memory tidak cukup");
new_cell->next = p;
q->next = new_cell;
new_cell->value = a;

}

/*
Nama fungsi: cell_delete
Fungsi: menghapus sebuah sel yang memiliki nilai tertentu
Input: value (nilai) sel yang ingin dihapus
*/


void cell_delete(int a)
{
cell *p, *q;

p=header.next;
q=&header;

// selesaikan bagian ini

}

/*
Nama fungsi: print_list
Fungsi: menampilkan value semua sel pada sebuah list
Input: tidak ada
*/


void print_list()
{
cell *p;

printf("\n");
printf("\t\tAddress\t\tvalue\n\t\t------------------------\n");
for(p=header.next;p!=NULL;p=p->next) printf("\t\t%p\t%d\n",p,p->value);
printf("\n");
}

/*
Main function
*/


main()
{

int mode,value;

printf("*****************************\n\t LINKED LIST \n*****************************\n");
printf("Pilihlah operasi yang ingin dilakukan: 1.memasukkan sel baru 2.menghapus sel 3.selesai\t");
while(scanf("%d",&mode)){
switch(mode){
case 1: printf("Operasi yang dipilih: memasukkan sel baru");
printf("Value sel yang ingin dimasukkan ? \t");
scanf("%d",&value);
cell_insert(value);
break;
case 2: printf("Operasi yang dipilih: menghapus sel\n");
printf("Value sel yang ingin dihapus\t");
scanf("%d",&value);
cell_delete(value);
break;
case 3: exit(0);
default: break;
}
print_list();
printf("Pilihlah operasi yang ingin dilakukan: 1.memasukkan sel baru 2.menghapus sel 3.selesai\t");
}
}