DLL (Double/Doubly Linked List)

Double Linked List
Double linked list adalah single linked list yang memiliki 2 arah. Tidak seperti single linked list yang hanya bergeser dari head ke tail, double linked list bisa begeser ke arah sebaliknya

Keuntungan Double linked List
1.       Implementasinya tidak jauh berbeda dari Single linksed list
2.       Mampu bergeser dua arah
3.       Deletion lebih mudah dilakukan, karena tidak perlu menggunakan pointer node dan pointer node sebelum yang akan dihapus. Double linked list hanya butuh pointer node yang ingin dihapus
4.       Bisa di allocate dan di deallocate dengan lebih mudah
5.       Salah satu data structures yang paling efisien jika pergeseran dengan dua arah dibutuhkan
Aplikasinya
                Navigasi
                Back/forward pages di browser
                Undo/redo

#include<stdio.h>
#include<conio.h>

void insertAtBeginning(int);
void insertAtEnd(int);
void insertAtAfter(int,int);
void deleteBeginning();
void deleteEnd();
void deleteSpecific(int);
void display();

struct Node
{
   int data;
   struct Node *previous, *next;
}*head = NULL;

void main()
{
   int choice1, choice2, value, location;
   clrscr();
   while(1)
   {
      printf("\n*********** MENU *************\n");
      printf("1. Insert\n2. Delete\n3. Display\n4. Exit\nEnter your choice: ");
      scanf("%d",&choice1);
      switch()
      {
         case 1: printf("Enter the value to be inserted: ");
                                scanf("%d",&value);
                 while(1)
                 {
                              printf("\nSelect from the following Inserting options\n");
                              printf("1. At Beginning\n2. At End\n3. After a Node\n4. Cancel\nEnter your choice: ");
                    scanf("%d",&choice2);
                    switch(choice2)
                    {
                       case 1:         insertAtBeginning(value);
                                             break;
                       case 2:         insertAtEnd(value);
                                             break;
                       case 3:         printf("Enter the location after which you want to insert: ");
                                             scanf("%d",&location);
                                             insertAfter(value,location);
                                             break;
                       case 4:         goto EndSwitch;
                       default: printf("\nPlease select correct Inserting option!!!\n");
                    }
                 }
         case 2: while(1)
                 {
                              printf("\nSelect from the following Deleting options\n");
                              printf("1. At Beginning\n2. At End\n3. Specific Node\n4. Cancel\nEnter your choice: ");
                    scanf("%d",&choice2);
                    switch(choice2)
                    {
                       case 1:         deleteBeginning();
                                             break;
                       case 2:         deleteEnd();
                                             break;
                       case 3:         printf("Enter the Node value to be deleted: ");
                                             scanf("%d",&location);
                                             deleteSpecic(location);
                                             break;
                       case 4:         goto EndSwitch;
                       default: printf("\nPlease select correct Deleting option!!!\n");
                    }
                 }
                 EndSwitch: break;
         case 3: display();
                break;
         case 4: exit(0);
         default: printf("\nPlease select correct option!!!");
      }
   }
}

void insertAtBeginning(int value)
{
    struct Node *newNode;
    newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode -> data = value;
    newNode -> previous = NULL;
    if(head == NULL)
    {
       newNode -> next = NULL;
       head = newNode;
    }
    else
    {
       newNode -> next = head;
       head = newNode;
    }
    printf("\nInsertion success!!!");
}
void insertAtEnd(int value)
{
   struct Node *newNode;
   newNode = (struct Node*)malloc(sizeof(struct Node));
   newNode -> data = value;
   newNode -> next = NULL;
   if(head == NULL)
   {
      newNode -> previous = NULL;
      head = newNode;
   }
   else
   {
      struct Node *temp = head;
      while(temp -> next != NULL)
         temp = temp -> next;
      temp -> next = newNode;
      newNode -> previous = temp;
   }
   printf("\nInsertion success!!!");  
}
void insertAfter(int value, int location)
{
   struct Node *newNode;
   newNode = (struct Node*)malloc(sizeof(struct Node));
   newNode -> data = value;
   if(head == NULL)
   {
      newNode -> previous = newNode -> next = NULL;
      head = newNode;
   }
   else
   {
      struct Node *temp1 = head, temp2;
      while(temp1 -> data != location)
      {
         if(temp1 -> next == NULL)
         {
            printf("Given node is not found in the list!!!");
            goto EndFunction;
         }
         else
         {
            temp1 = temp1 -> next;
         }
      }
      temp2 = temp1 -> next;
      temp1 -> next = newNode;
      newNode -> previous = temp1;
      newNode -> next = temp2;
      temp2 -> previous = newNode;
      printf("\nInsertion success!!!");
   }
   EndFunction:
}
void deleteBeginning()
{
   if(head == NULL)
      printf("List is Empty!!! Deletion not possible!!!");
   else
   {
      struct Node *temp = head;
      if(temp -> previous == temp -> next)
      {
         head = NULL;
         free(temp);
      }
      else{
         head = temp -> next;
         head -> previous = NULL;
         free(temp);
      }
      printf("\nDeletion success!!!");
   }
}
void deleteEnd()
{
   if(head == NULL)
      printf("List is Empty!!! Deletion not possible!!!");
   else
   {
      struct Node *temp = head;
      if(temp -> previous == temp -> next)
      {
         head = NULL;
         free(temp);
      }
      else{
         while(temp -> next != NULL)
            temp = temp -> next;
         temp -> previous -> next = NULL;
         free(temp);
      }
      printf("\nDeletion success!!!");
   }
}
void deleteSpecific(int delValue)
{
   if(head == NULL)
      printf("List is Empty!!! Deletion not possible!!!");
   else
   {
      struct Node *temp = head;
      while(temp -> data != delValue)
      {
         if(temp -> next == NULL)
         {
            printf("\nGiven node is not found in the list!!!");
            goto FuctionEnd;
         }
         else
         {
            temp = temp -> next;
         }
      }
      if(temp == head)
      {
         head = NULL;
         free(temp);
      }
      else
      {
         temp -> previous -> next = temp -> next;
         free(temp);  
      }
      printf("\nDeletion success!!!");
   }
   FuctionEnd:
}
void display()
{
   if(head == NULL)
      printf("\nList is Empty!!!");
   else
   {
      struct Node *temp = head;
      printf("\nList elements are: \n");
      printf("NULL <--- ");
      while(temp -> next != NULL)
      {
         printf("%d <===> ",temp -> data);
      }
      printf("%d ---> NULL", temp -> data);
   }
}



