arrayを使用する代わりに、linked listを使用してstackを実装することもできます。 リンクリストはメモリを動的に割り当てます。 しかし、両方のシナリオの時間の複雑さは、すべての操作、すなわちpush、pop、peekで同じです。
スタックのリンクリスト実装では、ノードはメモリ内で非連続的に維持されます。 各ノードには、スタック内の直接の後継ノードへのポインタが含まれています。 メモリヒープに残っている領域がノードを作成するのに十分でない場合、スタックはオーバーフローされると言われます。
スタック内の最上位のノードは、常にそのアドレスフィールドにnullを含みます。 Stackのリンクリスト実装で各操作がどのように実行されるかを説明します。
スタックへのノードの追加(プッシュ操作)
スタックへのノードの追加をプッシュ操作と呼びます。 リンクリスト実装の要素をスタックにプッシュすることは、配列実装のそれとは異なります。 要素をスタックにプッシュするには、次の手順が必要です。
- 最初にノードを作成し、それにメモリを割り当てます。
- リストが空の場合、項目はリストの開始ノードとしてプッシュされます。 これには、ノードのデータ部分への値の割り当てと、ノードのアドレス部分へのnullの割り当てが含まれます。
- リストに既にノードがある場合は、リストの先頭に新しい要素を追加する必要があります（スタックのプロパティに違反しないように）。 この目的のために、開始要素のアドレスを新しいノードのアドレスフィールドに割り当て、新しいノードをリストの開始ノードにします。
- underflow条件のチェック:underflow条件は、既に空のスタックからポップしようとすると発生します。 リストの先頭ポインタがnullを指している場合、スタックは空になります。
- それに応じてヘッドポインタを調整します。stackでは、要素は一方の端からのみポップされるため、ヘッドポインタに格納されている値を削除し、ノードを解放する必要があります。 これで、ヘッドノードの次のノードがヘッドノードになります。
- ヘッドポインタを一時ポインタにコピーします。
- 一時ポインタをリストのすべてのノードに移動し、すべてのノードにアタッチされた値フィールドを出力します。
時間の複雑さ：o(1)
C実装:
スタックからノードを削除する(POP操作)
スタックの先頭からノードを削除することをpop操作と呼びます。 Stackのリンクリスト実装からノードを削除することは、array実装のものとは異なります。 スタックから要素をポップするには、次の手順を実行する必要があります:
: o(n)
Cの実装
ノードの表示(トラバース)
スタックのすべてのノードを表示するには、スタックの形式で編成されたリンクリストのすべてのノードをトラバースする必要があります。 この目的のためには、次の手順を実行する必要があります。
: o(n)