Makalah LINKED LIST Struktur Data LENGKAP

A.   Tujuan :

Mahasiswa dapat memahami Linked List.

Mahasiswa dapat menerapkan Linked List

B.   Dasar Teori

Linked list atau senarai adalah struktur data berisis kumpulan data / node yang tersusun secara sequential, saling sambung menyambung dan dinamis.
Linked list ini mirip array, namun linked list ini bersifat dinamis, penambahan data tidak terbatas, sequential acces, dan penghapusan data mudah.

Prinsip linked list dapat kita bandingkan seperti suatu rantai yang matanya dihubungkan satu sama lain. Mata rantai tersebut dapat kita asosiasikan dengan record atau node. Jadi, untuk selanjutnya dalam konteks linked list kita menggunakan terminology NODE untuk pengertian sebuah record.

Ciri khas suatu node dalam linked list adalah harus selalu terdapat field, paling sedikit dua bagian, yaitu :

1.       Data

2.       Pointer.

Secara umum linked list dibedakan atas 2 macam, yaitu :

1.       Single Linked List dan

2.       Double Linked List

Single Linked List mempunyai satu pointer untuk setiap node yang menunjuk ke node berikutnya, artinya hanya punya satu arah. 

Gambar 8.1 Node yang terakhir selalu menunjuk ke elemen kosong, dan diidentifikasi dengan nilai NIL

Pada Gambar 8.1 dapat kita lihat bahwa setiap record mempunyai satu pointer yang menunjuk ke record yang berikutnya, dengan pengecualian untuk record terakhir yang menunjuk ke record yang tidak ada. Record yang tidak ada tersebut kita definisi dengan nilai Nul (NIL) yang artinya juga sebagi akhir suatu list.

Double Linked List mempunyai dua pointer yang menunjuk ke node berikutnya dan sebelumnya, artinya punya dua arah.

Gambar 8.2 Previous pointer Node pertama dan Next pointer Node terakhir menunjuk ke elemen kosong, dan diidentifikasi dengan nilai NULL

Double Linked List dapat dilihat pada Gambar 8.2. Pointer Node pertama tidak mempunyai pendahulu, jadi pointer yang menunjuk ke elemen sebelumnya adalah elemen yang tidak ada (NIL) dan analog untuk node terakhir, dimana pointer yang menunjuk ke elemen berikutnya adalah elemen yang tidak ada (NIL).

C. PRAKTIKUM LINKED LIST BAHASA C

#include<stdio.h>

#include<stdlib.h>

#include<iostream.h>

#include<malloc.h>

struct node

{

     int info;

     struct node *next;

}

typedef struct node NODE;

typedef NODE* PTRNODE;

PTRNODE PtrAwal = NULL, tPtr;

/*menambah node di akhir dari list*/

void InsertLast(PTRNODE *Ptr, int Value)

{

     PTRNODE prevPtr = *Ptr, nowPtr = *Ptr, newPtr;

     newPtr = malloc(sizeof(NODE));

     newPtr->info = Value;

     newPtr->next = NULL;

     while (nowPtr != NULL)

     {

           prevPtr = nowPtr;

           nowPtr = nowPtr->next;

     }

     if(prevPtr == NULL)

           *Ptr = newPtr;

           else

           prevPtr->next = newPtr;

}

/*menambah node diawal dari list*/

void InsertFirst(PTRNODE *Ptr, int Value)

{

     PTRNODE newPtr;

     newPtr = malloc(sizeof(NODE));

     newPtr->info = Value;

     newPtr->next = *Ptr;

     *Ptr = newPtr;

}

/*menyisipkan node sehingga menjadi list terurut*/

void InsertOrder(PTRNODE *Ptr, int Value)

{

     PTRNODE prevPtr = *Ptr, nowPtr = *Ptr, newPtr;

     newPtr = malloc(sizeof(NODE));

     newPtr->info = Value;

     newPtr->next = NULL;

     while(nowPtr != NULL && Value > nowPtr->info)

     {

           prevPtr = nowPtr;

           nowPtr = nowPtr->next;

     }

     if (prevPtr == NULL)

     {

           newPtr->next = *Ptr;

           *Ptr = newPtr;

     }

     else

     {

           prevPtr->next = newPtr;

           newPtr->next = nowPtr;

     }

}

/*mencari node yang mempunyai nilai value tertentu*/

PTRNODE Cari(PTRNODE Ptr, int Value)

{

     PTRNODE cariPtr = Ptr;

     int Ketemu = 0;

     while (cariPtr != NULL && Ketemu == 0)

     {

           if (cariPtr->info == Value)

                Ketemu = 1;

           else

                cariPtr = cariPtr->next;

     }

     return cariPtr;

}

/*mendapatkan pointer ke node sebelum node yang ditunjuk Ptr*/

PTRNODE PtrSebelum(PTRNODE Head, PTRNODE Ptr)

{

     PTRNODE nowPtr = Head, prevPtr = NULL;

     while (nowPtr != Ptr)

     {

           prevPtr = nowPtr;

           nowPtr = nowPtr->next;

     }

     return prevPtr;

}

/*menghapus node yang berisi Value*/

void Delete(PTRNODE *Ptr, int Value)

{

     PTRNODE nowPtr, prevPtr, tPtr;

     nowPtr = Cari(*Ptr, Value);

     if (nowPtr != NULL)

     {

           prevPtr = PtrSebelum(*Ptr, nowPtr);

           if (prevPtr == NULL)

           {

                tPtr = *Ptr;

                *Ptr = (*Ptr)->next;

                free(tPtr);

           }

           else

           {

                prevPtr->next = nowPtr->next;

                free(nowPtr);

           }

     }

}

/*menyajikan seluruh isi node kelayar*/

void cetak(PTRNODE Ptr)

{

     while (Ptr != NULL)

     {

           printf("%4d ",Ptr->info);

           Ptr = Ptr->next;

     }

     printf("\n");

}

Program dia atas masih terdapat kesalahan, coba betulkan sehingga dapat digunakan untuk menyisipkan, menghapus dan mencetak linked list.

D.   Tugas Pendahuluan

1.    Jelaskan struktur data linked list!

2.    Jelaskan operasi-operasi pada linked list!

3.    Jelaskan macam-macam linked list dan gambar dari macam-macam linked list tersebut!

E.   Tugas Praktikum

1.    Buatlah program Double Linked List Non Circular (DLLNC) yang terdiri dari menu yang berisi :

1.       Menambah Data Depan

2.       Menambah Data Belakang

3.       Menambanh Data Tengah

4.       Menghapus Data Depan

5.       Menghapus Data Belakang

6.       Menghapus Data Tengah

😊