LINKED LIST

LINKED LIST

Array merupakan variable yang bersifat statis (ukuran dan urutannya sudah pasti).
Selain itu, ruang memori yang dipakai olehnya tidak dapat dihapus bila array tersebut sudah tidak digunakan lagi pada saat program dijalankan.
Untuk memecahkan masalah di atas, kita dapat menggunakan variabel pointer. Tipe data pointer bersifat dinamis, variabel akan dialokasikan hanya pada saat dibutuhkan dan sesudah tidak dibutuhkan dapat direlokasikan kembali. Setiap ingin menambahkan data, Anda selalu menggunakan variabel pointer yang baru, akibatnya Anda akan membutuhkan banyak sekali pointer.
Oleh karena itu, ada baiknya jika Anda hanya menggunakan satu variabel pointer saja untuk menyimpan banyak data dengan metode yang kita sebut Linked List. Linked list adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian. Linked adalah koleksi obyek heterogen dengan sifat setiap obyek (kecuali obyek terakhir) mempunyai penerus dan setiap obyek (kecuali obyek pertama) mempunyai pendahulu. Salah satu penggunaan pointer adalah untuk membuat linked list atau senarai berantai. Linked list sendiri dapat diartikan sebagai sekumpulan komponen yang saling berhubungan (berantai) dengan bantuan pointer. Perhatikan ilustrasi berikut untuk lebih jelasnya.


Linier Linked List
merupakan setiap node yang mempunyai pointer dimana menunjuk ke simpul berikutnya sehingga membentuk suatu rantaian / untaian, dengan demikian hanya diperlukan sebuah variable pointer. Pembuatan single linked list dapat menggunakan 2 metode yaitu; LIFO (LAST IN FIRST OUT) adalah suatu metode pembuatan llinked list dimana data yang masuk paling akhir adalah data yang paling pertama keluar. Sedangkan FIFO (FIRST IN FIRST OUT) adalah suatu metode pembuatan llinked list dimana data yang masuk paling awal adalah data yang paling pertama keluar juga.
Contoh Program untuk Dicoba

Contoh Program 1

#include
#include
struct dataMahasiswa {
char nim[11];
char nama[31];
float ipk;
} mahasiswa;
struct dataMahasiswa mhsTheologi;
void main()
{
strcpy( mahasiswa.nim, “0244500016” );
strcpy( mahasiswa.nama, “Chotimatul” );
mahasiswa.ipk = 3.123;
mhsTheologi = mahasiswa;
printf(“Cetak isi struct mahasiswa”);
printf(“\nNim mahasiswa : %s”,mahasiswa.nim);
printf(“\nNama mahasiswa : %s”,mahasiswa.nama);
printf(“\nIPK mahasiswa : %f”,mahasiswa.ipk);
}


Contoh Program 2

#include “stdio.h”
#include “conio.h”
#include “stdlib.h”
#include “malloc.h”

struct simpul {
int data;
struct simpul *link;
}

void insert_awal();
void insert_tengah();
void insert_akhir();
void delete_awal();
void delete_tengah();
void delete_akhir();
void tampil();

struct simpul *first=NULL
struct simpul *penunjuk;
struct simpul *p;
int x;

void main() {
int pilih;
menu :
clrscr();
gotoxy(25,14);puts("Linier Linked List");
gotoxy(25,15);puts("[1]. Insert - Input Link List");
gotoxy(25,16);puts("[2]. Delete - Hapus Linked List");
gotoxy(25,17);puts("[3]. Show - Tampil ");
gotoxy(25,18);puts("[4]. Quit - Keluar ");
gotoxy(25,20);printf(" pilih : "); scanf("%i",&pilih);

switch(pilih)
{ case 1:
printf(“Masukkan sebuah nilai integer : ”); scanf(“%i”, &x);
if(first==NULL) {
insert_awal();
} else {
penunjuk = first;
if(xdata) {
insert_awal();
} else {
while(penunjuk->link != NULL) {
penunjuk=penunjuk->link;
}
if(x>penunjuk->data) {
insert_akhir();
} else {
insert_tengah();
}
}
}
getch(); break;

case 2:
printf(“\nMasukkan bilangan yang mau dihapus : ”); scanf(“%i”, &x);
if(first != NULL) {
penunjuk = first;
if(x == penunjuk->data) {
delete_awal();
} else {
while(penunjuk->link != NULL) {
penunjuk = penunjuk->link;
}
if(x == penunjuk->data) {
delete_akhir();
} else {
penunjuk = first->link;
while(x != penunjuk->data) {
penunjuk = penunjuk->link;
if(penunjuk->link == NULL) {
printf(“%i tidak ditemukan pada link list”, x);
getch(); goto menu;
}
delete_tengah();
}
}
}
}
getch(); break;

case 3:
tampil();
getch(); break;

case 4:
exit(0); break;
}
goto menu;
} //end of main()

void insert_awal() {
p = (struct simpul *)malloc(sizeof(struct simpul));
p->data = x;
if(first != NULL) {
p->link = first;
first = p;
printf(“\nsisip awal”);
} else {
p->link = NULL;
first = p;
printf(“\nbikin simpul baru”);
}
}

