Daftar Tertaut Tunggal dalam Struktur Data

Oleh: Sarah Chen Sarah Chen
Hours Updated

⚡ Ringkasan Cerdas

Singly Linked List adalah struktur data linier dan searah di mana setiap node menyimpan data dan satu pointer ke node berikutnya, sehingga penelusuran hanya bergerak dari kepala ke ekor dan memori dialokasikan secara dinamis saat node baru ditambahkan.

  • 🧩 Struktur Node: Setiap node menyimpan satu bidang data dan satu berikutnya penunjuk ke node berikut; node ekor berikutnya Pointer bernilai NULL.
  • 📦 Daftar vs. Larik: Singly Linked List lebih disukai ketika jumlah elemen tidak diketahui, akses acak tidak diperlukan, dan penyisipan di tengah daftar sering terjadi.
  • ➕ Sisipan: Node dapat ditambahkan di bagian kepala, di bagian ekor, setelah node yang cocok, atau sebelum node yang cocok menggunakan penulisan ulang penunjuk berikutnya.
  • ➖ Penghapusan: Menghapus head, tail, atau node yang dicari akan memperbarui pointer tetangga dan membebaskan memori yang dilepaskan untuk menghindari kebocoran memori.
  • 🔁 Penelusuran: Hanya penelusuran maju yang didukung karena tidak ada penunjuk sebelumnya, sehingga penelusuran mundur pada Singly Linked List tidak dimungkinkan.
  • ???? C++ ke Python Code: Implementasi lengkap menunjukkan rutinitas penyisipan, penghapusan, pencarian, dan penelusuran dengan output yang dapat dijalankan.
  • 📊 Kompleksitas: Penyisipan atau penghapusan kepala adalah O(1); pencarian dan penyisipan serta penghapusan lainnya adalah O(n); kompleksitas ruang adalah O(n).
Baca Selengkapnya

Daftar Tertaut Tunggal

Apa itu Daftar Tertaut Tunggal?

Singly Linked List (SLI) adalah struktur data linier dan searah di mana data disimpan pada node, dan setiap node terhubung melalui tautan ke node berikutnya. Setiap node berisi bidang data dan tautan ke node berikutnya. SINGLY Linked List hanya dapat dilalui dalam satu arah, sedangkan Linked List (LI) dapat dilalui dalam satu arah. Daftar Tertaut Ganda dapat dilalui dari kedua arah.

Berikut adalah struktur node dari Linked List Tunggal:

Struktur Node dalam Daftar Tertaut

Struktur Node dalam Daftar Tertaut

Mengapa Menggunakan Linked List Dibandingkan Array?

Beberapa skenario lebih mendukung penggunaan Linked List daripada sebuah array. susunan:

  • Jumlah elemen yang tidak diketahui: Ketika jumlah elemen yang dibutuhkan tidak diketahui pada saat kompilasi, Linked List akan mengalokasikan memori secara dinamis saat elemen ditambahkan.
  • Akses acak: Jika akses terindeks secara acak tidak diperlukan, Linked List adalah pilihan yang tepat.
  • Penyisipan di tengah: Menyisipkan elemen di tengah array memerlukan pergeseran elemen. Linked List memungkinkan penyisipan di posisi mana pun hanya dengan menulis ulang beberapa pointer.

Operations dari Daftar Tertaut Tunggal

Singly Linked List (SIL) cocok untuk alokasi memori dinamis. SIL mendukung operasi standar linked list, yaitu penyisipan, penghapusan, pencarian, pembaruan, penggabungan dua list, dan penelusuran.

Operasi-operasi berikut dibahas dalam artikel ini:

  • 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 adalah contoh linked list dengan empat node.

Contoh Daftar Tertaut Tunggal

Contoh Daftar Tertaut Tunggal

Penyisipan di Bagian Awal Daftar Bertautan Tunggal

Ini adalah operasi sederhana. Secara umum dikenal sebagai penambahan elemen ke dalam Singly Linked List. Sebuah node baru dibuat dan ditempatkan di kepala daftar.

Untuk melakukan operasi ini, ikuti dua kondisi penting:

  1. Jika daftar tersebut kosong, node yang baru dibuat menjadi node kepala, dan seterusnya. berikutnya Pointer bernilai NULL.
  2. Jika daftar tersebut tidak kosong, node baru tersebut menjadi node kepala, dan seterusnya. berikutnya Pointer menunjuk ke node kepala sebelumnya.

Berikut adalah pseudocode untuk memasukkan node di kepala linked list:

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 Bertautan Tunggal

Menyisipkan node di akhir linked list mirip dengan menyisipkan di kepala. Telusuri hingga node ekor, lalu arahkan ke node tersebut. berikutnya Penunjuk ke node baru. Jika head bernilai NULL, node baru tersebut menjadi head.

