C++：リンクされたリスト表現

Question

方法私は基本的にノードクラス（より好ましく構造体）を作成し、実際のLinkedListのクラスを作成する方法リンクリストを表現するために知って。しかし、昨日、私はのロジックを探していました。これは、単一のリンクリストの操作を逆転させ、私が遭遇したソリューションのほぼ90％が関数を含んでいたため、戻り値の型はノード*でした。したがって、あなたが行った操作が何であってもリストを逆転させたいのであれば、それはlinkedListのタイプではないでしょうか？私はそれを間違った方法でやっているのですか？

リンクリストの実装Iは常に実行されます。

#include <iostream> 
using namespace std; 

struct Node 
{ 
    int data; 
    Node *next; 
}; 

class linkedList 
{ 
public: 
    Node* firstPtr; 
    Node* lastPtr; 

    linkedList() 
    { 
     firstPtr=lastPtr=NULL; 
    } 
    void insert(int value) 
    { 
     Node* newNode=new Node; 
     newNode->data=value; 
     if(firstPtr==NULL) 
      firstPtr=lastPtr=newNode; 
     else { 
      newNode->next=firstPtr; 
      firstPtr=newNode; 
     } 
    } 
    void print() 
    { 
     Node *temp=firstPtr; 
     while(temp!=NULL) 
     { 
      cout<<temp->data<<" "; 
      temp=temp->next; 
     } 
    } 
}; 

Answer 1

アプローチは間違っていませんが、あなたのlinkedListクラスに重点を置いている可能性があります。

実際にそのクラスには何が含まれていますか？最初のノードへのポインタと最後のノードへのポインタ（これは、最初のノードのみを知ることによって最後のノードを見つけることができるので、冗長な情報です）。したがって、基本的にlinkedListは追加情報のないヘルパークラスに過ぎません。

linkedListのメンバー関数は、Nodeの中で簡単に移動できます。または、Nodeをパラメーターとするフリー関数にすることができます。

Answer 2

まあ、リンクされたリストは何ですか、最初のノードへのポインタですか？リストは、最初のノードに到達することができれば完全にアクセス可能であり、そのために必要なものは、最初のノードへのポインタです。

extraリストに関する制御情報（長さなど）を保存しない限り、リスト自体に別のデータタイプは必要ありません。

O（n）ではなくO（1）にアイテムを追加できるように、効率的にリストの最後のノードへのポインタを格納する実装もあります。しかし、一覧の余分な機能であり、一般的な一覧ののの要件ではありません。

Answer 3

これらの関数は、リンクされたリストを逆順にした後にポインタをリストの最初のノードに戻すため、Node *型を戻している可能性があります。