Daftar Tertaut Tunggal dalam Struktur Data

Oleh: Sarah Chen Sarah Chen
Hours Updated

Apa itu Daftar Tertaut Tunggal?

Singly Linked List adalah struktur data linier dan searah, dimana data disimpan pada node, dan setiap node dihubungkan melalui link ke node berikutnya. Setiap node berisi field data dan link ke node berikutnya. Daftar Tertaut Tunggal dapat dilintasi hanya dalam satu arah, sedangkan Daftar Tertaut Ganda dapat dilintasi dalam dua arah.

Berikut struktur simpul dari Daftar Tertaut Tunggal:

Struktur Node dalam Daftar Tertaut
Struktur Node dalam Daftar Tertaut

Mengapa menggunakan daftar tertaut di atas array?

Ada beberapa kasus di mana lebih baik menggunakan Daftar Tertaut daripada Daftar Tertaut susunan. Berikut beberapa skenarionya:

  • Jumlah elemen yang tidak diketahui: Jika Anda tidak mengetahui berapa banyak elemen yang perlu disimpan selama runtime program, Anda dapat menggunakan Daftar Tertaut. Memori dialokasikan secara dinamis saat Anda menambahkan elemen ke daftar tertaut.
  • Akses acak: Dalam skenario di mana Anda tidak perlu menggunakan akses acak dari elemen, Anda dapat menggunakan Daftar Tertaut.
  • Penyisipan di tengah: Penyisipan di tengah array merupakan tugas yang rumit. Karena Anda perlu mendorong elemen lain ke kanan. Namun, Linked List memungkinkan Anda untuk menambahkan elemen ke posisi mana pun yang Anda inginkan.

Operations dari Daftar Tertaut Tunggal

Single Linked List bagus untuk mengalokasikan memori secara dinamis. Ia menyediakan semua operasi dasar dari linked list, yaitu, penyisipan, penghapusan, pencarian, pembaruan, penggabungan dua linked list, traversal, dll.

Di sini kita akan membahas operasi linked list berikut:

  • Memasukkan di kepala
  • Memasukkan di bagian ekor
  • Memasukkan setelah sebuah node
  • Memasukkan sebelum node
  • Hapus simpul kepala
  • Hapus simpul ekor
  • Cari dan Hapus sebuah node
  • Melintasi Daftar Tertaut

Berikut ini contoh daftar tertaut dengan empat node.

Contoh Daftar Tertaut Tunggal
Contoh Daftar Tertaut Tunggal

Penyisipan di bagian atas Daftar Tertaut Tunggal

Ini adalah operasi sederhana. Secara umum, ini dikenal sebagai mendorong daftar tertaut tunggal. Anda perlu membuat node baru dan menempatkannya di bagian atas daftar tertaut.

Untuk melakukan operasi ini, kita perlu mengikuti dua kondisi penting. Yaitu

  1. Jika daftarnya kosong, maka node yang baru dibuat akan menjadi node kepala, dan node kepala berikutnya akan menjadi “NULL”.
  2. Jika daftar tidak kosong, node baru akan menjadi node kepala, dan node berikutnya akan menunjuk ke node kepala sebelumnya.

Berikut kode semu untuk menyisipkan node di bagian atas daftar tertaut:

function insertAtHead( head, value ):
	newNode = Node(value)
	if head is NULL:
		head = newNode
		return head
	else: 
		newNode.next = head
		return newNode
Memasukkan di Kepala
Memasukkan di kepala

Penyisipan di akhir Daftar Tertaut Tunggal

Memasukkan node di akhir daftar tertaut memiliki beberapa kesamaan dengan menyisipkan di kepala. Yang perlu Anda lakukan hanyalah melintasi ke simpul akhir atau simpul ekor. Kemudian arahkan node “berikutnya” dari node akhir ke node yang baru dibuat. Jika node kepala adalah null, maka node baru akan menjadi node kepala.

Berikut langkah-langkahnya:

Langkah 1) Lintasi hingga node “berikutnya” dari node saat ini menjadi nol.

Langkah 2) Buat node baru dengan nilai yang ditentukan.

