Pour une liste singulièrement liée, faut-il toujours ajouter un nouveau nœud comme premier élément ?

Question

Habituellement, dans une liste singulièrement liée, ajoute-t-on toujours un nouvel élément en tant que head.next, c'est-à-dire en tant que premier élément ? Ou bien va-t-on jusqu'à la fin de la liste et l'ajoute-t-on à cet endroit ?

Answer 1

Conformément à cette conférence de l'université de Stanford (après 13:00 min), ajoute marche à la fin de la liste et y ajoute le nouveau noeud. Voici une capture d'écran du code (C++)

Dans le notes de cours de l'UC Berkley (Java) ils l'ajoutent comme premier élément, mais ensuite ils l'appellent explicitement comme insertFront()

public class SList {
  private SListNode head;             // First node in list.
  private int size;                   // Number of items in list.

  public SList() {                    // Here's how to represent an empty list.
    head = null;
    size = 0;
  }

  public void insertFront(Object item) {
    head = new SListNode(item, head);
    size++;
  }
}

Dans le Classe LinkedList dans le cadre de java (il s'agit d'une liste doublement liée), ajouter signifie simplement ajouter à la fin de la liste. Ainsi, si vous ajoutez 1, puis 2 et enfin 3, 3 sera le dernier élément de la liste.

En bref : À moins d'être explicitement appelé addFront (ou quelque chose comme ça), add sur une LinkedList, signifie ajouter comme dernier élément.

Answer 2

Les deux façons sont possibles, mais l'insertion à l'avant est généralement préférée pour des raisons de performance.

L'insertion d'un nouvel élément comme tête est très rapide, O(1), car il suffit de créer un élément et un pointeur vers l'ancienne tête.

Insérer à la fin signifie parcourir la liste pour trouver le dernier élément et mettre à jour son pointeur vers le nouvel élément. Ceci est O(n).

Vous pouvez échanger le temps contre le stockage en gardant également la trace de la queue de votre liste et en effectuant O(1) insertions à la fin. Mais alors vous avez quelque chose d'un peu plus compliqué qu'une liste singulièrement liée.

Qualification Habituellement

Quand je dis généralement Je fais référence aux listes singulièrement liées faites à la main, spécialement écrites en C, peut-être pour un dispositif embarqué où l'espace est limité et où l'espace supplémentaire pour stocker la queue est juste trop important.

Pour un langage général comme Java, par exemple, l'implémentation de LinkedList stocke la queue, de sorte que les deux opérations sont O(1). Il est intéressant de noter que, dans le cas de Java, l'interface abstraite de List ne définit qu'une opération d'ajout à la liste.

Une implémentation (en pseudo C)

Disons que j'ai une liste telle que

struct List {
    int data;
    List *next;
};

Si je veux insérer au début, je vais écrire

List* insert(List *original_list, int data) {
    List* head = allocate new List(data, original_list);
    return head;
}

Si je veux ajouter, je vais écrire

void append(List *original_list, int data) {
    List* new_tail = allocate new List(data, null);
    ptr = original_list
    while(ptr->next != null)
        ptr++
    ptr->next = new_tail;
}

Answer 3

Comme l'a dit @munk, les deux voies sont possibles. Cependant, la complexité temporelle de l'insertion peut varier en fonction de la structure que vous utilisez. Permettez-moi d'être plus clair.

Utilisons le langage C pour que ce soit plus simple. Une façon possible d'implémenter une liste chaînée unique est la suivante :

typedef struct node {
    int foo;
    node_t* next;
} node_t;

typedef struct list {
    node_t* head;
} list_t;

De cette façon, vous créez d'abord une structure node pour stocker les informations que vous voulez stocker, puis déclarez une deuxième structure list qui contient simplement un pointeur vers le premier nœud de la liste, c'est-à-dire l'élément head . Avec cette mise en œuvre :

• L'insertion au début prend O(1) temps (il suffit de changer le head et a fait quelques ajustements avec next .
• L'insertion à la fin prend O(n) temps parce que vous devez parcourir la liste entière.

Une deuxième façon d'implémenter une liste liée unique est la suivante :

typedef struct node {
    int foo;
    node_t* next;
} node_t;

typedef struct list {
    node_t* head;
    node_t* tail;
} list_t;

Vous maintenez un pointeur sur le dernier élément de la liste, ce qui fait que l'insertion à la fin de la liste prend O(1) temps, aussi. Cependant, ce type de mise en œuvre prend plus de place que l'autre.