Struktur Data LinkedList

Daftar Isi

Representasi LinkedList
Utilitas Daftar Tertaut
Implementasi Daftar Tertaut dalam Contoh Python, Java, C, dan C ++
Kompleksitas Daftar Tertaut
Aplikasi Daftar Tertaut

Dalam tutorial ini, Anda akan belajar tentang struktur data daftar tertaut dan implementasinya dalam Python, Java, C, dan C ++.

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

Struktur Data LinkedList

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

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

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

Representasi LinkedList

Mari kita lihat bagaimana setiap node dari LinkedList direpresentasikan. 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 penyegaran pada pointer dan struct.

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

Representasi LinkedList

Kekuatan LinkedList berasal dari kemampuan untuk memutuskan rantai dan bergabung 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 pointer berikutnya dari "1" ke node 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 yang bagus 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 ++

Python Java C 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 #include // 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 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; ) )