Struktur data daftar tertaut mencakup serangkaian node yang terhubung. Di sini, setiap node menyimpan data dan alamat node berikutnya. Sebagai contoh,

Anda harus memulai di suatu tempat, jadi kami memberikan alamat node pertama nama khusus yang disebut KEPALA.

Juga, simpul terakhir dalam daftar tertaut dapat diidentifikasi karena bagian berikutnya menunjuk ke BATAL.

Anda mungkin pernah memainkan game Treasure Hunt, di mana setiap petunjuk menyertakan informasi tentang petunjuk selanjutnya. Begitulah cara daftar tertaut beroperasi.

Representasi dari Linked List

Mari kita lihat bagaimana setiap node dari daftar tertaut diwakili. Setiap node terdiri dari:

• Item data
• Alamat node lain

Kami membungkus item data dan referensi node berikutnya dalam sebuah struct sebagai:

struct node
{
  int data;
  struct node *next;
};

Memahami struktur node daftar tertaut adalah kunci untuk memahaminya.

Setiap node struct memiliki item data dan penunjuk ke node struct lain. Mari kita buat Daftar Tertaut sederhana dengan tiga item untuk memahami cara kerjanya.

/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */
one->data = 1;
two->data = 2;
three->data=3;

/* Connect nodes */
one->next = two;
two->next = three;
three->next = NULL;

/* Save address of first node in head */
head = one;

Jika Anda tidak memahami salah satu baris di atas, yang Anda butuhkan hanyalah penyegar pada pointer dan struct.

Hanya dalam beberapa langkah, kami telah membuat daftar tertaut sederhana dengan tiga node.

Kekuatan daftar tertaut berasal dari kemampuan memutus rantai dan menggabungkannya kembali. Misalnya jika Anda ingin meletakkan elemen 4 antara 1 dan 2, langkah-langkahnya adalah:

• Buat node struct baru dan alokasikan memori untuk itu.
• Tambahkan nilai datanya sebagai 4
• Arahkan penunjuk berikutnya ke node struct yang berisi 2 sebagai nilai datanya
• Ubah penunjuk berikutnya dari “1” ke simpul yang baru kita buat.

Melakukan sesuatu yang serupa dalam sebuah larik akan membutuhkan pergeseran posisi dari semua elemen berikutnya.

Di python dan Java, daftar tertaut dapat diimplementasikan menggunakan kelas seperti yang ditunjukkan pada kode di bawah ini.

Utilitas Daftar Tertaut

List adalah salah satu struktur data yang paling populer dan efisien, dengan implementasi di setiap bahasa pemrograman seperti C, C ++, Python, Java, dan C #.

Selain itu, daftar tertaut adalah cara terbaik untuk mempelajari cara kerja pointer. Dengan mempraktikkan cara memanipulasi daftar tertaut, Anda dapat mempersiapkan diri untuk mempelajari struktur data yang lebih canggih seperti grafik dan pohon.

Implementasi Daftar Tertaut dalam Contoh Python, Java, C, dan C ++

# Linked list implementation in Python


class Node:
    # Creating a node
    def __init__(self, item):
        self.item = item
        self.next = None


class LinkedList:

    def __init__(self):
        self.head = None


if __name__ == '__main__':

    linked_list = LinkedList()

    # Assign item values
    linked_list.head = Node(1)
    second = Node(2)
    third = Node(3)

    # Connect nodes
    linked_list.head.next = second
    second.next = third

    # Print the linked list item
    while linked_list.head != None:
        print(linked_list.head.item, end=" ")
        linked_list.head = linked_list.head.next

// Linked list implementation in Java

class LinkedList {
  // Creating a node
  Node head;

  static class Node {
    int value;
    Node next;

    Node(int d) {
      value = d;
      next = null;
    }
  }

  public static void main(String[] args) {
    LinkedList linkedList = new LinkedList();

    // Assign value values
    linkedList.head = new Node(1);
    Node second = new Node(2);
    Node third = new Node(3);

    // Connect nodess
    linkedList.head.next = second;
    second.next = third;

    // printing node-value
    while (linkedList.head != null) {
      System.out.print(linkedList.head.value + " ");
      linkedList.head = linkedList.head.next;
    }
  }
}

// Linked list implementation in C

#include <stdio.h>
#include <stdlib.h>

// Creating a node
struct node {
  int value;
  struct node *next;
};

// print the linked list value
void printLinkedlist(struct node *p) {
  while (p != NULL) {
    printf("%d ", p->value);
    p = p->next;
  }
}

int main() {
  // Initialize nodes
  struct node *head;
  struct node *one = NULL;
  struct node *two = NULL;
  struct node *three = NULL;

  // Allocate memory
  one = malloc(sizeof(struct node));
  two = malloc(sizeof(struct node));
  three = malloc(sizeof(struct node));

  // Assign value values
  one->value = 1;
  two->value = 2;
  three->value = 3;

  // Connect nodes
  one->next = two;
  two->next = three;
  three->next = NULL;

  // printing node-value
  head = one;
  printLinkedlist(head);
}

// Linked list implementation in C++

#include <bits/stdc++.h>
using namespace std;

// Creating a node
class Node {
   public:
  int value;
  Node* next;
};

int main() {
  Node* head;
  Node* one = NULL;
  Node* two = NULL;
  Node* three = NULL;

  // allocate 3 nodes in the heap
  one = new Node();
  two = new Node();
  three = new Node();

  // Assign value values
  one->value = 1;
  two->value = 2;
  three->value = 3;

  // Connect nodes
  one->next = two;
  two->next = three;
  three->next = NULL;

  // print the linked list value
  head = one;
  while (head != NULL) {
    printf("%d ", head->value);
    head = head->next;
  }
}

Kompleksitas Daftar Tertaut

Kompleksitas Waktu

Kompleksitas Ruang: O(n)

Aplikasi Daftar Tertaut

• Alokasi memori dinamis
• Diterapkan dalam tumpukan dan antrian
• Di membuka fungsionalitas perangkat lunak
• Tabel hash, Grafik

Bacaan yang Direkomendasikan

1. Tutorial

• Operasi Daftar Tertaut (Lintasi, Sisipkan, Hapus)
• Jenis Daftar Tertaut
• Java LinkedList

2. Contoh

• Dapatkan elemen tengah dari Linked List dalam satu iterasi
• Ubah Daftar Tertaut menjadi Array dan sebaliknya
• Deteksi loop dalam Daftar Tertaut