Algoritmussorozat — Linkolt lista

Linkelt lista

A linkelt lista az egyik legegyszerűbb adatstruktúra. Ez egy csomópontok tömbje, amelyek mutatókkal vannak összekötve.

A lista minden csomópontja tartalmaz egy értéket és egy mutatót a lista következő csomópontjára. Ez a viselkedés lehetővé teszi, hogy a csatolt lista dinamikus tömbként viselkedjen, ahol a méret nincs rögzítve, és még a létrehozása után is módosítható (a hagyományos statikus tömböktől eltérően).

A linkelt listának a három alapvető műveletet támogatnia kell: keresés, beillesztés és törlés.

Futási idők

Beszúrás:

Beszúrás az elején: O(1)
Beszúrás a végén: O(n) (legrosszabb esetben, amikor a végére kell haladnunk, hogy új csomópontot szúrjunk be)
Beszúrás egy adott pozícióba: O(n) (legrosszabb esetben, amikor az adott pozícióba kell áthaladnunk egy új csomópont beillesztéséhez)

Törlés:

Törlés az elején: O(1)
Törlés a végén: O(n) (legrosszabb esetben, amikor a végére kell haladnunk egy csomópont törléséhez)
Törlés egy adott pozícióban: O(n) (legrosszabb esetben, amikor egy csomópont törléséhez az adott pozícióba kell áthaladnunk)

Keresés: O(n) (a legrosszabb esetben, amikor a lista összes elemén keresztül kell haladnunk, hogy megtaláljunk egy adott elemet)

Linkelt lista megvalósítása

1. Hivatkozott lista létrehozása

Először hozzuk létre a Node osztályt a lista csomópontjainak megjelenítésére. Mint említettük, minden csomópontnak van értéke és egy mutatója a következő csomópontra.

class Node:
    def __init__(self, value, next = None) -> None:
        self.value = value
        self.next = next

Ezután a LinkedList osztály. Hozzáadom a __repr__ metódust is, hogy ki tudjuk nyomtatni a lista elemeit.

class LinkedList:
    def __init__(self, head: Node = None):
        """
        # Consturctor #1 - Empty Linked List
        """
        self.head = head

  def __repr__(self):
        """
        Print Linked List
        """
        items = ''
        current_node = self.head
        while current_node != None:
            items += str(current_node.value) + '-->'
            current_node = current_node.next
        return f"LinkedList({items[:-3]})"

Nézzük meg, hogyan hozhatunk létre linkelt listát:

# Creating a linked list
head = Node(2)
head.next = Node(1)
head.next.next = Node(4)
head.next.next.next = Node(3)
head.next.next.next.next = Node(5)
head.next.next.next.next.next = Node(6)

linked_list = LinkedList(head)

# print list
print(linked_list)

# Output:
# LinkedList(2-->1-->4-->3-->5-->6)

Ezután létrehozhatunk egy második konstruktort az osztályhoz, amely lehetővé teszi a linkelt listák könnyebb létrehozását. Tegyük fel, hogy lehetővé akarjuk tenni a felhasználók számára, hogy értéklista átadásával linkelt listákat hozzanak létre. Megtehetjük így:

class LinkedList:
    def __init__(self, head: Node = None):
        """
        # Consturctor #1 - Empty Linked List
        """
        self.head = head

  def __repr__(self):
        """
        Print Linked List
        """
        items = ''
        current_node = self.head
        while current_node != None:
            items += str(current_node.value) + '-->'
            current_node = current_node.next
        return f"LinkedList({items[:-3]})"

  @classmethod
    def generate_list(cls, *args):
        """
        Constructor #2 - Generate Linked List from list of values
        """
        head = Node(args[0])
        current_node = head
        for value in args[1:]:
            current_node.next = Node(value)
            current_node = current_node.next

        return cls(head = head)

Mostantól sokkal könnyebben hozhatunk létre egy linkelt listát:

linked_list = LinkedList.generate_list(2,1,4,3,5,6)
print(linked_list)

# Output
# LinkedList(2-->1-->4-->3-->5-->6)

2. Keresés

Az érték keresése egy linkelt listában magában foglalja a listán való bejárást, amíg el nem érjük a None értéket (lista vége), vagy meg nem találjuk a keresett értékkel rendelkező csomópontot.

