Memahami Implementasi Daftar Tertaut dengan Python

Struktur data memainkan peran kunci dalam dunia pemrograman. Mereka membantu kami mengatur data kami dengan cara yang dapat digunakan secara efisien.

Dalam tutorial ini, kita akan belajar tentang daftar tertaut tunggal dan daftar tertaut ganda.

Daftar tertaut adalah struktur data linier. Itu tidak menyimpan data di lokasi memori yang berdekatan seperti array. Dan setiap elemen yang ditautkan disebut node dan mereka terhubung menggunakan pointer. Node pertama dalam linked list disebut head.

Ukuran daftar tertaut bersifat dinamis. Jadi, kita dapat memiliki node sebanyak yang kita inginkan kecuali penyimpanan tersedia di perangkat.

Ada dua jenis daftar tertaut. Mari kita lihat tutorial detailnya satu per satu.

#1. Daftar Tertaut Tunggal

Daftar tertaut tunggal berisi satu penunjuk yang terhubung ke node berikutnya dalam daftar tertaut. Kita harus menyimpan data dan pointer untuk setiap node di linked list.

Node terakhir dalam linked list berisi null sebagai pointer berikutnya untuk mewakili akhir dari linked list.

Anda dapat melihat ilustrasi tautan di bawah ini.

Sekarang, kami memiliki pemahaman penuh tentang daftar tertaut tunggal. Mari kita lihat langkah-langkah untuk mengimplementasikannya dengan Python.

Implementasi Daftar Tertaut Tunggal

1. Langkah pertama adalah membuat node untuk linked list.

Bagaimana cara membuatnya?

Di Python, kita dapat dengan mudah membuat node menggunakan class. Kelas berisi data dan pointer untuk node berikutnya.

Lihatlah kode untuk node.

class Node:

	def __init__(self, data):
		## data of the node
		self.data = data

		## next pointer
		self.next = None

Kita dapat membuat simpul dengan semua jenis data menggunakan kelas di atas. Kita akan melihatnya sebentar lagi.

Sekarang, kami memiliki node bersama kami. Selanjutnya, kita harus membuat linked list dengan beberapa node. Mari buat kelas lain untuk linked list.

  Singkirkan Australis & Kembalikan Tema Klasik Di Firefox 29

2. Buat kelas bernama LinkedList dengan kepala diinisialisasi ke Tidak ada. Lihat kode di bawah ini.

class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

3. Kami memiliki kelas Node dan LinkedList bersama kami. Bagaimana kita memasukkan node baru ke dalam linked list? Jawaban sederhana mungkin menggunakan metode di kelas LinkedList. Ya, itu akan menyenangkan. Mari tulis sebuah metode untuk menyisipkan node baru ke dalam linked list.

Untuk memasukkan node baru ke dalam linked list, kita harus mengikuti langkah-langkah tertentu.

Mari kita lihat mereka.

  • Periksa apakah kepala kosong atau tidak.
  • Jika kepala kosong, tetapkan simpul baru ke kepala.
  • Jika kepala tidak kosong, dapatkan node terakhir dari linked list.
  • Tetapkan node baru ke pointer berikutnya node terakhir.

Mari kita lihat kode untuk memasukkan node baru ke dalam linked list.

class LinkedList:

	####

	def insert(self, new_node):
		## check whether the head is empty or not
		if self.head:
			## getting the last node
			last_node = self.head
			while last_node != None:
				last_node = last_node.next

			## assigning the new node to the next pointer of last node
			last_node.next = new_node

		else:
			## head is empty
			## assigning the node to head
			self.head = new_node

Hore! kami telah menyelesaikan metode untuk memasukkan simpul baru ke dalam daftar tertaut. Bagaimana kita bisa mengakses data node dari linked list?

Untuk mengakses data dari daftar tertaut, kita harus mengulang melalui tertaut menggunakan penunjuk berikutnya seperti yang kita lakukan untuk mendapatkan node terakhir dalam metode penyisipan. Mari tulis sebuah metode di dalam kelas LinkedList untuk mencetak semua data node dalam daftar tertaut.

4. Ikuti langkah-langkah di bawah ini untuk mencetak semua data node dalam linked list.

  • Inisialisasi variabel dengan kepala.
  • Tulis sebuah loop yang berulang sampai kita mencapai akhir linked list.
    • Cetak data node.
    • Pindahkan penunjuk berikutnya
  Cara Membuat USB yang Dapat Di-boot Untuk Sistem Operasi Desktop Apa Pun

Mari kita lihat kodenya.

class LinkedList:

	####

	def display(self):
		## variable for iteration
		temp_node = self.head

		## iterating until we reach the end of the linked list
		while temp_node != None:
			## printing the node data
			print(temp_node.data, end='->')

			## moving to the next node
			temp_node = temp_node.next

		print('Null')

