リンクリスト内のヘッドノードは情報を持っているか、リンクリストの最初のノードだけを指していますか?
ヘッドノードをリンクリストの開始ノードとして定義できますか?
ヘッドノードは最初のノードのみを指していますか? リンクされたリストはノードで構成され、各ノードにはデータと、リスト内の別のノードへのリンクが含まれています。しかし、最初のノードは、データと2番目のノードへのリンクを含むノードですか?あるいは、それはノードへのリンク(およびデータなし)だけを含んでいますか?私は、リンクされたリストの最初のノードにデータと別のノードへのリンクがあると考えましたが、1つの入門書では、頭はノードですが、最初のノードに移動するリンクです。同時に、headはノードの型の変数です。なぜそれはこのようなものですか?リンク・リストの先頭ノードと開始ノードの違いは何ですか?
答えて
従来、ヘッドノードはリンクされたリストの最初のノードですが、「タイプ」の観点からは他のどのノードとも変わりません。それには、データだけでなく、次のノード(リンクされたリストの第2ノードが存在する場合)へのポインタも含まれます。
この回答は必ずしも真実ではありません。リストを実装する方法はたくさんありますが、この例は1つだけです。 –
@Carl - 私はこれが唯一の方法であると主張しませんでした。私は単にこれが大会だと言った。 – Sid
この実装がコンベンションであると述べるには、どのような基準がありますか? –
実装によって異なります。 head
変数は、通常、この1ノードリストのようなリストの最初のノードを指し示すノードポインタある:
+--------+
head -> | node 1 | -> NULL
+--------+
しかし、私が見た実装場所(二重に「空」リンクされた)リストは2つのノードで構成されているため、挿入および削除コードは、先頭または末尾の前に挿入しようとするエッジの場合や頭/尾の削除を心配する必要はありません。
挿入する位置(および削除を許可するすべてのノード)にprev
ノードとnext
ノードがあるため、コードは簡略化されています。
+-------+ +------+ +-------+
head -> | dummy | -> | node | -> | dummy | -> NULL
NULL <- | node | <- | 1 | <- | node | <- tail
+-------+ +------+ +-------+
ではなく頭や尾をチェックするたくさんの、挿入および削除は、次のとおりです。
def insertBefore (node, newnode):
newnode.next = node
newnode.prev = node.prev
node.prev.next = newnode
node.prev = newnode
def deleteNode (node):
node.prev.next = node.next
node.next.prev = node.prev
free node
それ少し複雑なリストトラバーサルあなたはcurr = head.next
ではなくcurr = head
で開始し、いつ終了しなければならなかったので、 curr == NULL
ではなくcurr == last
であるが、使用されていない2つのノードを犠牲にして有効なトレードオフと考える人もいる。
あなたはそれをリストオブジェクト
- 店のポインタが空のデータメンバー
- と「頭」ノードは、特別な「頭を持っている、少なくとも3つの異なる方法を行うことができますデータメンバのないノード
これらのそれぞれは、いくつかの操作を優先するか、使用される領域を最適化するトレードオフを持っています。
他のノードと同じタイプのヘッドオブジェクトを持つと、リンク操作が簡単になります。データペイロードのないヘッドノードを有することにより、メモリが節約される。リストオブジェクト内にポインタを格納すると、空のリストの動的割り当てが節約される可能性がありますが、swap
を実装するのが難しくなります。
すべての用途に最適です。
- 1. リンク先の先頭に新しいノードを挿入
- 2. リストの先頭にノードを挿入する
- 3. ノードとモジュールの違いは?
- 4. NodeJS Webアプリケーションファイルアップロードの開始オフファイルの先頭
- 5. ノード内からエッジを開始する
- 6. Playの実行と開始の違いは何ですか?
- 7. drupalの「ノード」とは何ですか?
- 8. Pythonでリンクされたリスト(ノード)
- 9. リンクリストの先頭にノードを挿入する
- 10. ノードjs内のstat fstatとlstat関数の違いは何ですか
- 11. リンクされたリスト - 現在のノードの前にノードを挿入する
- 12. xamDataTreeはコード内のノードの編集を開始します
- 13. 再開はノード
- 14. ノードjsとエクスプレスjsの違い
- 15. リンクされたリストの先頭にノードを挿入する機能が2回失敗したのはなぜですか?
- 16. Neo4jのノードのIDのリストと共にノードのリストを取得する
- 17. リストと何か([_])と何か(_)の違い
- 18. イベントテーブルのFacebook開始時刻とFBイベントページのFacebookの違いは何ですか?
- 19. 他のノードを追加するのではなく、ノードを変更するリンクされたリスト
- 20. リンクされたリストからのノードの削除
- 21. Silverlightアプリケーションでデバッグ開始とデバッグなしの違いは何ですか?
- 22. C++ - 完全なときに頭部からノードをポップする静的リスト
- 23. ノード、エクスプレス、ブートストラップで始める
- 24. Androidマージン開始/終了と右/左の違いは何ですか?
- 25. ノードの印刷親ノードが親ノードと子ノードを返すのはなぜですか?
- 26. C:リンクされたリストの2つのノードを交換する
- 27. ノードのデータベースを使い始める
- 28. @ + ID /アンドロイドの違いは何ですか:リストと@ + ID /リスト
- 29. Web開発以外のノードですか?
- 30. リンクされたリストaddノードは単なるノードではなくすべてのノードの値を変更します
リンクされたリストの実装に完全に依存します。 –