Tête de nœud dans les listes liées

J'ai des problèmes avec la compréhension de ce qu'est la nature du premier nœud, ou le soi-disant à la tête, dans une liste, la structure de données. Une liste chaînée est constitué de nœuds, et chaque nœud contient des données et un lien vers un autre nœud dans la liste. Mais il est le premier nœud un nœud qui contient des données et un lien vers le deuxième nœud? Ou est-ce seulement contenir un lien (et pas de données) à un nœud? Je pensais que le premier nœud dans une liste liée a la fois les données et un lien vers un autre nœud, mais dans un livre d'introduction, il est expliqué que la tête est un nœud, mais un lien qui vous mène vers le premier nœud. Dans le même temps, la tête est une variable du type du nœud. Pourquoi est-il comme cela? (Je travaille en Java, si ce qui compte). Merci à vous.

OriginalL'auteur user42155 | 2010-12-20

6

Ces derniers sont appelés "dummy" en-tête de nœuds, et ils vous permettent d'écrire du code qui fonctionne pour vides et non vides listes.

Régulièrement, si vous souhaitez insérer un Node à la fin de votre liste, vous avez besoin de deux cas. Si head est null, ce qui indique la liste est vide, vous devez définir head à la nouvelle Node. Si head n'est pas null, alors vous suivez les next pointeurs jusqu'à ce que vous avez la dernière Node, et de définir la next pointeur vers la nouvelle Node.

Toutefois, si vous utilisez un mannequin en-tête, head ne sera jamais nulle. Ce sera un Node avec une valeur null next pointeur, vous pouvez pointer vers votre nouveau Node, juste la façon dont vous le feriez si la liste ne contiennent des nœuds.

OriginalL'auteur ACoolie
2

Un @falmarri répondu, vous pouvez la mettre en œuvre. Tête de nœud est similaire à n'importe quel autre nœud dans une seule liste Liée. C'est juste un noeud de départ avec laquelle nous pouvons parcourir le reste de la liste chaînée. Nous pouvons mettre en œuvre la tête comme un nœud ou comme un pointeur.

OriginalL'auteur svKris
1

Pensez-y comme un Nœud est un objet qui a une variable "data" pour conserver la valeur et une autre variable "suivant" qui pointe vers un autre Nœud de l'objet pour faire un lien.
voir ci-dessous la classe java.
```
public class ListNode {
private int data;
private ListNode next = null;

public ListNode() {
    //TODO Auto-generated constructor stub
}
//constructor for creating a listNode
public ListNode(int data){
    this.data = data;
}
/*below are setters and getters  */
public void setData(int data){
    this.data = data;
}
public int getData(){
    return this.data;
}
public void setNext(ListNode next){
    this.next = next;
}
public ListNode getNext(){
    return this.next;
}
}
```
et ce est la façon dont je voudrais faire un lien.
```
//create 3 list node objects
    ListNode one = new ListNode(1);
    ListNode two = new ListNode(2);
    ListNode three = new ListNode(3);

    one.setNext(two);
    two.setNext(three);
```
Mais note nous avons besoin de connaître le nœud de tête pour toute autre manipulation, comme l'ajout d'un ListNode à la fin, au début ou à un endroit aléatoire dans la Liste.

une Tête de Nœud est dans notre cas où la liste de la chaîne a commencé.

Espère qu'il efface 🙂

Merci
Punith

Quel est le nombre 1 dans ListNode one = new ListNode(1); ou le nombre 2 dans ListNode two = new ListNode(2); dans les parenthèses? Que faut-il faire?
voir le paramètre de constructeur de ListNode(int data). il prend les données et l'attribue aux objets de données de la variable.

OriginalL'auteur Punith Raj
0

Vous pouvez la mettre en œuvre. Un premier nœud qui n'a pas de données et juste un lien serait assez bizarre de mise en œuvre.

