Structures de données expliquées avec des exemples - Liste liée

Tout comme une guirlande est faite de fleurs, une liste chaînée est composée de nœuds. Nous appelons chaque fleur de cette guirlande particulière à être un nœud. Et chacun des nœuds pointe vers le nœud suivant de cette liste ainsi que des données (ici, c'est le type de fleur).

Les types

Liste liée individuellement

Les listes liées individuellement contiennent des nœuds qui ont un datachamp ainsi qu'un nextchamp, qui pointe vers le nœud suivant dans la séquence. Les opérations qui peuvent être effectuées sur des listes liées individuellement sont l'insertion, la suppression et le parcours.

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

Implémentation interne de CPython, les cadres et les variables évaluées sont conservés sur une pile.

Pour cela, nous n'avons besoin d'itérer que vers l'avant pour obtenir la tête, donc une seule liste chaînée est utilisée.

Liste doublement liée

Les listes doublement liées contiennent des nœuds qui ont un datachamp, un nextchamp et un autre champ de lien prevpointant vers le nœud précédent dans la séquence.

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

Le cache du navigateur qui vous permet d'appuyer sur le bouton RETOUR et AVANT. Ici, nous devons maintenir une liste doublement liée, avec URLscomme champ de données, pour permettre l'accès dans les deux sens. Pour aller à l'URL précédente, nous utiliserons le prevchamp et pour aller à la page suivante, nous utiliserons le nextchamp.

Liste liée circulaire

Les listes chaînées circulaires sont une liste chaînée unique dans laquelle le dernier nœud, le nextchamp pointe vers le premier nœud de la séquence.

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

Problème de temps partagé résolu par le système d'exploitation.

Dans un environnement de partage de temps, le système d'exploitation doit maintenir une liste des utilisateurs actuels et doit alternativement permettre à chaque utilisateur d'utiliser une petite partie du temps CPU, un utilisateur à la fois. Le système d'exploitation choisira un utilisateur, lui permettra d'utiliser une petite quantité de temps CPU, puis passera à l'utilisateur suivant.

Pour cette application, il ne devrait y avoir aucun pointeur NULL sauf s'il n'y a absolument personne qui demande du temps CPU, c'est-à-dire que la liste est vide.

Opérations de base

Insertion

Pour ajouter un nouvel élément à la liste.

Insertion au début:

  • Créez un nouveau nœud avec des données données.
  • Pointez le nouveau nœud nextvers l'ancien head.
  • Pointez headsur ce nouveau nœud.

Insertion au milieu / à la fin.

Insertion après le nœud X.

  • Créez un nouveau nœud avec des données données.
  • Le point nouveau nœud est nextà l' ancien X de next.
  • Pointez X nextsur ce nouveau nœud.

Complexité temporelle: O (1)

Effacement

Pour supprimer un élément existant de la liste.

Suppression au début

  • Obtenez le nœud indiqué par headTemp.
  • Pointez headsur Temp next.
  • Mémoire libre utilisée par le nœud Temp.

Suppression au milieu / à la fin.

Suppression après le nœud X.

  • Obtenez le nœud indiqué par XTemp.
  • Pointez X nextsur Temp next.
  • Mémoire libre utilisée par le nœud Temp.

Complexité temporelle: O (1)

Traverser

Pour parcourir la liste.

Traversée

  • Obtenez le nœud pointé par headcomme Current.
  • Vérifiez si Current n'est pas nul et affichez-le.
  • Pointez Current sur Current's nextet passez à l'étape ci-dessus.

Complexité temporelle: O (n) // Ici n est la taille de la liste de liens

la mise en oeuvre

Implémentation C ++ d'une liste chaînée unique

// 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;

Impression des données dans chaque nœud

// 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.

Original text