02 - Implementasi Linked List - 2101686234 - Fandy Shobryanto

Hari ini saya akan membahas tentang implementasi terhadap linked list. Implementasi pada linked list dapat berupa :

1. Single Linked List
2. Polynomial Representation
3. Cicular Single Linked List
4. Doubly Linked List
5. Circular Doubly Linked List
6. Header Linked List

- Single Linked List

    Single Linked List adalah sebuah Linked List yang menggunakan sebuah variabel pointer saja untuk menyimpan banyak data. Single Linked List juga hanya mempunyai satu arah penunjuk ke alamat data selanjutnya (NEXT). Setiap data diwakili dengan NODE dan node ini memiliki nilai nya masing - masing serta memiliki alamat data selanjutnya. Node - Node yang saling terhubung satu sama lain yang diawali dari HEAD dan diakhiri dengan TAIL.

 Untuk membuat List,pertama - tama kita perlu mendefinisikan struktur Node terlebih dahulu.

struct tnode {

int nilai;

struct tnode *next;

};

struct tnode *head = 0

*head adalah pointer untuk menuju ke elemen pertama pada Linked List.

• Push

Push adalah sebuah operasi insert. Pada Linked List terdapat 2 kemungkinan insert,yaitu melalui depan (pushDepan) ataupun belakang (pushBelakang). PushDepan berarti data yang terakhir dimasukkan akan berada di depan data lainnya, begitu juga sebaliknya pushBelakang berarti data yang terakhir dimasukan akan berada di belakang data lainnya. Contohnya seperti berikut :

pushDepan : 1, 3, 5, 7, 10 maka hasilnya akan 10 => 7 => 5 => 3 => 1 => NULL

pushBelakang : 1, 3, 5, 7, 10 maka hasilnya akan 1 => 3 => 5 => 7 => 10 => NULL

contoh pushDepan :

struct kelas{
    char nama_Mhs[25];
    int nilai;
    struct kelas *next;
}*head, *tail;

void pushDepan(char nama_Mhs[],int nilai){

 struct kelas *curr = (struct kelas*) malloc(sizeof(struct kelas));
 strcpy(curr->nama_Mhs , nama_Mhs);
 curr->nilai = nilai;
    if(head == NULL)

    {
        head = tail = curr;
        tail->next = NULL;
    }else{
        curr->next = head;
        head = curr;
    }
}

• Pop

Pop adalah kebalikannya dari push yaitu operasi delete. Pada operasi ini juga sama seperti operasi insert yaitu memili 2 kemungkinan,yaitu popDepan ataupun popBelakang. PopDepan berarti data yang ingin dihapus adalah data yang paling depan dan popBelakang berarti data yang ingin dihapus adalah data yang paling belakang(akhir). 

Contoh popDepan

void popBelakang(){ 
 if(head){   
   struct kelas*curr = head; 
 if(head == tail){ //1     
     head = tail = NULL;
  free(curr);   
    }

else{    //>1 
   while(curr->next != tail){     
  curr=curr->next;          
  }          
  tail = curr;           
 free(curr->next);            
tail->next = NULL;      
  } 
else{     
   printf("No more data to be deleted..\n\n");   
 }
}

- Polynomial Representation

Polynomial Representation adalah sebuah persamaan pangkat tiga seperti 6x3 + 9x2 + 7x + 10 
setiap term yang ada pada polynomial seperti diatas dapat di representasikan sebagai node dari linked list.
persamaan diatas nilainya adalah 6, 9, 7, 1 dan koefesiennya adalah 3, 2, 1, 0. Maksudnya adalah 
x pangkat tiga sebagai 3,
x pangkat dua sebagai 2,
dan x pangkat 1 sebagai 1,
serta x pangkat 0 sebagai 0

-Circular Single Linked List

Dalam circular, node terakhir berisi pointer untuk node pertama. Kita dapat memiliki Circular Single Linked List dan juga Circular Double Linked List. kita tidak dapat memasukkan nilai NULL pada list.

- Doubly Linked List

Double Linked List hampir sama seperti Single Linked List, tetapi hanya memiliki NEXT saja.Contohnya seperti berikut :

struct kelas{
    char nama_Mhs[25];
    int nilai;
    struct kelas *next;

    struct kelas  *prev;
};

struct tnode *head = 0;
struct tnode *tail = 0;

Cara pushBelakang :

struct kelas *curr = (struct kelas*) malloc(sizeof(struct kelas));

node->value = x;
node->next = NULL;
node->prev = tail;
tail->next = node;
tail = node;

- Circular Doubly Linked List

Hal ini sangat mirip dengan circular single linked list,tapi total pointer yang berada pada masing - masing node adalah 2 pointer.

- Header Linked List

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

2101686234 - Fandy Shobryanto