9

リンクされたリストのデータ構造の最初のノード、いわゆるヘッドの性質を理解するのに問題があります。リンクされたリストはノードで構成され、各ノードにはいくつかのデータとリスト内の別のノードへのリンクが含まれています。しかし、最初のノードは、データと 2 番目のノードへのリンクを含むノードですか? それとも、ノードへのリンクのみ (およびデータなし) が含まれていますか? リンクリストの最初のノードにはデータと別のノードへのリンクの両方があると思っていましたが、ある入門書では、ヘッドはノードですが、最初のノードに移動するためのリンクであると説明されています。同時に head はノードの型の変数です。なぜこのようになっているのですか？（問題があれば、私はJavaで作業しています）。ありがとうございます。

4

7 に答える 7

8

これらは「ダミー」ヘッダー ノードと呼ばれ、空のリストと空でないリストで機能する一般的なコードを記述できます。

通常、リストの最後にa を挿入する場合はNode、2 つのケースが必要です。headリストが空であることを示す null の場合 はhead、 new に設定しますNode。が null でない場合は、最後の が得られるまでポインタheadをたどり、ポインタを新しい に設定します。nextNodenextNode

ただし、ダミー ヘッダーを使用する場合は、headnull になることはありません。リストにノードが含まれていた場合と同じように、 new を指すことができるNodenull ポインターを持つ になります。nextNode

于 2010-12-20T01:34:11.370 に答える
2

@falmarriが答えました。どちらの方法でも実装できます。ヘッド ノードは、単一リンク リスト内の他のノードと同様です。これは、リンクされたリストの残りをトラバースできる開始ノードにすぎません。ヘッドをノードまたはポインターとして実装できます。

于 2013-09-15T08:25:24.890 に答える
1

Node は、値を保持する変数「data」と、リンクを作成する別の Node オブジェクトを指す別の変数「next」を持つオブジェクトであると考えてください。以下の 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;
}
}

これが私がそれをリンクする方法です。

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

ただし、リストの最後、最初、またはランダムな場所に ListNode を追加するなどの操作を行うには、ヘッド ノードを知る必要があることに注意してください。

ヘッド ノードは、この場合、リスト チェーンが開始された場所の 1 つです。

それがクリアされることを願っています:)

ありがとうございます

于 2012-12-11T18:52:25.330 に答える
0

これが C++ の場合、理解しやすいかもしれませんが、ヘッダー ノードは、リスト全体への最初のアクセスを取得するために使用する単なる参照です。これは、リストのデータ セット内のデータ項目と次のノードへの参照を含む、リスト内の最初の「完全な」ノードを参照します。これが C++ の場合、ノードは実際にはデータ構造への単なる「ポインタ」であり、コンパイラのメモリ アドレスにすぎません。リンクされたリストを指すヘッダーノードがなければ、「エーテル」で失われ、二度とアクセスできなくなりますが、メモリ内のスペースを占有します。

Java がバックグラウンドでこれを処理するため、ポインターについて実際に心配する必要はありません。しかし、それがあなたの混乱の背後にある理由かもしれません。非常に多くの詳細が隠されているため、概念の背後にある事前知識がなければ、その背後にある理由を知らずに構文規則を受け入れる必要があります.

概念上、配列はリストの一種であり、連結リストもリストの一種です。配列はメモリ内に順番に配置されますが、リンクされたリストはそうではありません。配列のメンバーはそのデータ項目のみを参照しますが、メンバーはメモリ内の場所に配置されるため、そのデータ項目のデータ型のサイズを掛けた整数値を配列全体の参照に追加するだけでアクセスできます。これは、連結リストが連続した順序で配置されていないため、より複雑なデータ構造を使用してリストを作成する必要があるという点で、連結リストとは異なります。つまり、「ノード」です。

ただし、リンクされたリストはメモリ内に任意の順序で配置されないため、コンパイラはデータのチャンクを確保する必要がないため、再作成することなく必要な長さにすることができます。長さを変えるたびに新しいもの。配列の長さは静的であるため、これは配列とは異なります。さらに、配列はその最初のメンバーによって参照されます。つまり、("a" という名前の配列の場合) これは "a[0]" またはこれが C の場合は同等の "a" になります。ただし、リンクされたリストはそうではありません。このように動作し、全体を参照する「ヘッダー」または「ダミー」ノードがあるのはそのためです。

ヘッダー ノードに関するもう 1 つの点は、リンク リストでさまざまな操作を実行するときに、「ヘッド ノード」と構造が似ているノードを作成して、リストで操作を実行するのに役立つことです。

于 2010-12-20T02:18:03.307 に答える
0

どちらの方法でも実装できます。ただし、データがなくリンクだけの最初のノードは、かなり奇妙な実装になります。

于 2010-12-20T01:20:47.243 に答える
0

ヘッド ノードは通常、論理的にリストの先頭にあり、他のノードがそれを指していないことを除いて、他のノードと同じです (二重リンク リストがない場合)。

他のノードがそれを指していないため、またリストの先頭を見つける簡単な方法も必要であるため、ヘッド ノードを指すノードへの別のポインターを格納するのが一般的です。このポインターはノード自体ではなく、ノードへの単なるポインターです。

于 2010-12-20T01:23:46.453 に答える