Modul 0 (Linked List)

Linked List

Terminologi

Sebelum masuk kepada definisi, terdapat istilah yang sering digunakan dalam mendeskripsikan linked list.

• Node – Sebuah node merepresentasikan satu elemen data yang dapat berisi nilai dan/atau informasi lain yang dibutuhkan serta terdapat hubungan atau link/reference ke node lain.
• Head – merupakan node pertama/paling depan dari linked list.
• Tail – merupakan node terakhir/paling belakang dari linked list.

Definisi

Linked List adalah struktur data yang menyimpan data dalam bentuk linear, dimana tiap-tiap data direpresentasikan oleh node-node yang membentuk sekuens secara berurutan. Pada dasarnya, satu node dalam linked list terdiri dari:

• Data yang disimpan, dan
• Referensi (link) kepada node selanjutnya

Contoh ilustrasi sebuah node dalam linked list.

Karakteristik

Linked list merupakan struktur data yang bersifat dinamis, yang artinya ukurannya dapat berubah mengikuti banyaknya data yang dimasukkan/ditambahkan, tidak seperti Static Array. Namun, data pada linked list tidak bisa diakses secara random layaknya pengaksesan indeks pada array, melainkan harus melalui proses traversing terlebih dahulu.

Ilustrasi

Linked list dapat diilustrasikan sebagai kumpulan node yang saling terhubung secara sekuensial membentuk rangkaian secara berurutan. Misalkan, terdapat list 𝐴 dengan kumpulan data 𝐴 = [2,3,6,11,13].

Operasi Dasar

• isEmpty - untuk memeriksa apakah list kosong atau tidak.

• pushBack - operasi untuk menambahkan data baru dari belakang list.

  

• pushFront - operasi untuk menambahkan data baru dari depan list.

  

• insertAt - operasi untuk menambahkan data baru pada posisi yang diinginkan.

  

• back - untuk memperoleh data yang berada pada paling belakang.

• front - untuk memperoleh data yang berada pada paling depan.

• getAt - untuk mendapatkan data pada posisi tertentu.

• popBack - operasi untuk menghapus data yang berada pada paling belakang.

  

• popFront - operasi untuk menghapus data yang berada pada paling depan.

  

• remove(x) - untuk menghapus data tertentu pertama pada list.

  

Variasi Linked List

Singly-Linked List

Doubly-Linked List

Implementasi ADT: SinglyList

Representasi dan Implementasi yang dijelaskan dalam modul ini adalah Singly Linked List yang menyimpan tipe data int. Representasi akan dibawa ke dalam bentuk Abstract Data Type (ADT) yang nantinya akan menjadi tipe data baru bernama SinglyList.

Dalam implementasi ini, kompleksitas waktunya adalah :

Operasi	Keterangan	Kompleksitas Waktu
pushBack	Memasukkan data baru dari belakang.	O(N)
pushFront	Memasukkan data baru dari depan.	O(1)
insertAt	Memasukkan data baru pada posisi tertentu.	O(N) (Worst-case)
popBack	Menghapus node paling belakang.	O(N)
popFront	Menghapus node paling depan.	O(1)
remove(x)	Menghapus node pertama dengan data x.	O(N) (Worst-case)
front	Mendapatkan nilai node terdepan.	O(1)
back	Mendapatkan nilai node paling belakang.	O(N)
getAt	Mendapatkan nilai node pada posisi tertentu.	O(N) (Worst-case)
isEmpty	Memeriksa apakah list kosong.	O(1)

• Representasi Node

  typedef struct snode_t {
      int data;
      struct snode_t *next;
  } SListNode;

• Struktur SinglyList

  typedef struct slist_t {
      unsigned _size;
      SListNode *_head;
  } SinglyList;

• isEmpty

  bool slist_isEmpty(SinglyList *list) {
      return (list->_head == NULL);
  }

• pushBack

  void slist_pushBack(SinglyList *list, int value)
  {
      SListNode *newNode = (SListNode*) malloc(sizeof(SListNode));
      if (newNode) {
          list->_size++;
          newNode->data = value;
          newNode->next = NULL;
          
          if (slist_isEmpty(list)) 
              list->_head = newNode;
          else {
              SListNode *temp = list->_head;
              while (temp->next != NULL) 
                  temp = temp->next;
              temp->next = newNode;
          }
      }
  }

• pushFront

  void slist_pushFront(SinglyList *list, int value) 
  {
      SListNode *newNode = (SListNode*) malloc(sizeof(SListNode));
      if (newNode) {
          list->_size++;
          if (slist_isEmpty(list)) newNode->next = NULL;
          else newNode->next = list->_head;
          
          newNode->data = value;
          list->_head = newNode;
      }
  }

• insertAt

  void slist_insertAt(SinglyList *list, int index, int value)
  {
      if (slist_isEmpty(list) || index >= list->_size) {
          slist_pushBack(list, value);
          return;    
      }
      else if (index == 0) {
          slist_pushFront(list, value);
          return;
      }
      
      SListNode *newNode = (SListNode*) malloc(sizeof(SListNode));
      if (newNode) {
          SListNode *temp = list->_head;
          int _i = 0;
          
          while (temp->next != NULL && _i < index-1) {
              temp = temp->next;
              _i++;
          }
          newNode->data = value;
          newNode->next = temp->next;
          temp->next = newNode;
          list->_size++;
      }
  }

• back

  int slist_back(SinglyList *list)
  {
      if (!slist_isEmpty(list)) {
          SListNode *temp = list->_head;
          while (temp->next != NULL) 
              temp = temp->next;
          return temp->data;
      }
      return 0;
  }

• front

  int slist_front(SinglyList *list)
  {
      if (!slist_isEmpty(list)) {
          return list->_head->data;
      }
      return 0;
  }

• getAt

  int slist_getAt(SinglyList *list, int index)
  {
      if (!slist_isEmpty(list)) {
          SListNode *temp = list->_head;
          int _i = 0;
          while (temp->next != NULL && _i < index) {
              temp = temp->next;
              _i++;
          }
          return temp->data;
      }
      return 0;
  }

• popBack

  void slist_popBack(SinglyList *list)
  {
      if (!slist_isEmpty(list)) {
          SListNode *nextNode = list->_head->next;
          SListNode *currNode = list->_head;
  
          while (nextNode->next != NULL) {
              currNode = nextNode;
              nextNode = nextNode->next;
          }
          currNode->next = NULL;
          free(nextNode);
          list->_size--;
      }
  }

• popFront

  void slist_popFront(SinglyList *list)
  {
      if (!slist_isEmpty(list)) {
          SListNode *temp = list->_head;
          list->_head = list->_head->next;
          free(temp);
          list->_size--;
      }
  }

• remove(x)

  /* BELUM ADA HEHE */