Węzeł główny na połączonych listach

Question

Mam problemy ze zrozumieniem, jaka jest natura pierwszego węzła lub tzw. Nagłówka w strukturze danych listy połączonych. Połączona lista składa się z węzłów, a każdy węzeł zawiera pewne dane i łącze do innego węzła na liście. Ale czy pierwszy węzeł jest węzłem, który zawiera dane i łącze do drugiego węzła? Czy może zawierać tylko łącze (i brak danych) do węzła? Myślałem, że pierwszy węzeł na połączonej liście ma zarówno dane, jak i łącze do innego węzła, ale w jednej książce wprowadzającej wyjaśniono, że głowa jest węzłem, ale linkiem, który prowadzi do pierwszego węzła. W tym samym czasie głowa jest zmienną typu węzła. Dlaczego tak jest? (Pracuję w Javie, jeśli to ma znaczenie). Dzięki Ci.

Answer 1

Można to zrealizować w dowolny sposób. Pierwszy węzeł, który nie ma danych i tylko link, byłby dość dziwaczną implementacją.

Answer 2

Węzeł główny jest zwykle jak każdy inny węzeł, z wyjątkiem tego, że logicznie pojawia się na początku listy, a żadne inne węzły nie wskazują na to (chyba że masz listę podwójnie połączoną).

Ponieważ żaden inny węzeł nie wskazuje na niego, a ponadto potrzebny jest łatwy sposób na znalezienie początku listy, zwykle jest przechowywany osobny wskaźnik do węzła wskazującego węzeł główny. Ten wskaźnik nie jest węzłem sam w sobie, tylko wskaźnikiem do jednego.

Answer 3

Są to tak zwane węzły nagłówkowe, które umożliwiają napisanie ogólnego kodu działającego na puste i niepuste listy.

Regularnie, jeśli chcesz wstawić Node na końcu listy, potrzebujesz dwóch przypadków. Jeśli head ma wartość NULL, oznacza to, że lista jest pusta, wówczas ustawisz head na nowy Node. Jeśli head nie ma wartości null, postępuj zgodnie ze wskazówkami next, dopóki nie masz ostatniego Node i ustaw wskaźnik next na nowy.

Jeśli jednak używasz dummy header, head nigdy nie będzie mieć wartości NULL. Będzie to Node ze wskaźnikiem zerowym next, który można wskazać na nowy Node, tak jak byś zrobił, gdyby lista zawierała węzły.

Answer 4

Jeśli był w C++, może być łatwiejszy do zrozumienia, ale węzeł nagłówka jest po prostu referencją, której używasz do uzyskania wstępnego dostępu do całej listy. Odwołuje się do pierwszego "kompletnego" węzła na liście, który zawiera jego pozycję danych w zestawie danych listy i odniesienie do następnego węzła. Jeśli był to C++, węzeł byłby po prostu "wskaźnikiem" do struktury danych, która jest po prostu adresem pamięci kompilatora. Jeśli nie masz węzła nagłówka, który wskazywałby na twoją listę połączoną, to zostałby utracony w "eterze", do którego nigdy nie można uzyskać dostępu - wciąż zajmując miejsce w pamięci.

Ponieważ Java zajmuje się tym za kulisami, nie musisz się martwić o wskaźniki. Ale to może być przyczyną twojego zamieszania. Ponieważ wiele szczegółów jest ukrytych, bez uprzedniej znajomości tych pojęć, musielibyśmy zaakceptować reguły składni, nie znając ich przyczyn.

W koncepcji tablice są typem listy, podobnie jak listy połączone są także typem listy. Tablice są umieszczane w kolejności w pamięci, natomiast listy połączone nie. Element tablicy odwołuje się tylko do elementu danych, ale ponieważ elementy są umieszczone w pamięci, można uzyskać do nich dostęp, dodając liczbę całkowitą pomnożoną przez rozmiar tego typu danych elementu danych do odwołania dla całej tablicy. Różni się to od list powiązanych przez fakt, że listy połączone nie są umieszczane w porządku sekwencyjnym, a zatem do utworzenia listy należy użyć bardziej złożonej struktury danych, tj. "Węzła".

Ale ponieważ lista połączona nie jest umieszczana w jakiejkolwiek kolejności w pamięci, kompilator nie musi odkładać na nią kawałka danych, dlatego może mieć dowolną długość bez konieczności ponownego tworzenia nowego za każdym razem, gdy zmieniasz jego długość. Różni się to od tablicy, ponieważ długości tablic są statyczne. Dodatkowo do tablicy odwołuje się jej pierwszy element, tj. (Dla tablicy o nazwie "a") to byłoby to "a [0]" lub odpowiednik "a", gdyby było to C. Jednak lista połączona nie działaj tak i dlatego masz węzeł "nagłówka" lub "manekina", aby odwoływać się do całej rzeczy.

Inną kwestią dotyczącą węzła nagłówka jest to, że podczas wykonywania różnych operacji na liście połączonej można również utworzyć węzeł o strukturze podobnej do "węzła głównego", aby pomóc w wykonywaniu operacji na liście.

Answer 5

Pomyśl o tym, jak węzeł jest obiektem, który ma zmienną "dane" do przechowywania wartości i inną zmienną "dalej", która wskazuje na inny obiekt węzła, aby utworzyć łącze. zobacz poniżej klasa 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; 
} 
} 

i tak powinienem go połączyć.

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

Ale pamiętać musimy znać węzeł głowy dla dalszych manipulacji jak dodanie ListNode w końcu zaczynają lub w losowej kolejności na liście.

Węzeł głowicy to nasz pierwszy przypadek, z którego zaczęła się lista.

Nadzieję, że czyści :)

Dzięki Punith

Answer 6

@falmarri odpowiedział, można wdrożyć go w obu kierunkach. Węzeł główny jest podobny do dowolnego innego węzła na liście Singly Linked. To tylko początkowy węzeł, z którym możemy przejść przez resztę połączonej listy. Możemy zaimplementować głowę jako węzeł lub wskaźnik.