Langkah 3) Tetapkan node baru sebagai node berikutnya dari node ekor.

Kode semu untuk menyisipkan node di bagian belakang daftar tunggal:

function insertAtEnd( head, value ):
	newNode = Node(value)
	if head is NULL:
		head = newNode
		return head
	while head.next is not NULL:
		then head = head.next
	head.next = newNode
	newNode.next = NULL
Memasukkan di Ekor
Memasukkan di bagian ekor

Penyisipan setelah sebuah node dalam Daftar Tertaut Tunggal

Memasukkan setelah sebuah node memiliki dua bagian: Mencari node dan melampirkan setelah node yang dicari. Kita perlu melintasi semua node. Untuk setiap node, kita perlu mencocokkan dengan elemen pencarian. Jika ada kecocokan, maka kita akan menambahkan node baru setelah node yang dicari.

Berikut langkah-langkahnya:

Langkah 1) Lintasi node berikutnya hingga nilai node saat ini sama dengan item pencarian.

Langkah 2) Penunjuk berikutnya pada simpul baru akan menjadi penunjuk berikutnya pada simpul saat ini.

Langkah 3) Node berikutnya dari node saat ini akan menjadi node baru.

Berikut pseudo-code untuk menyisipkan node demi node:

function insertAfter( head, value, searchItem ):
	newNode = Node(value)
	while head.value equals searchItem:
		then head = head.next
	newNode.next = head.next.next
	head.next = newNode
Memasukkan Node Setelah Node dalam Daftar Tertaut Tunggal
Memasukkan node demi node dalam Single Linked List

ARTIKEL TERKAIT

Penyisipan sebelum sebuah node dalam Daftar Tertaut Tunggal

Fungsi ini mirip dengan penyisipan setelah sebuah node. Kita harus membuat node baru dan melintasi daftar tertaut hingga node saat ini cocok dengan node pencarian. Setelah itu kita akan menambahkan node baru sebagai node sebelumnya dari node saat ini.

Berikut langkah-langkahnya:

Langkah 1) Lintasi hingga nilai node berikutnya sama dengan item pencarian.

Langkah 2) Buat node baru dan tetapkan node "berikutnya" dengan node berikutnya dari node saat ini.

Langkah 3) Tetapkan node baru sebagai node berikutnya dari node saat ini.

Berikut kode semunya:

function insertBefore( head, value, searchItem ):
	newNode = Node(value)
	while head.next.value equals searchItem:
		then head = head.next
	newNode.next = head.next.next
	head.next = newNode
Menyisipkan Node Sebelum Node dalam Daftar Tertaut Tunggal
Memasukkan node sebelum node dalam Daftar Tertaut Tunggal

Hapus kepala daftar tertaut tunggal

Dalam setiap fungsi dari linked list, penunjuk kepala disediakan sebagai parameter. Anda perlu menghapus simpul kepala dan menjadikan simpul berikutnya dari simpul kepala sebagai kepala baru dari linked list. Kita juga perlu mengosongkan memori dari simpul yang dihapus. Jika tidak, memori akan ditandai sebagai terisi ketika program lain mencoba mengaksesnya.

Berikut langkah-langkah untuk menghapus kepala single linked list:

Langkah 1) Tetapkan node berikutnya dari node kepala sebagai kepala baru.

Langkah 2) Bebaskan memori yang dialokasikan oleh node kepala sebelumnya.

Langkah 3) Kembalikan node kepala baru.

Kode semu untuk menghapus node kepala:

function deleteHead( head ):
	temp = head
	head = head.next
	free( temp )
	return head
Menghapus Kepala daftar Tertaut
Menghapus kepala daftar tertaut

Hapus bagian ekor dari daftar tertaut tunggal

Menghapus node ekor lebih mirip dengan menghapus node kepala. Perbedaannya adalah kita perlu menelusuri ke akhir daftar tertaut dan menghapusnya. Dalam daftar tertaut tunggal, simpul dengan simpul berikutnya sebagai “NULL” adalah simpul ekor.

Berikut langkah-langkah untuk menghapus simpul ekor dari daftar tertaut:

Langkah 1) Lintasi sebelum simpul ekor. Simpan simpul saat ini.

