Példákkal magyarázott adatszerkezetek - összekapcsolt lista

Programozás

Ahogy a füzér virágokkal készül, a csatolt lista csomópontokból áll. Az adott füzér minden virágát csomópontnak hívjuk. És mindegyik csomópont a lista következő csomópontjára mutat, valamint rendelkezik adatokkal (itt ez a virág típusa).

Típusok

Egyszerűen összekapcsolt lista

Az egyesével összekapcsolt listák olyan csomópontokat tartalmaznak, amelyeknek van datamezője, valamint nextmezője, amely a sorozat következő csomópontjára mutat. Az egymással összekapcsolt listákon végrehajtható műveletek a beillesztés, a törlés és a bejárás.

 head | | +-----+--+ +-----+--+ +-----+------+ | 1 |o-----> | 2 |o-----> | 3 | NULL | +-----+--+ +-----+--+ +-----+------+

A CPython belső megvalósítása, a keretek és az értékelt változók veremben vannak.

Ehhez csak előre kell fordítanunk az aur-t, hogy megkapja a fejét, ezért egyedül linkelt listát használunk.

Kétségkívül összekapcsolt lista

A kétszeresen összekapcsolt listák tartalmaznak olyan csomópontot, amelynek datamezője, nextmezője és egy másik prevlinkmezője a sorozat előző csomópontjára mutat.

 head | | +------+-----+--+ +--+-----+--+ +-----+------+ | | |o------> | |o------> | | | | NULL | 1 | | 2 | | 3 | NULL | | | | <------o| | <------o| | | +------+-----+--+ +--+-----+--+ +-----+------+

A böngésző gyorsítótára, amely lehetővé teszi a VISSZA és ELŐRE gomb megnyomását. Itt fenn kell tartanunk egy kétszeresen összekapcsolt listát, URLsmint adatmező, hogy mindkét irányba hozzáférhessünk. Az előző URL-hez a prevmezőt fogjuk használni , a következő oldalra pedig a nextmezőt fogjuk használni .

Kör alakú összekapcsolt lista

A körkörös összekapcsolt listák egyenként összekapcsolt listák, amelyekben az utolsó nextmezõ a mezõ a szekvencia elsõ csomópontjára mutat.

 head | | +-----+--+ +-----+--+ +-----+--+ —> | 1 |o-----> | 2 |o-----> | 3 |o----| +-----+--+ +-----+--+ +-----+--+

Az időmegosztás problémáját az operációs rendszer megoldotta.

Időmegosztásos környezetben az operációs rendszernek karban kell tartania a jelenlegi felhasználók listáját, és váltakozva lehetővé kell tennie minden felhasználó számára, hogy egyszerre csak egy felhasználót használjon a CPU idő kis részében. Az operációs rendszer kiválaszt egy felhasználót, hagyja, hogy egy kis CPU-időt használjon, majd továbblépjen a következő felhasználóhoz.

Ehhez az alkalmazáshoz nem lehet NULL mutató, hacsak egyáltalán nincs olyan, aki CPU-időt kérne, azaz a lista üres.

Alapműveletek

Beszúrás

Új elem hozzáadása a listához.

Beszúrás az elején:

  • Hozzon létre egy új csomópontot a megadott adatokkal.
  • Mutasson új csomópontot nexta régire head.
  • Mutasson headerre az új csomópontra.

Beillesztés a közepébe / végébe.

Beszúrás az X csomópont után.

  • Hozzon létre egy új csomópontot a megadott adatokkal.
  • Mutasson új csomópontokat nexta régi X-ekre next.
  • X pont nexterre az új csomópontra.

Időkomplexum: O (1)

Törlés

Meglévő elem törlése a listáról.

Törlés az elején

  • Szerezd meg a csomópontot headHőm.
  • Mutasson heada Temp's-ra next.
  • A Temp csomópont által használt szabad memória.

Törlés a közepén / végén.

Törlés az X csomópont után.

  • Szerezd meg a csomópontot XHőm.
  • X pont nexta hőmérséklethez next.
  • A Temp csomópont által használt szabad memória.