Insertion
Insertion untuk code tersebut dapat dilakukan dengan 3 cara:
1.       Insert depan
2.       Insert Akhir
3.       Insert di lokasi yang spesifik
Insert Depan
1.       Buat newNode dengan value yang diinginkan dan newNode->previous sebagai NULL
2.       Cek apakah daftar kosong/Head==NULL
3.       Jika kosong, maka assign Null ke newNode->next dan newNode ke Head
4.       Jika tidak kosong, maka assign Head ke newNode->next dan newNode ke Head
Insert Akhir
1.       Buat newNode dengan value yang diinginkan dan newNode->previous sebagai NULL
2.       Cek apakah daftar kosong/Head==NULL
3.       Jika kosong, maka assign Null ke newNode->next dan newNode ke Head
4.       Jika tidak kosong, maka bentuk pointer node temp dan inisialisasi dengan Head
5.       Temp akan bergeser terus sampai ke node terakhir pada daftar/temp->next == NULL
6.       Assign newNode ke temp->next dan temp ke newNode->previous

Insert di lokasi yang spesifik
1.       Buat newNode dengan value yang diisi
2.       Cek apakah daftar kosong
3.       Jika kosong, maka assign NULL ke newNode->previous dan newNode->next dan set newNode ke Head
4.       Jika tidak kosong, maka bentuk pointer node temp1 dan temp2 dan inisialisasi temp1 dengan Head
5.       temp1 akan tetap bergeser sampai lnode yang akan diisi dengan newNode
6.       temp1 akan selalu cek apakah temp1 sampai ke node terakhir. Jika sampai ke node terakhir. Maka cetak 'Given node is not found in the list!!! Insertion not possible!!!' dan function selesai. Jika tidak, maka temp1 akan lanjut bergeser
7.       Assign temp1 → next ke temp2, newNode ke temp1 → next, temp1 ke newNode → previous, temp2 ke newNode → next dan newNode ke temp2 → previous.

Deletion
                Deletion dalam code tersebut dapat dilakukan dengann 3 cara:
1.       Delete dari depan
2.       Delete dari terakhir
3.       Delete di lokasi yang spesifik

Delete depan
1.       Cek apakah daftar tersebut kosong/Head == NULL
2.       Jika kosong, maka munculkan 'List is Empty!!! Deletion is not possible' dan function selesai
3.       Jika tidak kosong, maka bentuk pointer node temp dan inisialisasi dengan Head
4.       Cek apakah daftar hanya berisi 1 node (temp->previous==temp->next)
5.       Jika True, maka set Head ke NULL dan hapus temp(memenuhi kondisi empty)
6.       Jika False, maka assign temp->next ke Head, NULL ke head->previous dan hapus temp

Delete Akhir
1.       Cek apakah daftar tersebut kosong/Head == NULL
2.       Jika kosong, maka munculkan 'List is Empty!!! Deletion is not possible' dan function selesai
3.       Jika tidak kosong, maka bentuk pointer node temp dan inisialisasi dengan Head
4.       Cek apakah daftar hanya berisi 1 node (temp->previous==temp->next)
5.       Jika True, maka set Head ke NULL dan hapus temp(memenuhi kondisi empty)
6.       Jika False, maka temp akan terus bergeser sampai node terakhir/temp->next==NULL
7.       Assign NULL ke temp->previous->next dan hapus temp