class Node:
    def __init__(self, value, next = None) -> None:
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self, head: Node = None):
        """
        # Consturctor #1 - Empty Linked List
        """
        self.head = head

    @classmethod
    def generate_list(cls, *args):
        """
        Constructor #2 - Generate Linked List from list of values
        """
        head = Node(args[0])
        current_node = head
        for value in args[1:]:
            current_node.next = Node(value)
            current_node = current_node.next

        return cls(head = head)
    
    def __repr__(self):
        """
        Print Linked List
        """
        items = ''
        current_node = self.head
        while current_node != None:
            items += str(current_node.value) + '-->'
            current_node = current_node.next
        return f"LinkedList({items[:-3]})"
        
    def index(self, index):
        """
        Seach a value in Linked List. Return -1 if not found
        Description:
            - Iterate through the linked list
            - If value is found, return the value
            - If value is not found, return -1
        """
        current_node = self.head
        while current_node != None:
            if index == 0:
                return current_node.value
            else:
                index -= 1
                current_node = current_node.next
        return -1

Lássunk egy példát:

linked_list = LinkedList.generate_list(2,1,4,3,5,6)
print(linked_list.index(2)) 

# Output:
# 4

2. Helyezze be

Hasonló logika a kereséshez. Haladjon végig a listán, amíg el nem éri a kívánt indexhelyet. Hozzon létre egy csomópontot, és helyezze be a listában arra a helyre.

Ezután frissítenünk kell a listában szereplő hivatkozásokat. Az új csomópontnak a lista következő csomópontjára kell mutatnia. Az előző csomópontnak pedig az új csomópontra kell mutatnia.

class Node:
    def __init__(self, value, next = None) -> None:
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self, head: Node = None):
        """
        # Consturctor #1 - Empty Linked List
        """
        self.head = head

    @classmethod
    def generate_list(cls, *args):
        """
        Constructor #2 - Generate Linked List from list of values
        """
        head = Node(args[0])
        current_node = head
        for value in args[1:]:
            current_node.next = Node(value)
            current_node = current_node.next

        return cls(head = head)
    
    def __repr__(self):
        """
        Print Linked List
        """
        items = ''
        current_node = self.head
        while current_node != None:
            items += str(current_node.value) + '-->'
            current_node = current_node.next
        return f"LinkedList({items[:-3]})"
        
    def index(self, index):
        """
        Seach a value in Linked List. Return -1 if not found
        Description:
            - Iterate through the linked list
            - If value is found, return the value
            - If value is not found, return -1
        """
        current_node = self.head
        while current_node != None:
            if index == 0:
                return current_node.value
            else:
                index -= 1
                current_node = current_node.next
        return -1

    def insert(self, value, index):
        """
        Insert a value at a given index
        """
        if len(self) < index:
            print("Index not in Range")
            return None

        current_node = self.head
        while current_node != None:
            if index == 1:
                next = current_node.next 
                current_node.next = Node(value) 
                current_node.next.next = next
                return 
            else:
                index -= 1
                current_node = current_node.next

  def __len__(self):
        """
        Return the length of the linked list
        """
        current_node = self.head
        counter = 0
        while current_node != None:
            counter += 1
            current_node = current_node.next
        return counter

Lássunk egy példát:

# Creating a linked list
linked_list = LinkedList.generate_list(2,1,4,3,5,6)

# Inserting a value
linked_list.insert(value=20, index=2)

# Print list
print(linked_list)

# Output:
# LinkedList(2-->1-->20-->4-->3-->5-->6)

3. Törlés

Egy csomópont törléséhez meg kell találnunk a csomópontot, majd törölnünk kell. Ezután frissítenünk kell az előző és a következő csomópont mutatóit, hogy egymásra mutassanak.

class Node:
    def __init__(self, value, next = None) -> None:
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self, head: Node = None):
        """
        # Consturctor #1 - Empty Linked List
        """
        self.head = head

    @classmethod
    def generate_list(cls, *args):
        """
        Constructor #2 - Generate Linked List from list of values
        """
        head = Node(args[0])
        current_node = head
        for value in args[1:]:
            current_node.next = Node(value)
            current_node = current_node.next

        return cls(head = head)
    
    def __repr__(self):
        """
        Print Linked List
        """
        items = ''
        current_node = self.head
        while current_node != None:
            items += str(current_node.value) + '-->'
            current_node = current_node.next
        return f"LinkedList({items[:-3]})"
        
    def index(self, index):
        """
        Seach a value in Linked List. Return -1 if not found
        Description:
            - Iterate through the linked list
            - If value is found, return the value
            - If value is not found, return -1
        """
        current_node = self.head
        while current_node != None:
            if index == 0:
                return current_node.value
            else:
                index -= 1
                current_node = current_node.next
        return -1

    def insert(self, value, index):
        """
        Insert a value at a given index
        """
        if len(self) < index:
            print("Index not in Range")
            return None

        current_node = self.head
        while current_node != None:
            if index == 1:
                next = current_node.next 
                current_node.next = Node(value) 
                current_node.next.next = next
                return 
            else:
                index -= 1
                current_node = current_node.next

    def delete(self, index):
        """
        Delete a node at specifc index
        """
        current_node = self.head
        while current_node != None:
            if index == 1:
                current_node.next = current_node.next.next
                break
            else:
                index -= 1
                current_node = current_node.next
        
    def __len__(self):
        """
        Return the length of the linked list
        """
        current_node = self.head
        counter = 0
        while current_node != None:
            counter += 1
            current_node = current_node.next
        return counter

