STRUKTUR DATA (Linked List)

TUGAS PRAKTIKUM
IMPLEMENTASI STRUKTUR DATA

MODUL 3
LINKED LIST/ SENARAI BERKAIT-LINKED LIST
DENGAN POINTER

Disusun Oleh
Nama : Agung Tri Utoro
NIM : 123090188
PLUG : 8
Asdos : Widy Sulistianto
CoAss : Ial Irwan Arahman

JURUSAN TEKNIK INFORMATIKA
FAKULTAS TEKNOLOGI INDUSTRI
UNIVERSITAS PEMBANGUNAN NASIONAL “VETERAN”
YOGYAKARTA
2010



BAB I
LAPORAN
#include
#include
#define true 1
#define false 0

using namespace std;

typedef int typeinfo; // membuat sebuah tipe data baru yang bernama tipeinfo dan setara dengan integer
typedef struct typenode *typeptr; // menyediakan sebuah struct dan bernama typenode dan diakses oleh *typeptr
typedef struct typenode { typeinfo info; // tipe: typeinfo setara dengan integer dan field info
typeptr next; // tipe: typeptr (menunjuk sebuah memory) dan field next
};
typeptr awal,akhir; // deklarasi awal dan akhir yang bertipe typeptr
void buatlistbaru(); // menyiapka sebuah fungsi buatlistbaru
void sisipnode(typeinfo IB); // menyiapkan sebuah fungsi sisipnode dengan parameter IB yang bertipe typeinfo
void hapusnode(typeinfo IH); // meyiapkan fungsi hapusnode dengan parameter IH yg bertipe typeinfo
void bacamaju (); // meyiapkan fungsi bacamaju
void bacamundur (); // menyiapkan fungsi bacamundur
int listkosong(); //

//****************************************************************************
int main() // blok main
{
cout << "List mula - mula : \n"; buatlistbaru(); // memanggil fungsi listbaru sisipnode(50); // memanggil fungsi sisipnode sisipnode(20); sisipnode(5); sisipnode(100); sisipnode(70); sisipnode(25); bacamaju(); cout << "\n\nHapus node 50\n"; cout << "\nKondisi List setelah di hapus, dibaca dari belakang :\n\n"; hapusnode (50); bacamundur(); return 0; } //---------------------------------------------------- void buatlistbaru() { typeptr list; // deklarasi sebuah list list = NULL; awal = list; akhir = list; } //------------------------------------------------------------------ void bacamaju() { typeptr bantu; bantu=awal; while (bantu!=NULL) { cout << " " <<>info;
cout << " "; bantu=bantu->next;
}
}
//----------------------------------------------------
void sisipnode(typeinfo IB) // data yang akan dimasukkan disimpan apada IB (info baru)
{
typeptr NB, bantu; // deklarasi NB, bantu yang bertype pointer
NB = (typenode*) malloc (sizeof(typenode)); // menyiapkan memori seukuran typenode NB
NB -> info = IB; // NB->info di isi dengan nilai pada IB
NB -> next = NULL; // NB->next tidak menunjuk node yang lain atau NULL (deklarasi pertama)
if (listkosong()) // jika list kosong maka
{
awal = NB; // awal yang berupa typeprt menunjuk NB
akhir = NB; // dan akhir yang berupa typeptr menunjuka NB
}
else if (IB <= awal->info) // jika sudah ada isinya (awal) maka akan dibandingkan dengan IB
{ // bila IB lebih kecil atau sama dengan awal->info maka
NB -> next = awal; // NB->next akan menunjuk awal
awal = NB; // awal berubah ke posisi NB
}
else // yang lain
{
bantu=awal; // node bantu sama dengan awal
while (bantu -> next!=NULL && IB > bantu->next->info)
bantu= bantu->next;
NB->next=bantu->next;
bantu->next=NB;
if (IB>akhir -> info)
akhir=NB;
}
}
//----------------------------------------------------
int listkosong()
{ if (awal==NULL)
return (true);
else
return (false);}

//------------------------------------------------------------------
void hapusnode (typeinfo IH)
{
typeptr hapus, bantu;
if (listkosong())
cout << "List masih kosong "; else if (awal -> info==IH)
{
hapus = awal;
awal=hapus->next;
free (hapus);}
else
{
bantu=awal;
while(bantu->next->next!=NULL && IH!=bantu->next->info)
bantu=bantu->next;
if (IH==bantu->next->info)
{
hapus=bantu->next;
if (hapus==akhir)
{ akhir = bantu;
akhir->next=NULL;}
else
bantu->next=hapus->next;
free(hapus);
}
else
cout << "Node tidak ditemukan!\n"; } } //------------------------------------------------------------------ void bacamundur() { typeptr depan,bantu; depan=awal; awal=akhir; do {bantu=depan; while (bantu->next!=akhir)
bantu=bantu->next;
akhir->next=bantu;
akhir=bantu;
} while ( akhir !=depan);
akhir->next=NULL;
bantu=awal;
while (bantu!=NULL)
{
cout << " " <<>info;
cout << ""; bantu=bantu->next;
}
}
//-------------------------------------------------------------------
















