Nodo principal en listas vinculadas

Question

Tengo problemas para comprender cuál es la naturaleza del primer nodo, o el denominado encabezado, en una estructura de datos de lista vinculada. Una lista vinculada consta de nodos, y cada nodo contiene algunos datos y un enlace a otro nodo en la lista. Pero, ¿el primer nodo es un nodo que contiene datos y un enlace al segundo nodo? ¿O contiene solo un enlace (y ningún dato) a un nodo? Pensé que el primer nodo en una lista vinculada tiene datos y un enlace a otro nodo, pero en un libro introductorio se explica que el encabezado es un nodo pero un enlace que lo lleva al primer nodo. Al mismo tiempo, head es una variable del tipo del nodo. ¿Por qué es como este? (Estoy trabajando en Java, si eso importa). Gracias.

Answer 1

Puede implementarlo de cualquier manera. Sin embargo, un primer nodo que no tenga datos y solo un enlace sería una implementación bastante extraña.

Answer 2

Un nodo principal normalmente es como cualquier otro nodo, excepto que viene lógicamente al principio de la lista, y ningún otro nodo lo señala (a menos que tenga una lista doblemente vinculada).

Como ningún otro nodo lo señala, y también necesita una manera fácil de encontrar el comienzo de la lista, es común almacenar un puntero separado a un nodo que apunta al nodo principal. Este puntero no es un nodo en sí mismo, solo un puntero a uno.

Answer 3

Estos se denominan nodos de encabezado "ficticios" y le permiten escribir código general que funciona para listas vacías y no vacías.

Regularmente, si desea insertar un Node al final de su lista, necesita dos casos. Si head es nulo, lo que indica que la lista está vacía, entonces establecería head en el nuevo Node. Si head no es nulo, siga los punteros next hasta que tenga el último Node y configure el puntero next en el nuevo Node.

Sin embargo, si utiliza un encabezado ficticio, head nunca será nulo. Será un Node con un puntero nulo next, que puede señalar a su nuevo Node, como lo haría si la lista no tuviera nodos.

Answer 4

Si esto fue en C++, podría ser más fácil para usted entenderlo, pero un nodo de encabezado es más que una referencia que utiliza para obtener el acceso inicial a la lista completa. Hace referencia al primer nodo "completo" en la lista que contiene su elemento de datos dentro del conjunto de datos de la lista y una referencia al siguiente nodo. Si esto fuera C++, un nodo sería realmente solo un "puntero" a una estructura de datos, que es solo la dirección de memoria para el compilador. Si no tiene un nodo de encabezado que apunte a su lista enlazada, entonces se perderá en el "éter" para no volver a acceder nunca más, mientras ocupa espacio en la memoria.

Dado que Java se encarga de esto detrás de escena, no tiene que preocuparse por los punteros. Pero, esa podría ser la razón detrás de tu confusión. Dado que se ocultan tantos detalles, sin ningún conocimiento previo detrás de los conceptos, usted debería aceptar las reglas de sintaxis sin conocer las razones detrás de ellos.

En concepto, las matrices son un tipo de lista, al igual que las listas vinculadas también son un tipo de lista. Las matrices se colocan en orden secuencial en la memoria, mientras que las listas vinculadas no lo son. Un miembro de la matriz solo hace referencia a su elemento de datos, pero como los miembros se ubican en la memoria, puede acceder a ellos agregando un valor entero multiplicado por el tamaño del tipo de datos de ese elemento de datos a la referencia de toda la matriz. Esto difiere de las listas enlazadas por el hecho de que las listas vinculadas no se colocan en orden secuencial y, por lo tanto, se debe usar una estructura de datos más compleja para componer la lista, es decir, un "nodo".

Pero, dado que la lista vinculada no se coloca en ningún tipo de orden en la memoria, el compilador no tiene que reservar una porción de datos para ella y es por eso que puede tener cualquier longitud que desee. sin tener que volver a crear uno nuevo cada vez que cambie su longitud. Esto difiere de una matriz ya que las longitudes de las matrices son estáticas. Además, su primer miembro hace referencia a una matriz, es decir (para una matriz llamada "a"), esta sería "a [0]" o su equivalente "a" si esta fuera C. Sin embargo, una lista vinculada no lo hace trabaje así y es por eso que tiene un nodo "encabezado" o "ficticio" para hacer referencia a todo el asunto.

Otra cosa sobre el nodo del encabezado es que al realizar varias operaciones en una lista enlazada, también puede crear un nodo que sea similar en estructura a su "nodo principal" para ayudarlo a realizar su operación en la lista.

Answer 5

Piense en ello como un nodo es un objeto que tiene una variable de "datos" para mantener el valor y otra variable "siguiente" que apunta a otro objeto nodo para hacer un enlace. vea la siguiente clase de 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; 
} 
} 

y así es como lo vincularía.

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

Pero tenga en cuenta que necesitamos saber el nodo principal para cualquier otra manipulación como la adición de un NodoLista al final, a partir de o en un lugar al azar en la lista.

a Head Node es uno en nuestro caso desde donde se inició la cadena de listas.

espero que borra :)

Gracias Punith

Answer 6

contestó Un @falmarri, se puede implementar de cualquier manera. El nodo principal es similar a cualquier otro nodo en una lista Singly Linked. Es solo un nodo inicial con el que podemos atravesar el resto de la lista enlazada. Podemos implementar la cabecera como un nodo o como un puntero.