Pas nécessairement. Avoir une "sentinelle" zéro nœud simplifie beaucoup d'opérations que vous pouvez effectuer sur une liste liée - par exemple, beaucoup d'opérations ne doivent plus explicitement à la vérification d'une liste vide.
Ok, vous avez raison, mais je suppose que ça dépend du problème que vous avez des problèmes. Je n'ai jamais eu personnellement à l'utilisation d'une liste de liens avec un vide premier nœud.
Que la mise en œuvre est là pour jdk6 linkedList.

OriginalL'auteur Falmarri
0

Un nœud de tête est normalement comme n'importe quel autre nœud, sauf qu'il s'agit logiquement au début de la liste, et pas d'autres nœuds point (sauf si vous avez une liste à double liaison).

Depuis pas d'autres points de nœud, et vous avez aussi besoin d'un moyen facile de trouver le début de la liste, il est courant pour stocker un pointeur séparé à un nœud qui pointe vers le nœud de tête. Ce pointeur n'est pas un nœud lui-même, juste un pointeur vers un.

Selon mon livre, ce pointeur a le même type de données que pour les autres nœuds. Donc, il n'est pas un nœud lui-même, mais du même type que les nœuds, est-ce correct?
Cela dépend de ce que la langue que vous écrivez. Dans quelque chose comme le java, le pointeur vers le premier nœud serait le plus susceptible d'être un nœud. Dans quelque chose comme C ou C++, vous pouvez avoir un réel pointeur.

OriginalL'auteur Jonathan Wood
0

Si c'est en C++, il peut être plus facile pour vous de comprendre, mais un en-tête de nœud est plus juste une référence que vous utilisez pour gagner de l'accès initial à l'ensemble de la liste. Elle fait référence à la première de "compléter" nœud dans la liste qui contient son élément de données dans la liste de l'ensemble de données et une référence vers le nœud suivant. Si c'était le C++, un noeud vraiment être juste un "pointeur" vers une structure de données, qui est juste l'adresse de mémoire pour le compilateur. Si vous ne disposez pas d'un en-tête de nœud qui a signalé à votre liste liée, alors il serait perdu dans la "éther" de ne jamais consulter de nouveau, tout en prenant de la place dans la mémoire.

Depuis Java prend soin de cela pour vous dans les coulisses, vous n'avez pas à vous soucier de pointeurs. Mais, qui pourrait être la raison derrière votre confusion. Depuis, beaucoup de détails sont cachés, sans aucune connaissance préalable, derrière les concepts vous avez juste à accepter les règles de syntaxe, sans en connaître les raisons derrière eux.

Dans le concept, les tableaux sont un type de liste, tout comme les listes liées sont également un type de liste. Les tableaux sont placés dans un ordre séquentiel de la mémoire alors que les listes chaînées sont pas. Un tableau est membre uniquement les références de son élément de données, mais puisque les membres sont placés là où ils sont en mémoire, vous pouvez y accéder par l'ajout d'une valeur d'entier multiplié par la taille de l'élément de données type de données de référence pour l'ensemble de la matrice. Cela diffère de listes liées par le fait que les listes ne sont pas placés dans l'ordre et donc de plus en plus complexe structure de données doit être utilisé pour faire la liste - c'est à dire un "nœud".

Mais, depuis la liste, n'est pas placé dans n'importe quel type de commande dans la mémoire, le compilateur n'a pas à mettre de côté un bloc de données et donc est pourquoi il peut avoir n'importe quelle longueur que vous le souhaitez sans avoir à en créer un nouveau à chaque fois que vous modifier sa longueur. Cela diffère d'un tableau de tableaux de longueurs sont statiques. En outre, un tableau est référencé par son premier membre, qui est (pour un tableau nommé "a") ce serait un "[0]" ou l'équivalent "d'un" si c'était C. Cependant, une liste chaînée ne fonctionne pas comme cela et c'est pourquoi vous avez un "en-tête" ou "dummy" nœud de référence de la chose entière.

Une autre chose à propos de l'en-tête de nœud, c'est que lors de l'exécution de diverses opérations sur une liste liée, vous pouvez également créer un nœud qui est similaire à la structure de votre "tête de nœud" pour les aider dans la réalisation de votre opération sur la liste.

OriginalL'auteur Michael M. Adkins

Vous devez vous connecter pour publier un commentaire.