Langkah 2) Bebaskan memori node berikutnya dari node saat ini.

Langkah 3) Tetapkan node berikutnya dari node saat ini sebagai NULL.

Berikut pseudo-code untuk menghapus node ekor:

function deleteTail( head ):
	while head.next.next is not NULL:
		head = head.next
	free( head.next )
	head.next = NULL
Menghapus bagian ekor dari Single Linked List
Menghapus bagian ekor dari Single Linked List

Cari dan hapus sebuah node dari daftar tertaut tunggal

Fungsi ini memiliki dua tugas, mencari dan menghapus. Kita perlu mencari sampai akhir daftar tertaut tunggal. Jika kami menemukan node serupa, kami akan menghapus node tersebut. Setelah itu, kita perlu menggabungkan atau menghubungkan node kiri dan kanan dari node yang dihapus. Berikut langkah-langkah untuk melakukan ini:

Langkah 1) Telusuri hingga akhir daftar tertaut. Periksa apakah node saat ini sama dengan node pencarian atau tidak.

Langkah 2) Jika ada node yang cocok, simpan penunjuk node ke node saat ini.

Langkah 3) Node berikutnya dari node sebelumnya akan menjadi node berikutnya dari node saat ini.

Langkah 4) Hapus dan kosongkan memori node saat ini.

Kode semu untuk mencari dan menghapus sebuah node dari daftar tertaut tunggal:

function searchAndDelete( head, searchItem ):
	while head.next.next is not NULL  and head.next.value is not equals searchItem :
		head = head.next
	head.next = head.next.next
	delete(head.next)
Cari dan Hapus Node dari Daftar Tertaut Tunggal
Cari dan hapus node dari Single Linked List

Telusuri daftar tertaut tunggal

Daftar tertaut tunggal hanya memiliki fungsi untuk melintasi head to tail. Tidak ada titik penunjuk ke node sebelumnya; itu sebabnya kami tidak dapat menelusuri Daftar Tertaut Tunggal dalam urutan terbalik. Kami akan melintasi setiap node dan mencetak nilai node saat ini hingga kami mendapatkan nol.

Berikut langkah-langkahnya:

Langkah 1) Lintasi setiap node hingga kita mendapatkan null sebagai node berikutnya.

Langkah 2) Cetak nilai node saat ini.

Kode semu untuk melintasi daftar tertaut tunggal:

function traverse( head ):
		while head.next is not NULL:
			print the value of the head
			head = head.next

Contoh Daftar Tertaut Tunggal di C++