BAB II
ARTIKEL
Linked List Dengan Pascal
Post under Programming By: ajonk
Saat pertama kali membaca judul itu mungkin ada anggapan kalau postingan ini akan berisi penjelasan mendetail tentang bahasa planet tersebut, seperti postingan-postingan lainnya. Oke, mungkin disini saya akan menjelaskan sedikit tentang Linked List, tapi tidak terlalu mendetail. Karena saya juga belum begitu mengerti. Sederhananya, Linked list adalah daftar record sejenis yang satu sama lain dihubungkan dengan ponter sehingga membentuk data yang berantai, seperti array, cuman Linked List lebih dinamis, pengertian lengkapnya bisa dilihat di Wikipedia.
Oke…yang jadi fokus di postingan ini sebenarnya saya hanya ingin share contoh Linked List dalam bahasa pascal.

Linked list (list bertaut) adalah salah satu struktur data dasar yang sangat fundamental dalam bidang ilmu komputer. Dengan menggunakan linked list maka programmer dapat menimpan datanya kapanpun dibutuhkan. Linked list mirip dangan array, kecuali pada linked list data yang ingin disimpan dapat dialokasikan secara dinamis pada saat pengoperasian program (run-time).
Pada array, apabila programmer ingin menyimpan data, programmer diharuskan untuk mendefinisikan besar array terlebih dahulu, seringkali programmer mengalokasikan array yang sangat besar(misal 100). Hal ini tidak efektif karena seringkali yang dipakai tidak sebesar itu. Dan apabila programmer ingin menyimpan data lebih dari seratus data, maka hal itu tidak dapat dimungkinkan karena sifat array yang besarnya statik. Linked list adalah salah satu struktur data yang mampu menutupi kelemahan tersebut.
Secara umum linked list tersusun atas sejumlah bagian-bagian data yang lebih kecil yang terhubung (biasanya melalui pointer). Linked list dapat divisualisasikan seperti kereta, bagian kepala linked list adalah mesin kereta, data yang disimpan adalah gerbong, dan pengait antar gerbong adalah pointer.

Programmer membaca data menyerupai kondektur yang ingin memeriksa karcis penumpang. Programmer menyusuri linked list melalui kepalanya, dan kemudian berlanjut ke gerbong (data) berikutnya, dan seterusnya sampai gerbong terakhir (biasanya ditandai dengan pointer menunjukkan alamat kosong (NULL)). Penyusuran data dilakukan secara satu persatu sehingga penyusuran data bekerja dengan keefektifan On. Dibandingkan array, ini merupakan kelemahan terbesar linked list. Pada array, apabilan programmer ingin mengakses data ke-n (index n), maka programmer dapat langsung mengaksesnya. Sedangkan dengan linked list programmer harus menyusuri data sebanyak n terlebih dahulu.
Linked List adalah struktur data yang berbeda dengan struktur data array. Linked list dapat dibayangkan seperti rantai yang bersambung satu sama lainnya. Tiap-tiap rantai (node) terhubung dengan pointer.
Gambar berikut memperlihatkan sebuah Linked List.

Sebelum kita membahas lebih jauh tentang Linked List, alangkah baiknya bila kita mengulang sedikit tentang structdan typedef. Struct atau structure dalam bahasa pemograman C/C++ digunakan untuk mendefinisikan tipe data yang memiliki anggota (member) bertipe tertentu. Berikut contoh dan cara mendeklarasi sebuah struct:
struct tgl {
int hari;
int bulan;
int tahun;
}

struct tgl Tanggal;

Bila divisualisasikan kira-kira sebagai berikut:


Contoh di atas memperlihatkan bagaimana mendeklarasi sebuah struct dengan nama struct tgl yang memiliki tiga member yaitu hari, bulan dan tahun yang bertipe int (integer). Kemudian, sebuah variabel Tanggal dideklarasikan bertipe struct tgl. Untuk mempersingkat dan menyederhanakan pendeklarasian sebuah struct, kata cadang typedefbiasa digunakan. Sesuai namanya, typedef digunakan untuk mendefinisikan sebuah tipe data menjadi suatu alias tertentu. Perhatikan contoh berikut:

Dengan cara yang sama, pendeklarasian struct tgl di atas dapat disederhanakan menggunakan kata cadang typedef menjadi:
typedef struct tgl {
int hari;
int bulan;
int tahun;
} Date;

