STRUKTUR DATA LINKED LIST

Linked List

Apa itu Linked List?

Linked List atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail. 

·                     Head adalah elemen yang berada pada posisi pertama dalam suatu linked list

·                     Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list

Ada beberapa macam Linked List, yaitu :

1.             Single Linked List

Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL.

contoh :

contoh codingannya :

struct Mahasiswa{

 char nama[25];

 int usia;

 struct Mahasiswa *next;

}*head,*tail;

    2. Double Linked List

Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL. contoh :

contoh codingannya :

struct Mahasiwa{

 char nama[25];

 int usia;

 struct Mahasiswa *next,*prev;

}*head,*tail;

    3. Circular Linked List

Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis Circular Linked List, yaitu :

·                     Circular Single Linked List

contoh :

·                     Circular Double Linked List

contoh :

    4. Multiple Linked List

Multiple Linked List merupakan suatu linked list yang memiliki lebih dar 2 buat variabel pointer. contoh :

4. Non Circular linked list

Pengertian:
Single : artinya field pointer-nya hanya satu buah saja dan satu arah.
Linked List : artinya node-node tersebut saling terhubung satu sama lain. 

      Ilustrasinya
- Setiap node pada linked list mempunyai field yang berisi pointer ke node
berikutnya, dan juga memiliki field yang berisi data.
- Pada akhir linked list, node terakhir akan menunjuk ke NULL yang akan
digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list

Contoh program single linked list non circular tambah list di depan :

# include<stdio.h>

# include<stdlib.h>

# include<conio.h>

# include<iostream.h>

# include<ctype.h>

# include<string.h>

struct simpul

{

            int angka;

            struct simpul*berikut;

} ;

struct simpul *awal=NULL;

int bil;

void tambah_list_didepan(int info);

void isi_list();

void tampil_list();

void hapus_list();

void main ()

{

            clrscr();

            isi_list();

            clrscr();

            tampil_list();

            hapus_list();

            getch();

}

void tambah_list_didepan(int info)

{

            struct simpul *baru;

            baru=(struct simpul *)malloc(sizeof(struct simpul));

            baru->angka=info;

            baru->berikut=awal;

            awal=baru;

}

void isi_list()

{

            char jawab;

            do

            {

            clrscr();

            cout<<"\ninput bilangan :";

            cin>>bil;

            tambah_list_didepan(bil);

            cout<<"\ntambah data Y/T :"  ;

            cin>>jawab;

            }

            while (toupper(jawab)!='T');

}

void tampil_list()

{

            struct simpul* baca;

            int i;

            baca=awal;

            i=1;

            while(baca!=NULL)

            {

                        cout<<"\nbilangan ke-"<<i<<"yang dibaca :"<<baca->angka;

                        i++;

                        baca=baca->berikut;

            }

}

void hapus_list()

{

            struct simpul*hapus;

            hapus=awal;

            while(hapus!=NULL)

            {

                        awal=hapus->berikut;

                        free(hapus);

                        hapus=awal;

            }

}

Memory Allocation

Dalam C/C++, alokasi memory dapat dilakukan dengan menggunakan malloc , sedangkan untuk dealokasi dapat menggunakan free. Fungsi free hanya membebaskan memory tetapi tidak menghapus isi dari memory tersebut. 

contoh penggunaan malloc:

·                     int  *px = (int *) malloc(sizeof(int));

·                     char *pc = (char *) malloc(sizeof(char));

·                     struct Facebook *curr = (struct Facebook*) malloc(sizeof(struct Facebook));

contoh penggunaan free:

·                     free(curr); 

Alokasi suatu memory biasanya dibutuhkan didalam linked list saat akan menambah node/data baru.

Insert dan Delete Node dalam Single Linked List

Insert (push) dan delete (pop) node pada linked list dapat dilakukan pada posisi depan (head), tengah (mid) dan belakang (tail)

Insert

Contoh codingan push depan :

Contoh codingan push belakang :

Insert dan Delete Node dalam Double Linked List

Insert (push) dan delete (pop) node pada linked list dapat dilakukan pada posisi depan (head), tengah (mid) dan belakang (tail)

Insert

Contoh codingan push depan :

Contoh codingan push belakang :

Header Linked List

Selain ke-4 jenis Linked List diatas, ada juga jenis lain yaitu header linked list. Header linked list merupakan header spesial yang terdiri dari node headernya. Jadi, linked list jenis ini tidak menunjuk pada node pertama (head) namun hanya menyimpan alamat dari node headernya.