#include<iostream>
using namespace std;
struct Node{
  int data;
  struct Node *next;
};
void insertAtHead(Node* &head, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  if(head!=NULL){
    newNode->next = head;
  }
  head = newNode;
  cout<<"Added "<<newNode->data<<" at the front"<<endl;
}
void insertEnd(Node* &head, int value){
  if(head==NULL){
    insertAtHead(head,value);
  }
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *temp = head;
  while(temp->next!=NULL){
    temp = temp->next;
  }
  temp->next = newNode;
  cout<<"Added "<<newNode->data<<" at the end"<<endl;
}
void searchAndDelete(Node **headPtr, int searchItem){
  Node *temp = new Node();
  if( (*headPtr)->data == searchItem ){
    temp = *headPtr;
    *headPtr = (*headPtr)->next;
    free(temp);
  }else{
    Node *currentNode = *headPtr;
    while(currentNode->next != NULL){
      if(currentNode->next->data == searchItem){
        temp = currentNode->next;
        currentNode->next = currentNode->next->next;
        free(temp);
      }else{
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
  return;
}
void insertAfter(Node * &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next!=NULL &&  head->data!=searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl;
}
void insertBefore(Node * &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next!=NULL &&  head->next->data!=searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl;
}
void traverse(Node *headPointer){  
  Node* tempNode = new Node();
  tempNode = headPointer;
  cout<<"Traversal from head:\t";
  while(tempNode !=NULL){
    cout<<tempNode->data;
    if(tempNode->next)
      cout<<" --> ";
    tempNode = tempNode ->next;
  }
  cout<<endl;
}
int main(){
  Node *head = NULL;
  insertAtHead(head,5);
  insertAtHead(head,6);
  insertAtHead(head,7);
  insertEnd(head,9);
  traverse(head);
  searchAndDelete(&head,6);
  traverse(head);
  insertAfter(head,7,10);
  insertBefore(head,9,11);
  traverse(head);
}

Keluaran:

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Traversal from head:    7 →  6 →  5 →  9
Deleted Node    6
Traversal from head:    7 →  5 →  9
Inserted 10 after node  7
Inserted 11 before node 9
Traversal from head:    7 →  10 →  5 →  11 →  9

Contoh Daftar Tertaut Tunggal di Python program

class Node:
  def __init__(self,data = None, next = None):
    self.data = data
    self.next = next
class SinglyLinkedList:
  def __init__(self):
    self.head = None 
  def insertAtHead(self, value):
    newNode = Node(data=value)    
    if self.head is not None:
      newNode.next = self.head
    self.head = newNode
    print(f'Added {newNode.data} at the front.')
    return  
  def insertAtEnd(self,value):
    if self.head is None:
      self.insertAtHead(value)
    newNode = Node(value)
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    print(f'Added {newNode.data} at the end.')  
  def searchAndDelete(self,searchItem):
    temp = Node()
    if self.head is searchItem:
      temp = self.head
      self.head = self.head.next
    else:
      currentNode = self.head
      while currentNode.next is not None:
        if currentNode.next.data is searchItem:
          temp = currentNode.next
          currentNode.next = currentNode.next.next
        else:
          currentNode = currentNode.next
    print(f'Deleted node\t{searchItem}')
    return
  def insertAfter(self,searchItem,value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data is not searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} after node\t{searchItem}')
    return 
  def insertbefore(self,searchItem,value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data is not searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} before node\t{searchItem}')
    return
  def traverse(self):
    temp = self.head
    print("Traversing from head:\t",end="")
    while temp:
      print("{}\t".format(temp.data),end="")
      temp = temp.next
    print()
SinglyLinkedList = SinglyLinkedList()
SinglyLinkedList.insertAtHead(5)
SinglyLinkedList.insertAtHead(6)
SinglyLinkedList.insertAtHead(7)
SinglyLinkedList.insertAtEnd(9)
SinglyLinkedList.traverse()
SinglyLinkedList.searchAndDelete(6)
SinglyLinkedList.traverse()
SinglyLinkedList.insertAfter(7,10)
SinglyLinkedList.insertbefore(9, 11)
SinglyLinkedList.traverse()

Keluaran:

Added 5 at the front.
Added 6 at the front.
Added 7 at the front.
Added 9 at the end.
Traversing from head:   7       6       5       9
Deleted node    6
Traversing from head:   7       5       9
Inserted 10 after node  7
Inserted 11 before node 9
Traversing from head:   7       10      5       11      9

Kompleksitas Daftar Tertaut Tunggal

Ada dua jenis kompleksitas: kompleksitas waktu dan kompleksitas ruang. Kompleksitas waktu terburuk dan rata-rata sama untuk Singly Linked List.

Kompleksitas waktu untuk kasus terbaik:

  • Penyisipan di kepala dapat dilakukan di O(1). Karena kita tidak perlu menelusuri bagian dalam daftar tertaut.
  • Operasi pencarian dan penghapusan dapat dilakukan di O(1) jika elemen pencarian ada di simpul kepala.

Kompleksitas waktu untuk kasus rata-rata:

  • Penyisipan ke dalam daftar tertaut akan memakan waktu O(n) jika elemen “n” ada dalam Daftar Tertaut Tunggal.
  • Pencarian dan penghapusan juga dapat memakan waktu O(n), karena elemen pencarian dapat ada di simpul ekor. Dalam hal ini, Anda harus menelusuri seluruh daftar.

Kompleksitas Ruang pada Daftar Tertaut Tunggal

Singly Linked List mengalokasikan memori secara dinamis. Jika kita ingin menyimpan n elemen, maka akan dialokasikan n unit memori. Jadi, kompleksitas ruangnya adalah O(n).