リンクリストの紹介

11828 ワード
tutorial codenewbie beginners ruby テキストリンク
Flatironからの我々の卒業がより接近するように、私のコホートと私は将来のインタビューの準備でアルゴリズムとデータ構造知識に集中しようとしていました.その理由は、私は、それが特別に尋ねられたインタビュー概念を乗り越える素晴らしいアイデアであると思いました:関連リスト!
概要
リンクリストは、単に文字通りお互いにリンクされているデータのリストです.それらは線形データ構造であり、順序の順序で配列された別々の要素で構成される.
線形と非線形のデータ構造の違いが最初に議論するのは役に立つかもしれません.

線形データ構造
線形データ構造は、データ要素がラインの他の1つの後に、したがって、線形で、そして、シーケンシャルに取り付けられるそれらである.これにより、各要素は前と次の要素に順番にリンクされます.線形データ構造の中の要素についての情報を見つけるには、最初の要素から始めて、各要素を1つずつ行ってください.あなたは、1つの反復で線形データ構造の内部のすべてのデータにアクセスすることができます.
非線形データ構造
他方、非線形データ構造は非シーケンシャルである.そして、それらが含む情報が次々と注文される必要はない.さらに、1つの要素が2つ以上の要素に接続され、1回の反復でデータのすべてを横断できるようになります.典型的には、線形データ構造を実施することは、非線形のものを実施するよりも容易である傾向がある.
リンクリストの種類
この新しい発見された知識で、関連リストに戻りましょう.以下は、単一のリンクリストの例を見ることができます.

単独連結リスト
これは最も基本的な例であり、リンクリストの主要なコンポーネントのすべてを私たちに与えます.リンクされたリスト内の各要素、またはノードには、2つの情報が含まれています.データまたは値を格納し、リスト内の次の項目の配置についての知識.ノードは、次のノードが存在するメモリの場所のこの知識を通して一緒にリンクされる.リンクリストを反復処理する場合は、先頭のノードで最初に開始する必要があります.頭の次のノードの知識を持つことによって、ノードの完全なリストを見ることができます.そして、リストの最後のノードは次のノードに関する情報を含んでいません.

二重連結リスト
また、ノードを構成する3つの部分を持つ2重連結リストもあり、そのうちの2つは前のノードと次のノードの知識ポイントである.これにより、リスト内のデータまたはノードにアクセスすることが容易になります.しかし、彼らは我々の次の考えに私たちをもたらすより多くのスペースを取る.
メモリー・ストレージ

彼らのより人気があって、姉妹配列とともに得るのがより簡単なそれらから彼らを分けるリンクリストの1つの重要な要因は、スペースと時間の使用、または大きいo表記です.
図に示すように、各々の正方形はメモリーのバイトを表示する.そして、アレーは予め定められた長さを有して、それらが占めるメモリーの予め定められた量を有する.すべてのスペースが現在データで満たされていないとしても、配列はメモリのこれらのバイトをまだ保持します.これは、配列がより長くする必要があると判断された場合、それらを嵩かしく、遅く、またはさらに悪くすることができます.それはコピーされなければならなくて、メモリに格納される新しいブロックまたは場所を見つけました.
リンクリストは、しかし、そのノードとして保存することができますメモリを介してマシンを喜ばせるように分離.ダイアグラムでは、リンクリストは、ノードが存在するのに必要なスペースを占有していることがわかります.これは、記憶される他のアイテムのためにメモリのより多くの柔軟性を考慮に入れて、どんな未使用のスペースも浪費しません.
リンクリスト内のすべての要素にアクセスするのにかかる時間は、リストのサイズに直接比例します.リストのサイズがNであるならば、時間複雑さは0(n)です.配列でこれを対照するために、代表的に、配列はそれらのサイズが固定されて、連続的にブロックにおいて、連続的に格納されるように、O(1)時間だけ取る.配列を使用すると、索引付けによって構造体の中央の項目に到達することができますが、可能ではないリンクリストを使用できます.
リンクリストは本当に挿入と削除に関して輝きます.小さいリストまたは最適探索を与えられて、両方とも一定または0(1)時間をとることができます.しかし、リストのサイズに主に依存しているので、挿入や削除が行われる必要がある場所を見つけるために、リスト全体を横断する必要があるので、それらは0(n)であることもできます.
実装
これを念頭に置いて、Rubyでリンクリストを実装した例を見てみることができます.
リンクリストは通常、2つのクラスとして作成されます:ノードクラスとリンクリストクラスです.
class Node
  attr_accessor :value, :next_node

  def initialize(value, next_node)
    @value = value
    @next_node = next_node
  end
