Python - Daftar Tertaut

Daftar tertaut adalah urutan elemen data, yang dihubungkan bersama melalui tautan. Setiap elemen data berisi koneksi ke elemen data lain dalam bentuk pointer. Python tidak memiliki daftar tertaut di pustaka standarnya. Kami menerapkan konsep daftar tertaut menggunakan konsep node seperti yang dibahas di bab sebelumnya. Kita telah melihat bagaimana kita membuat kelas simpul dan bagaimana melintasi elemen sebuah simpul. Dalam bab ini kita akan mempelajari jenis-jenis daftar tertaut yang dikenal sebagai daftar tertaut tunggal. Dalam tipe struktur data ini hanya ada satu tautan antara dua elemen data. Kami membuat daftar seperti itu dan membuat metode tambahan untuk menyisipkan, memperbarui, dan menghapus elemen dari daftar.

Pembuatan daftar Linked

Daftar tertaut dibuat dengan menggunakan kelas node yang kita pelajari di bab terakhir. Kami membuat objek Node dan membuat kelas lain untuk menggunakan objek ode ini. Kami meneruskan nilai yang sesuai melalui objek node untuk mengarahkan ke elemen data berikutnya. Program di bawah ini membuat daftar tertaut dengan tiga elemen data. Di bagian selanjutnya kita akan melihat bagaimana melintasi daftar tertaut.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

Melintasi Daftar Tertaut

Daftar tertaut tunggal dapat dilalui hanya dalam arah forwrad mulai dari elemen data pertama. Kami cukup mencetak nilai elemen data berikutnya dengan menetapkan penunjuk node berikutnya ke elemen data saat ini.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

# Link first Node to second node
list.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

list.listprint()

Ketika kode di atas dijalankan, menghasilkan hasil sebagai berikut:

Mon
Tue
Wed

Penyisipan dalam Daftar Tertaut

Memasukkan elemen dalam daftar tertaut melibatkan penugasan kembali pointer dari node yang ada ke node yang baru dimasukkan. Bergantung pada apakah elemen data baru dimasukkan di awal atau di tengah atau di akhir daftar tertaut, kami memiliki skenario di bawah ini.

Memasukkan di Awal dari Daftar Tertaut

Ini melibatkan mengarahkan penunjuk berikutnya dari node data baru ke kepala saat ini dari daftar tertaut. Jadi kepala daftar tertaut saat ini menjadi elemen data kedua dan simpul baru menjadi kepala daftar tertaut.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval
    def AtBegining(self,newdata):
        NewNode = Node(newdata)

# Update the new nodes next val to existing node
        NewNode.nextval = self.headval
        self.headval = NewNode

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtBegining("Sun")

list.listprint()

Ketika kode di atas dijalankan, menghasilkan hasil sebagai berikut:

Sun
Mon
Tue
Wed

Memasukkan di Akhir Daftar Tertaut

Ini melibatkan menunjuk penunjuk berikutnya dari simpul terakhir saat ini dari daftar tertaut ke simpul data baru. Jadi simpul terakhir saat ini dari daftar tertaut menjadi simpul data terakhir kedua dan simpul baru menjadi simpul terakhir dari daftar tertaut.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Function to add newnode
    def AtEnd(self, newdata):
        NewNode = Node(newdata)
        if self.headval is None:
            self.headval = NewNode
            return
        laste = self.headval
        while(laste.nextval):
            laste = laste.nextval
        laste.nextval=NewNode

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval


list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtEnd("Thu")

list.listprint()

Ketika kode di atas dijalankan, menghasilkan hasil sebagai berikut:

Mon
Tue
Wed
Thu

Memasukkan di antara dua Node Data

Ini melibatkan chaging pointer dari node tertentu untuk menunjuk ke node baru. Hal ini dimungkinkan dengan melewatkan kedua node baru dan node yang sudah ada setelah node baru akan dimasukkan. Jadi kami mendefinisikan kelas tambahan yang akan mengubah penunjuk berikutnya dari node baru ke penunjuk node tengah berikutnya. Kemudian tetapkan simpul baru ke penunjuk berikutnya dari simpul tengah.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Function to add node
    def Inbetween(self,middle_node,newdata):
        if middle_node is None:
            print("The mentioned node is absent")
            return

        NewNode = Node(newdata)
        NewNode.nextval = middle_node.nextval
        middle_node.nextval = NewNode

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval


list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Thu")

list.headval.nextval = e2
e2.nextval = e3

list.Inbetween(list.headval.nextval,"Fri")

list.listprint()

Ketika kode di atas dijalankan, menghasilkan hasil sebagai berikut:

Mon
Tue
Fri
Thu

Menghapus Item dari Daftar yang Disukai

Kita dapat menghapus node yang ada menggunakan kunci untuk node tersebut. Dalam program di bawah ini kami menemukan node sebelumnya dari node yang akan dihapus. Kemudian arahkan pointer berikutnya dari node ini ke node berikutnya dari node yang akan dihapus.

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class SLinkedList:
    def __init__(self):
        self.head = None

    def Atbegining(self, data_in):
        NewNode = Node(data_in)
        NewNode.next = self.head
        self.head = NewNode
		
# Function to remove node
    def RemoveNode(self, Removekey):

        HeadVal = self.head

        if (HeadVal is not None):
            if (HeadVal.data == Removekey):
                self.head = HeadVal.next
                HeadVal = None
                return

        while (HeadVal is not None):
            if HeadVal.data == Removekey:
                break
            prev = HeadVal
            HeadVal = HeadVal.next

        if (HeadVal == None):
            return

        prev.next = HeadVal.next

        HeadVal = None

    def LListprint(self):
        printval = self.head
        while (printval):
            print(printval.data),
            printval = printval.next


llist = SLinkedList()
llist.Atbegining("Mon")
llist.Atbegining("Tue")
llist.Atbegining("Wed")
llist.Atbegining("Thu")
llist.RemoveNode("Tue")
llist.LListprint()

Ketika kode di atas dijalankan, menghasilkan hasil sebagai berikut:

Thu
Wed
Mon