Date Tanggal;

Single Linked List
Linked list dapat dianalogikan sebagai rantai yang terdiri dari beberapa node yang saling terkait. Dengan memegang node terdepan, maka node-node yang saling terkait lainnya dapat kita telesuri.
Dengan hanya mencatat atau memegang alamat dari alokasi data bertipe struct root pada sebuah variabel LL maka keberadaan node-node dalam linked list tersebut dapat diketahui. Bila data-data dalam node berupa bilangan bulat, maka struct yang diperlukan untuk membentuk linked list adalah sebagai berikut:
typedef struct node * NodePtr;
typedef struct node {
int data;
NodePtr next;
}Node;

typedef struct root {
NodePtr head;
unsigned size;
}Root;

Root LL;

Penambahan Node Linked List
Bila setiap penambahan simpul pada linked list dilakukan pada bagian depan (paling dekat dengan head) maka kompleksitas yang diperlukan untuk menambah node baru dalam linked list konstan atau O(1). Penambahan sebuah node dengan nilai 3 pada linked list di atas dapat divisualisasikan sebagai berikut:


Penelusuran Node Linked List
Kompleksitas penelusuran (pencarian) node dalam linked list adalah linier atau O(n). Hal ini disebabkan karena node-node dalam linked list disusun secara acak (tidak berurut). Seandainya pun simpul-simpul dalam linked list disusun secara berurut, metode pencarian biner (binary search) tetap tidak dapat dipergunakan. Ada 2 alasan mengapa pencarian biner tidak dapat digunakan:
1. Linked list tidak memiliki indeks seperti array, sehingga akses langsung ke node tertentu tidak dapat dilakukan. Untuk menuju ke node tertentu, proses pemeriksaan tetap dimulai dari node head (node terdepan). Oleh karena itu proses pencarian selalu berjalan secara linier.
2. Tidak dapat membagi linked list menjadi 2 bagian yang sama besar seperti saat membagi array menjadi 2 bagian bila metode pencarian biner diaplikasikan pada array terurut.

Penghapusan Node Linked List
Sebelum proses penghapusan dilakukan, pencarian node yang ingin dihapus harus terlebih dahulu dilakukan. Bila node yang ingin dihapus ditemukan, suatu hal yang selalu harus diperhatikan adalah bagaimana mengeluarkan node tersebut dari linked list dan kemudian menyambung kembali linked list kembali. Kompleksitas menghapus sebuah node dalam linked list adalah O(n). Perhatikan gambar berikut ini:

Implementasi Linked List
/* linkedlist.h: header file */
typedef struct node * NodePtr;
typedef struct node {
int data;
NodePtr next;
}Node;

typedef struct list {
NodePtr head;
unsigned size;
}List;

void initList(List *);
int addList(List *, int);
void displayList(List *);
void freeList(List *);


/* linkedlist.c: implementasi method dilakukan dalam file ini */

#include "linkedlist.h"
#include
#include

void initList(List * lptr) {
lptr->head = NULL;
lptr->size = 0;
}

int addList(List * lptr, int data) {
NodePtr new;
new = malloc(sizeof(Node));
if(new == NULL) {
printf("Error dalam membuat alokasi memori\n");
return 0;
}
new->data = data;
new->next = lptr->head;
lptr->head = new;
lptr->size++;
return 1;
}

void displayList(List * lptr) {
NodePtr current = lptr->head;
printf("\n");
while(current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("null\n");
}

void freeList(List * lptr) {
NodePtr next=lptr->head;
NodePtr current=next;
while(current != NULL) {
next = current->next;
free(current);
current = next;
}
}


/* main.c */

#include
#include
#include "linkedlist.h"

int main(void) {
int i, n, data;
List LL;

initList(&LL); /* Buat initial linked list */

printf("Jumlah simpul = ");
scanf("%d", &n);

/* Input data simpul */
for(i=0; i gcc –Wall –pedantic –g –o mylist main.c linkedlist.c
Hasil kompilasi di atas akan membuat sebuah objek mylist (yang dibangkitkan dari dua file main.c dan linkedlist.c). Kemudian objek mylist tersebut dapat dijalan melalui command line.


Kesimpulan


Pada praktikum kali ini kita mempraktekan bentuk linked list/snarai berkait beserta operasi-operasi yang dikenakan padanya dan mengimplementasikan linked lisd menggunakan pointer.Disini kita dituntut untuk bisa memahami dan mengerti maksud dan tujuan dari penggunaan linked list dengan pointer tersebut.Pengertian dari list sendiri adalah koleksi dari obyek-obyek dengan sifat setiap elemen memiliki penerus dan setiap elemen memiliki pendahulu.