Lássunk egy példát:

# Creating a linked list
linked_list = LinkedList.generate_list(2,1,4,3,5,6)

# Delete the node at index 2
linked_list.delete(index=2)

# Print list
print(linked_list)

# Output:
# LinkedList(2-->1-->3-->5-->6)

Vegye figyelembe, hogy ez a megvalósítás a linkelt lista alapformája, testreszabhatjuk és kell is, hogy megfeleljen az igényeinknek. Ezenkívül a Python két beépített adatstruktúrával rendelkezik, amelyek linkelt listaként viselkedhetnek, ezek a Lists és collections.deque. A legtöbb esetben jobb lenne, ha ezt a két adatstruktúrát használnánk.

Ha nincs szükség speciális testreszabásra, akkor először ezeket a beépített adatstruktúrákat kell használnunk. A linkelt listák hasznosabbak olyan nyelvekben, mint a C, amelyek statikus tömböket tartalmaznak. Az adatstruktúra megvalósításának ismerete azonban hasznos lehet bizonyos helyzetekben, és hozzájárul ahhoz, hogy jobban megértse, hogyan épülnek fel és hogyan viselkednek más adatstruktúrák.

hasonló anyagok:

Új anyagok

A rádiógomb ellenőrzött eseményének használata a jQueryben

Ebben a cikkben látni fogjuk, hogyan kell dolgozni a jquery választógombbal ellenőrzött eseményeivel. A választógombok HTML gombok, amelyek segítenek kiválasztani egyetlen értéket egy csoportból...

Körkörös függőségek megoldása terraformban adatforrásokkal – lépésről lépésre

Mi az a körkörös függőségek Dolgozzunk egy egyszerű eseten, amikor az SQS-sor és az S3-vödör közötti körkörös függőség problémája van egy egymástól függő címkeérték miatt. provider..

Miért érdemes elkezdeni a kódolást 2023-ban?

01100011 01101111 01100100 01100101 — beep boop beep boop Világunk folyamatosan fejlődik a technológia körül, és naponta fejlesztenek új technológiákat a valós problémák megoldására. Amint..

🎙 Random Noise #2 – Örökbefogadás és hit

az analitika íratlan világának gondozása Szeretné, hogy ezek a frissítések a postaládájába kerüljenek? Iratkozzon fel itt . "Ha önvezető autókat gyártanak, akkor mi miért ne..

A legrosszabb politika és prediktív modellek májátültetésre jelöltek számára az Egyesült Államokban

A máj (vagy óangolul lifer) az emberi test legnehezebb belső szervére utal, amely csendesen működik a nap 24 órájában. Mit csinál a máj? 500 feladatot hajt végre a szervezet egészségének..

5 webhely, amely 2022-ben fejleszti front-end fejlesztői készségeit

Frontendmentor.io A tényleges projektek létrehozásával a Frontendmentor.io segítséget nyújt a front-end kódolási képességeinek fejlesztésében. A kódolást azután kezdheti meg, hogy..

Mikor kell használni a Type-t az interfészhez képest a TypeScriptben?

A TypeScript a JavaScript gépelt szuperkészlete, amely statikus gépelést ad a nyelvhez. Ez megkönnyíti a robusztus és karbantartható kód írását azáltal, hogy a hibákat a fordítási időben..

Címkék

Machine Learning JavaScript Artificial Intelligence Data Science Python Software Development Web Development Coding Deep Learning AI React Nodejs Front End Development Software Engineering Javascript Tips NLP Computer Science HTML Neural Networks Algorithms Tech Development Typescript Python Programming CSS ChatGPT Javascript Development Statistics Data Java Science Golang Code Data Structures Open Source Software DevOps Programming Languages