void insert_tengah() {
struct simpul *q, *r;
p = (struct simpul *)malloc(sizeof(struct simpul));
p->data = x;
if(first != NULL) {
q = first;
while(q->data <>
k = q;
q = q->link;
}
p->link = q;
r->link = p;
printf(“\ninsert tengah ……..”);
} else {
insert_awal();
}
}

void insert_akhir() {
struct simpul *q;
p = (struct simpul *)malloc(sizeof(struct simpul));
p->data = x;
if(first != NULL) {
q = first;
while(q->link !=NULL) {
q = q->link;
}
q->link = p;
p->link = NULL;
printf(“\ninsert akhir………………..”);
} else {
insert_awal();
}
}

void delete_awal() {
if(first != NULL) {
p = first;
first = first->link;
x = p->data;
p->link = NULL;
printf(“\n%i telah disingkirkan dari link list”, x);
free(p);
} else {
printf(“\nLinked list masih kosong”);
}
}

void delete_tengah() {
//buat sendiri lah
}

void delete_akhir() {
struct simpul *q;
if(first != NULL) {
p = first;
while(p->link != NULL) {
q = p;
p = p->link;
}
q ->link = NULL;
x = p->data;
printf(“\n%i telah disingkirkan dari link list”, x);
p->link = NULL;
free(p);
} else {
printf(“\nList masih kosong”);
}
}

void tampil() {
if(first != NULL) {
p = first;
while(p != NULL) {
x = p->data;
p = p->link;
printf(“%i -> ”, p->data);
}
}
}

Double Linked List
adalah pointer ganda yang digunakan untuk bergerak lebih dari satu arah saja.


Contoh Program 1

#include “stdio.h”
#include “conio.h”
#include “stdlib.h”
#include “malloc.h”
#include “ctype.h”

struct simpul {
int data;
struct simpul *left;
struct simpul *right;
}

void insert_kiri();
void insert_tengah();
void insert_kanan();
void delete_kiri();
void delete_tengah();
void delete_kanan();
void pesan1();
void pesan2();
void tampil();

struct simpul *kiri=NULL
struct simpul *kanan = NULL;
struct simpul *penunjuk;
struct simpul *p;
int x;

void main() {
int pilih;
menu :
clrscr();
gotoxy(25,14);puts("Double Linked List");
gotoxy(25,15);puts("[1]. Insert - Input Link List");
gotoxy(25,16);puts("[2]. Delete - Hapus Linked List");
gotoxy(25,17);puts("[3]. Show - Tampil ");
gotoxy(25,18);puts("[4]. Quit - Keluar ");
gotoxy(25,20);printf(" pilih : "); scanf("%i",&pilih);

switch(pilih)
{ case 1:
printf(“Masukkan sebuah nilai integer : ”); scanf(“%i”, &x);
if(kiri==NULL) {
insert_kiri();
} else {
penunjuk = kiri;
if(x <>data) {
insert_kiri();
} else {
while(penunjuk->link != NULL) {
penunjuk=penunjuk->right;
}
if(x>penunjuk->data) {
insert_kanan();
} else {
insert_tengah();
}
}
}
getch(); break;

case 2:
printf(“\nMasukkan bilangan yang mau dihapus : ”); scanf(“%i”, &x);
if(kiri == NULL) {
pesan1(); goto menu;
} else {
penunjuk = kiri;
if(x == penunjuk->data) {
delete_kiri();
} else {
penunjuk = kanan;
if(x == penunjuk->data) {
delete_kanan();
} else {
penunjuk = kanan->left;
while(x != penunjuk->data) {
if(penunjuk == kiri) {
pesan2();
goto menu;
} else {
penunjuk = penunjuk->left;
}
delete_tengah();
}
}
}
}
getch(); break;

case 3:
tampil();
getch(); break;

case 4:
exit(0); break;
}
goto menu;
} //end of main()

void insert_kiri() {
p = (struct simpul *)malloc(sizeof(struct simpul));
p->data = x;
if(kiri != NULL) {
p->link = kiri;
kiri->left = p;
kiri = p;
p->left = NULL;
printf(“\ninsert kiri………..”);
} else {
p->left = NULL;
p->right = NULL;
kiri = p;
kanan = p;
printf(“\nbikin simpul baru”);
}
}

void insert_tengah() {
struct simpul *q;
p = (struct simpul *)malloc(sizeof(struct simpul));
p->data = x;
if(kiri != NULL) {
q = kiri;
while(q->data <>
q = q->right;
}
p->right = q;
p->left = q->left;
q->left->right = p;
q->left = p;
printf(“\ninsert tengah ……..”);
} else {
p->left = NULL;
p->right = NULL;
kiri = p;
kanan = p;
printf(“\nbikin simpul baru”);
}
}

void insert_kanan() {
//buat prosedur insert_kanan()
}

void delete_kiri() {
//buat prosedur delete_kiri()
}

void delete_tengah() {
//buat sendiri lah
}

void delete_kanan() {
//terusin sendiri
}

void tampil() {
if(kiri != NULL) {
p = kiri;
while(p != NULL) {
x = p->data;
p = p->right;
printf(“%i -> ”, p->data);
}
}
}

void pesan1() {
gotoxy(25,15); textcolor(YELLOW+BLINK);
{ cprintf(“Link List masih kosong……….”); }
getch();
}

void pesan2() {
gotoxy(25,15); textcolor(YELLOW+BLINK);
{ cprintf(“Data tidak ditemukan dalam Link List…………..”); }
getch();
}