Fiuh! kami selesai membuat tautan dengan metode yang diperlukan. Mari kita uji daftar tertaut dengan memberi contoh dengan beberapa data.

Kita dapat membuat node dengan kode Node(1). Mari kita lihat kode lengkap implementasi linked list beserta contoh penggunaannya.

class Node:

	def __init__(self, data):
		## data of the node
		self.data = data

		## next pointer
		self.next = None

class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

	def insert(self, new_node):
		## check whether the head is empty or not
		if self.head:
			## getting the last node
			last_node = self.head
			while last_node.next != None:
				last_node = last_node.next

			## assigning the new node to the next pointer of last node
			last_node.next = new_node

		else:
			## head is empty
			## assigning the node to head
			self.head = new_node

	def display(self):
		## variable for iteration
		temp_node = self.head

		## iterating until we reach the end of the linked list
		while temp_node != None:
			## printing the node data
			print(temp_node.data, end='->')

			## moving to the next node
			temp_node = temp_node.next

		print('Null')


if __name__ == '__main__':
	## instantiating the linked list
	linked_list = LinkedList()

	## inserting the data into the linked list
	linked_list.insert(Node(1))
	linked_list.insert(Node(2))
	linked_list.insert(Node(3))
	linked_list.insert(Node(4))
	linked_list.insert(Node(5))
	linked_list.insert(Node(6))
	linked_list.insert(Node(7))

	## printing the linked list
	linked_list.display()

Jalankan program di atas untuk mendapatkan hasil sebagai berikut.

1->2->3->4->5->6->7->Null

Itu saja untuk linked list. Sekarang, Anda tahu cara mengimplementasikan single-linked list. Anda dapat dengan mudah mengimplementasikan daftar tertaut ganda dengan sepengetahuan daftar tertaut tunggal. Mari selami bagian tutorial selanjutnya.

#2. Daftar Berantai Ganda

Daftar tertaut ganda berisi dua penunjuk yang terhubung ke simpul sebelumnya dan simpul berikutnya dalam daftar tertaut. Kita harus menyimpan data dan dua pointer untuk setiap node di linked list.

Penunjuk sebelumnya dari simpul pertama adalah nol dan penunjuk berikutnya dari simpul terakhir adalah nol untuk mewakili akhir dari daftar tertaut di kedua sisi.

  Cara Cepat Menemukan Preferensi Sistem Tertentu di Mac

Anda dapat melihat ilustrasi tautan di bawah ini.

Double-linked list juga memiliki langkah-langkah yang mirip dengan single-linked list dalam implementasinya. Sekali lagi menjelaskan hal yang sama akan membosankan bagi Anda. Telusuri kode di setiap langkah dan Anda akan memahaminya dengan sangat cepat. Ayo pergi.

Penerapan Doubly Linked List

1. Membuat simpul untuk daftar tertaut ganda dengan penunjuk simpul sebelumnya, data, dan penunjuk simpul berikutnya.

class Node:

	def __init__(self, data):
		## previous pointer
		self.prev = None

		## data of the node
		self.data = data

		## next pointer
		self.next = None

2. Kelas daftar tertaut ganda.

class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

3. Metode untuk menyisipkan node baru ke dalam double-linked list.

class LinkedList:

	####

	def insert(self, new_node):
		## check whether the head is empty or not
		if self.head:
			## getting the last node
			last_node = self.head
			while last_node.next != None:
				last_node = last_node.next

			## assigning the last node to the previous pointer of the new node
			new_node.prev = last_node

			## assigning the new node to the next pointer of last node
			last_node.next = new_node

4. Metode untuk menampilkan data double-linked list.

class LinkedList:

	####

	def display(self):

		## printing the data in normal order
		print("Normal Order: ", end='')

		temp_node = self.head
		while temp_node != None:
			print(temp_node.data, end=' ')
			temp_node = temp_node.next
		print()

		## printing the data in reverse order using previous pointer
		print("Reverse Order: ", end='')

		## getting the last node
		last_node = self.head
		while last_node.next != None:
			last_node = last_node.next

		temp_node = last_node
		while temp_node != None:
			print(temp_node.data, end=' ')
			temp_node = temp_node.prev
		print()

Kami telah melihat kode dari daftar tertaut ganda. Dan tidak ada kode untuk penggunaan kelas daftar tertaut ganda. Itu untukmu. Gunakan kelas daftar tertaut ganda yang mirip dengan daftar tertaut tunggal. Selamat bersenang-senang 🙂

Kesimpulan

Anda dapat menemukan banyak masalah berdasarkan linked list. Namun, Anda harus mengetahui implementasi dasar dari link yang telah Anda pelajari dalam tutorial ini. Semoga Anda bersenang-senang mempelajari konsep baru.

Selamat Coding 🙂