Pertemuan 2-Linked List Implementation 1-2101654781-Devita Cahyadi

Linked List Implementation 1

Single Linked List

Untuk membuat sebuah list, pertama-tama kita harus menetapkan struktur node.

struct tnode {

  int value;

  struct tnode *next;

};

•

struct tnode *head = 0;

Head di atas adalah pointer untuk elemen pertama dalam linked list.

Single Linked List : Insert

struct tnode *node =

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

node->value = x;

node->next  = head;

head = node;

Operator sama dengan

(*node).value = x;

(*node).next = head ;

Single Linked List : Delete

Ada dua kondisi yang harus diperhatikan:

1. Jika x di head node

2. x tidak di head node

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);

}

Doubly Linked list

yaitu linked list struktur data dengan dua link, satu berisi acuan untuk data selanjutnya dan satunya berisi acuan untuk data sebelumnya.

struct tnode {

  int value;

  struct tnode *next;

  struct tnode *prev;

};

•

struct tnode *head = 0;

struct tnode *tail = 0;

Doubly Linked List : Insert

struct tnode *a = ??;

struct tnode *b = ??;

// the new node will be inserted between a and b

struct tnode *node =

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

node->value  = x;

node->next  = b;

node->prev  = a;

a->next  = node;

b->prev  = node;

Doubly Linked List : Delete

Ada empat kondisi :

1. Node yang akan dihapus adalah satu-satunya node di linked list

- free(head);

- head = NULL;

- tail = NULL;

2. Node yang akan dihapus adalah head

- head = head->next

- free(head->prev);

- head->prev = NULL;

3. Node yang akan dihapus adalah tail

- tail = tail->next

- free(tail->prev);

- tail->prev = NULL;

4. Node yag akan dihapus bukan head atau tail

struct tnode *curr = head;

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

  struct tnode *a   = curr;

  struct tnode *del = curr->next;

  struct tnode *b   = curr->next->next;

  a->next = b;

  b->prev = a;

  free(del);