Delete di lokasi yang spesifik
1.       Cek apakah daftar tersebut kosong/Head == NULL
2.       Jika kosong, maka munculkan 'List is Empty!!! Deletion is not possible' dan function selesai
3.       Jika tidak kosong, maka bentuk pointer node temp dan inisialisasi dengan Head
4.       Temp akan terus bergeser sampai node yang ingin dihapus atau node terakhir
5.       Jika sampai ke node terakhir, muncul 'Given node not found in the list! Deletion not possible!!!' dan function selesai
6.       Jika sampai ke node yang ingin dihapus, cek apakah daftar tersebut hanya berisi satu node
7.       Jika hanya berisi satu node dan node itu yang ingin dihapus, maka set Head ke Null dan hapus temp (free(temp))
8.       Jika berisi banyak node, maka cek apakah temp adalah node depan/temp==Head
9.       Jika temp adalah node depan, maka geser head ke node selanjutnya (Head = Head → next), set Head dari previous ke NULL (Head → previous = NULL) dan hapus temp
1   Jika temp bukan node depan, maka cek apakah temp adalah node terakhir/temp->next==NULL
1  Jika temp adalah node terakhir, maka set temp dari previous dari next ke NULL/ temp → previous → next = NULL, dan hapus temp (free(temp))
1 Jika temp bukan node depan dan terakhir, maka set temp dari previous dari next ke temp dari next (temp → previous → next = temp → next), temp dari next dari previous ke temp dari previous (temp → next → previous = temp → previous) dan dhapus temp (free(temp)).



Display
                Cara menampilkan elemen yang ada dalam daftar tersebut adalah:
1.       Cek apakah daftar kosong/Head==NULL
2.       Jika kosong, maka munculkan 'List is Empty!!!' dan function selesai
3.       Jika tidak kosong, maka membentuk pointer temp dan dimulai dengan Head
4.       Munculkan 'NULL <--- '
5.       Munculkan temp->data dengan tanda panah(<---->) sampai temp mencapai node terakhir
6.       Munculkan, temp -> data dengan panah menunjuk ke NULL (temp → data ---> NULL)

Komentar

Posting Komentar

Postingan populer dari blog ini

CA01-011 Heap & Tries

Gambar
Max Heap : pohon yang parentnya selalu lebih besar dari anaknya Min Heap : pohon yang parentnya selalu lebih kecil dari anaknya Min-Max Heap : Pohon yang selang-seling parentnya Heap biasanya menggunakan array, tapi bisa menggunakan linked list juga. Dimulai dari 1 untuk memudahkan mencari node. Insert dalam heap dilakukan dengan seperti berikut: 1.        Insert node seperti dalam Binary Tree 2.        cek apakah angka tersebut memenuhi syarat (lebih besar dari parentnya untuk min heap, lebih kecil dari parentnya untuk max heap) 3.        Jika salah, maka angka tersebut ditukar dengan parentnya 4.        lakukan step 2 dan 3 sampai node tersebut memenuhi syaratnya, atau node tersebut berada di posisi root aksi yang dilakukan tersebut disebut Heapify Up untuk delete dilakukan sebagai berikut: 1.        hap...
Baca selengkapnya

CA01-006

Linked List Butuh malloc untuk alokasi value ke memory yang berbeda Pointer next dibuat untuk menyimpan data setelahnya, struct data untuk recursive Indikator posisi awal dengan if head==NULL Pergeseran dilakukan dengan next->curr Tail->Next==NULL Sebagai penanda akhir list Next adalah alamat curr setelah bergeser Menghapus/pop dengan menggeser curr/tail ke alamat sebelumnya Double Linked List Double linked list adalah single linked list yang memiliki 2 arah. Tidak seperti single linked list yang hanya bergeser dari head ke tail, double linked list bisa begeser ke arah sebaliknya Keuntungan Double linked List 1.         Implementasinya tidak jauh berbeda dari Single linksed list 2.         Mampu bergeser dua arah 3.         Deletion lebih mudah dilakukan, karena tidak perlu menggunakan pointer node dan pointer node sebelum yang akan...
Baca selengkapnya

CA01-004

BST/ Binary Search Tree BST adalah sebuah cara untuk mengurutkan data berdasarkan Hieerarki. Karena Binary, masing-masing node hanya punya boleh keturunan maksimum dua. Dalam penyusunannya, data yang lebih besar ada di kanan dan data yang lebih kecil ada di kiri, bisa juga sebaliknya. Insert: insert dalam BST setelah insert pertama adalah ·          Jika node yang dimasukkan lebih besar dari node atasnya, maka keturunannya akan ada di bawah dan diletakkan di sisi kanan node tersebut. ·          Jika node yang dimasukkan lebih kecil dari node atasnya, maka keturunannya aka nada di bawah dan diletakkan di sisi kiri node tersebut Pop : Pop dalam BST memiliki aturan sebagai berikut: ·          Jika pop dilakukan pada leaf/ node yang tidak memiliki keturunan maka node tersebut akan langsung di pop ·          Jika pop...
Baca selengkapnya