end
最初のノードクラスは、値と次の値のポインターであるnextSumノードで初期化されます.新しいノードインスタンスを作成すると、次にNILとして初期化されます.
class LinkedList
  def initialize(value)
    @head = Node.new(value, nil)
  end

  def addition(value)
    current_node = @head
    while current_node.next_node != nil
      current_node = current_node.next_node
    end
      current_node.next_node = Node.new(value, nil)
  end

  def find(value)
    current_node = @head
    puts current_node.value
    return false if !current_node.next_node
    return current_node if current_node.value == value
    while (current_node = current_node.next_node)
      return current_node if current_node.value == value
    end
  end

  def deletion(value)
    current_node = @head
    if current_node.value == value
      @head = current_node.next_node
    else
      while (current_node.next_node != nil) && (current_node.next_node.value != value)
        if (current_node.next_node == nil) || (current_node.next_node.value == value)
          current_node.next_node = current_node.next_node.next_node
        else
          current_node = current_node.next_node
        end
      end
      current_node.next_node = current_node.next_node.next_node
    end
  end

  def print_list
    current_node = @head
    puts current_node.value
    while (current_node = current_node.next_node)
      puts current_node.value
    end
  end

end
私は、コンソールに値を印刷するための方法と同様に、リンクリスト(追加、削除と検索)のために3つの基本的な方法を含みました.
追加
最初に、現在のノードは、頭、またはリストの最初のノードとして設定されます.ノードが残っていないまでリンクリストを通過します.それが最後のノードを見つけるとき、それは前に止まり、新しいものを次と最後の、ノードとして追加します.
見つける
再び、現在のノードはヘッド・ノードにセットされる.そして、最初の2つのリターンはエッジケースである.リストが空でないと仮定して、頭のノードが一致している値でないと仮定して、値が見つかるまで、リストは1つずつ繰り返されます.
削除
値がリンクリストで必ずしも削除されるというわけではないので、これは最も重要な方法です、彼らは単にアンリンクスされて、新しいリストで渡されます.最初のif文は、削除される値がheadノードに含まれている場合のエッジケースです.そうであるならば、私たちは私たちの新しいCurrentSumノードを次の価値であるように設定します.これがそうでないならば、私たちは終わりまでリストを通って横断します、あるいは、値がノードと一致するまで.この場合、CurrentLightノードを次の次のノードに設定し、「削除」されるノードを越えます.
この例では、2つのノードを前方に見ておく必要があります.削除するものを見つけるときには、単純にスキップして、次の次のノードにcurrentCageノードを割り当てます.
版下リスト
最後のメソッドPrintCountリストは、単純に表示するためにコンソールに印刷されたリスト全体を印刷するだけです.
list = LinkedList.new(2)
list.addition(5)
list.addition(7)
list.addition(10)
list.deletion(5)
list.print_list

# 2, 7, 10
持ち帰り
リンクリストは、アイテムの追加と削除に便利です.それらはしばしば配列と正当な理由で比較されます.これらは非常に同様に機能しますが、以下のようにいくつかのかなり明確な利点と欠点があります.
長所
項目を加えて、取るときに、アレーより効果的なより多くの時間
  • の未使用のメモリ
    • 非線形データ構造よりも実装が容易である

  • 短所
    項目
    • のインデックスを見つけるときに、配列より遅い
  • は、次のノード
    • に参照を記憶するためのメモリー割当てを意識しなければならない
    アレイよりも実装するのが困難である

  • あなたがあなたの次のアプリケーションでリンクリストを実装することに決めたならば、あなたが次のインタビューでこの面白いデータ構造について尋ねられるようになるならば、これは役に立つかもしれません.ハッピーコーディング!
    • 囲碁の世界の結晶
    showdocインストールとデータベース基本管理