Langkah 1) Lintasi hingga berikutnya Pointer dari node saat ini menjadi NULL.

Langkah 2) Buat node baru dengan nilai yang ditentukan.

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

Berikut adalah pseudokode untuk menyisipkan elemen di bagian akhir daftar tunggal:

function insertAtEnd(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  while head.next is not NULL:
    head = head.next
  head.next = newNode
  newNode.next = NULL

Memasukkan di Ekor

Memasukkan di bagian ekor

Penyisipan Setelah Node dalam Daftar Berantai Tunggal

Menyisipkan node setelah node target memiliki dua bagian: mencari node target dan memasang node baru setelahnya. Telusuri daftar hingga ditemukan kecocokan, lalu sisipkan node baru tersebut.

Langkah 1) Lakukan penelusuran hingga nilai node saat ini sama dengan item pencarian.

Langkah 2) Tetapkan node baru berikutnya penunjuk ke node saat ini berikutnya penunjuk.

Langkah 3) Arahkan simpul saat ini berikutnya penunjuk ke node baru.

Kode semu:

function insertAfter(head, value, searchItem):
  newNode = Node(value)
  while head.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

Memasukkan Node Setelah Node dalam Daftar Tertaut Tunggal

Memasukkan node demi node dalam Single Linked List

Penyisipan Sebelum Node dalam Daftar Berantai Tunggal

Ini mirip dengan penyisipan setelah sebuah node. Telusuri hingga node berikutnya cocok dengan nilai pencarian, lalu sisipkan node baru sebelum node tersebut.

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

Langkah 2) Buat node baru dan atur propertinya. berikutnya penunjuk ke node saat ini berikutnya.

Langkah 3) Arahkan simpul saat ini berikutnya ke node baru.

function insertBefore(head, value, searchItem):
  newNode = Node(value)
  while head.next.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

Menyisipkan Node Sebelum Node dalam Daftar Tertaut Tunggal

Memasukkan node sebelum node dalam Daftar Tertaut Tunggal

ARTIKEL TERKAIT

Hapus Head dari Linked List Tunggal

Pointer kepala diberikan sebagai parameter. Node kepala dihapus, dan node berikutnya menjadi kepala yang baru. Memori node yang dihapus harus dibebaskan untuk menghindari kebocoran memori.

Langkah 1) Tetapkan node berikutnya dari head sebagai head yang baru.

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

Langkah 3) Kembalikan node kepala baru.

function deleteHead(head):
  temp = head
  head = head.next
  free(temp)
  return head

Menghapus Kepala daftar Tertaut

Menghapus kepala daftar tertaut

Hapus Ekor dari Linked List Tunggal

Menghapus node ekor mirip dengan menghapus node kepala. Perbedaannya adalah diperlukan penelusuran hingga akhir daftar. Dalam Singly Linked List, node yang berikutnya Pointer bernilai NULL, yang merupakan node ekor.

Langkah 1) Telusuri hingga tepat sebelum simpul ekor. Simpan simpul saat ini.

Langkah 2) Bebaskan memori node berikutnya (ekor).

Langkah 3) Atur node berikutnya dari node saat ini menjadi NULL.

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

Mencari dan Menghapus Node dari Linked List Tunggal

Fungsi ini melakukan dua tugas: mencari dan menghapus. Telusuri hingga akhir daftar. Jika simpul yang cocok ditemukan, hapus simpul tersebut dan tautkan kembali simpul sebelumnya. berikutnya penunjuk.

Langkah 1) Telusuri hingga akhir daftar. Periksa apakah node saat ini sama dengan node yang dicari.

Langkah 2) Jika ditemukan kecocokan, simpan penunjuk ke node saat ini.

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

Langkah 4) Hapus node saat ini dan bebaskan memorinya.

function searchAndDelete(head, searchItem):
  while head.next.next is not NULL and head.next.value != searchItem:
    head = head.next
  temp = head.next
  head.next = head.next.next
  free(temp)

Cari dan Hapus Node dari Daftar Tertaut Tunggal

Cari dan hapus node dari Single Linked List

Menjelajahi Daftar Berantai Tunggal

Singly Linked List hanya mendukung penelusuran dari kepala ke ekor. Tidak ada penunjuk ke node sebelumnya, sehingga penelusuran terbalik tidak mungkin dilakukan. Setiap node dikunjungi secara berurutan, mencetak nilainya hingga mencapai NULL.

Langkah 1) Telusuri setiap node hingga mencapai NULL.

Langkah 2) Cetak nilai node saat ini.

