Pertemuan 3- Linked List - 2101648785 - Christian Nugroho

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
2. Double Linked List

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 codingannya :

struct Mahasiswa{
      char nama[25];
      int usia;
      struct Mahasiswa *next;
}*head,*tail;

 

 

 Single Linked list: inserted

 

 

   struct Mahasiswa *node = 

  (struct Mahasiswa*) malloc(sizeof(struct Mahasiswa));

   node->value = x;

  node->next  = head;

  head = node;

 

 

Operator -> has the same meaning as:

(*node).value = x;

(*node).next  = head;

 

 
Single Linked list: deleted

 

struct tnode *curr = head;

•

// if x is in head node

if ( head->value == x ) {

  head = head->next;

  free(curr);
}

// if x is in tail node

else if(tail->value == x){

  while(curr->next!=tail) curr = curr->next;

  free(tail); tail = curr;

  tail->next = NULL;

}

// if x is not in head node, find the location

else {

  while ( curr->next->value != x ) curr = curr->next;

  struct tnode *del = curr->next;

  curr->next = del->next;

  free(del);

}

 

 

 

 

 

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 codingannya :

  struct Mahasiwa{
     char nama[25];
     int usia;
     struct Mahasiswa *next,*prev; }*head,*tail;

 

 

 Double linked list: inserted

struct tnode *node =

  (struct tnode*) malloc(sizeof(struct tnode));

node->value = x;

node->next  = NULL;

node->prev  = tail;

tail->next  = node;

tail = node;

 

 

 

 Single Linked list: deleted

 

Jika node dihapus pada head

•  head = head->next;
•  free(head->prev);
•  head->prev = NULL;

 

Jika node dihapus pada tail

 

•tail = tail->prev;

•  free(tail->next);

•  tail->next = NULL;

 

 

 

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.