Időkomplexum: O (1)

Traversing

Utazni a listán.

Traversal

  • Szerezd meg a csomópontot headaktuálisként.
  • Ellenőrizze, hogy a Current nem null, és jelenítse meg.
  • Mutasson az Áram áramra nextés lépjen a fenti lépésre.

Időkomplexitás: O (n) // Itt n a linklista mérete

Végrehajtás

Egyszerűen összekapcsolt lista C ++ megvalósítása

// Header files #include  struct node { int data; struct node *next; }; // Head pointer always points to first element of the linked list struct node *head = NULL;

Adatok nyomtatása az egyes csomópontokban

// Display the list void printList() { struct node *ptr = head; // Start from the beginning while(ptr != NULL) { std::cout

Insertion at the beginning

// Insert link at the beginning void insertFirst(int data) { // Create a new node struct node *new_node = new struct node; new_node->data = data; // Point it to old head new_node->next = head; // Point head to new node head = new_node; std::cout << "Inserted successfully" << std::endl; }

Deletion at the beginning

// Delete first item void deleteFirst() { // Save reference to head struct node *temp = head; // Point head to head's next head = head->next; // Free memory used by temp temp = NULL: delete temp; std::cout << "Deleted successfully" << std::endl; }

Size

// Find no. of nodes in link list void size() { int length = 0; struct node *current; for(current = head; current != NULL; current = current->next) { length++; } std::cout << "Size of Linked List is " << length << std::endl; }

Searching

// Find node with given data void find(int data){ // Start from the head struct node* current = head; // If list is empty if(head == NULL) { std::cout << "List is empty" next == NULL){ std::cout << "Not Found"

Deletion after a node

// Delete a node with given data void del(int data){ // Start from the first node struct node* current = head; struct node* previous = NULL; // If list is empty if(head == NULL){ std::cout << "List is empty" next == NULL){ std::cout << "Element not found" 
       
        next; } else { // Skip the current node previous->next = current->next; } // Free space used by deleted node current = NULL; delete current; std::cout << "Deleted succesfully" << std::endl; }

Python Implementation of Singly Linked List

class Node(object): # Constructor def __init__(self, data=None, next=None): self.data = data self.next = next # Function to get data def get_data(self): return self.data # Function to get next node def get_next(self): return self.next # Function to set next field def set_next(self, new_next): self.next = new_next class LinkedList(object): def __init__(self, head=None): self.head = head

Insertion

 # Function to insert data def insert(self, data): # new_node is a object of class Node new_node = Node(data) new_node.set_next(self.head) self.head = new_node print("Node with data " + str(data) + " is created succesfully")

Size

 # Function to get size def size(self): current = self.head count = 0 while current: count += 1 current = current.get_next() print("Size of link list is " + str(count))

Searching

 # Function to search a data def search(self, data): current = self.head found = False while current and found is False: if current.get_data() == data: found = True else: current = current.get_next() if current is None: print("Node with data " + str(data) + " is not present") else: print("Node with data " + str(data) + " is found")

Deletion after a node

 # Function to delete a node with data def delete(self, data): current = self.head previous = None found = False while current and found is False: if current.get_data() == data: found = True else: previous = current current = current.get_next() if current is None: print("Node with data " + str(data) + " is not in list") elif previous is None: self.head = current.get_next() print("Node with data " + str(data) + " is deleted successfully") else: previous.set_next(current.get_next()) print("Node with data " + str(data) + " is deleted successfully")

Advantages

  1. Linked lists are a dynamic data structure, which can grow and shrink, allocating and deallocating memory while the program is running.
  2. Insertion and deletion of node are easily implemented in a linked list at any position.

Disadvantages

  1. They use more memory than arrays because of the memory used by their pointers (next and prev).
  2. Random access is not possible in linked list. We have to access nodes sequentially.
  3. It’s more complex than array. If a language supports array bound check automatically, Arrays would serve you better.

Note

We have to use free() in C and delete in C++ to free the space used by deleted node, whereas, in Python and Java free space is collected automatically by garbage collector.