function traverse(head):
  while head is not NULL:
    print head.value
    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);
    return;
  }
  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 = NULL;
  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);
        break;
      } else {
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
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 = 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

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.')
  def insertAtEnd(self, value):
    if self.head is None:
      self.insertAtHead(value)
      return
    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):
    if self.head is None:
      return
    if self.head.data == searchItem:
      self.head = self.head.next
      print(f'Deleted node\t{searchItem}')
      return
    currentNode = self.head
    while currentNode.next is not None:
      if currentNode.next.data == searchItem:
        currentNode.next = currentNode.next.next
        print(f'Deleted node\t{searchItem}')
        return
      currentNode = currentNode.next
  def insertAfter(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} after node\t{searchItem}')
  def insertBefore(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} before node\t{searchItem}')
  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 kasus terburuk dan rata-rata sama untuk Singly Linked List.

Kompleksitas waktu kasus terbaik:

  • Penyisipan di bagian depan dapat dilakukan dalam O(1). Tidak diperlukan penelusuran di dalam daftar.
  • Pencarian dan penghapusan dapat dilakukan dalam O(1) jika elemen target berada di node kepala.

Kompleksitas waktu kasus rata-rata:

  • Penyisipan ke dalam linked list membutuhkan waktu O(n), di mana n adalah jumlah total elemen.
  • Pencarian dan penghapusan juga dapat memakan waktu O(n), karena elemen target dapat berada di mana saja hingga simpul ekor.

Kompleksitas ruang dari Daftar Berantai Tunggal

Sebuah Singly Linked List mengalokasikan memori secara dinamis. Untuk menyimpan n elemen, ia mengalokasikan n unit memori. Jadi kompleksitas ruangnya adalah O(n).

Aplikasi dari Linked List Tunggal

Linked List Tunggal muncul di banyak tempat di mana penelusuran maju saja dan memori dinamis berguna:

  • Tumpukan dan antrian: Penyimpanan dasar untuk tumpukan LIFO dan antrian FIFO yang dibangun dari node.
  • Rantai tabel hash: Konflik diselesaikan dengan menggabungkan entri ke dalam Singly Linked List per bucket.
  • Daftar yang berdekatan: Graf jarang menggunakan Daftar Berantai Tunggal (Singly Linked List) dari tetangga untuk setiap simpul.
  • Tabel simbol: Compiler dan interpreter menghubungkan pengidentifikasi ke dalam Daftar Berantai Tunggal (Singly Linked List) per cakupan.
  • Pengalokasi memori: Pengalokasi daftar bebas track blok bebas sebagai Daftar Berantai Tunggal.

Pertanyaan Umum Demo Slot

Singly Linked List menghubungkan sampel pelatihan, mini-batch, dan blok memori kosong di dalam kerangka kerja AI, memungkinkan antrian dinamis untuk input streaming dan pipeline data tanpa penguncian yang dapat diskalakan sesuai dengan kebutuhan model.

Ya. GitHub Copilot dan GPT dapat menghasilkan Linked List tunggal lengkap dalam bahasa C. C++, Java, Python, atau JavaSkrip, termasuk penyisipan, penghapusan, pembalikan, deteksi siklus, dan pengujian unit.

Linked List Tunggal hanya memiliki satu pointer next dan hanya menelusuri ke depan. Linked List Ganda memiliki pointer next dan prev serta menelusuri ke kedua arah tetapi menggunakan lebih banyak memori per node.

Penggunaan umum meliputi implementasi stack dan queue, hash-table chaining, adjacency list untuk sparse graph, symbol table dalam compiler, free-list allocators, dan undo history dalam editor ringan.

Penyisipan atau penghapusan di kepala adalah O(1). Penyisipan di ekor, pencarian, penyisipan pada suatu posisi, dan penghapusan node tertentu semuanya membutuhkan biaya O(n) karena diperlukan penelusuran dari kepala.

Linked List dapat bertambah besar dan kecil saat runtime, melakukan penyisipan atau penghapusan dalam O(1) setelah posisinya diketahui, dan tidak pernah membutuhkan memori yang berdekatan. Array menawarkan akses acak O(1) dan lokalisasi cache yang lebih baik.

Telusuri daftar dengan tiga penunjuk, prev, curr, dan next. Pada setiap langkah, simpan curr.next, arahkan curr.next ke prev, dan geser prev dan curr ke depan. Kembalikan prev sebagai head yang baru.

Algoritma kura-kura dan kelinci Floyd menggunakan dua penunjuk yang bergerak dengan kecepatan berbeda. Jika keduanya bertemu, daftar tersebut berisi siklus. Jika tidak, penunjuk yang bergerak cepat mencapai NULL dan tidak ada siklus.

Ringkaslah postingan ini dengan: