[アルゴリズム]とArrayリンク-list

Array

# 처음 상태
rooms = ["윤아", "수영", "티파니", "효연", "유리", "태연", "써니", "**서현**"]

# 1번 이동 -> 써니와 서현 변경
rooms = ["윤아", "수영", "티파니", "효연", "유리", "태연", "**서현**", "써니" ]

# 2번 이동 -> 태연과 서현 변경
rooms = ["윤아", "수영", "티파니", "효연", "유리", "**서현"**, "태연", "써니" ]

# 3번 이동 -> 유리와 서현 변경
rooms = ["윤아", "수영", "티파니", "효연", "**서현**", "유리", "태연", "써니" ]

# 4번 이동 -> 효연과 서현 변경
rooms = ["윤아", "수영", "티파니", "**서현**", "효연", "유리", "태연", "써니" ]

# 5번 이동 -> 티파니와 서현 변경! 후! 드디어 도착!
rooms = ["윤아", "수영", "**서현**", "티파니", "효연", "유리", "태연", "써니" ]

アレイの所与のサイズのデータ上の空間->決定されると、

は変更できません.

アレイは、各要素->ルーム[0]にすぐにアクセスできます.
📌 配列のインデックス順序はゼロから始まります
📌 インスタントアクセス可能->一定時間でアクセス可能:

はO(1)でアクセス可能であることを示す

配列の要素を挿入/削除するには、次の手順に従います.すべての要素を移動する必要があります

の時間的複雑度はO(N)であり,最悪の場合にはN個のアレイを移動しなければならないからである.

配列の新しい要素を追加するには、次の手順に従います.

は、新しいスペースを割り当てる必要があるため、非常に非効率です.

LinkedList

train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

リストは、スペース->不確定なサイズのデータに接続するだけで自由に拡張できます.

リストは、特定の要素にどのようにアクセスしますか?接続リングに沿ってナビゲートする必要があります
最悪の場合、すべての貨物室をナビゲーションする必要があるため、O(N)の時間的複雑さを有する
🚩 接続リング=ポインタ、各貨物室=ノード

要素を中央に挿入/削除するには、

をリストします.前後のポインタを変更するだけで済みます
したがって、

は、要素O(1)の挿入/削除の時間的複雑さにおいて解決することができる.
📢 Array vs LinkedList
項目ArrayLinked-List特定要素O(1)O(N)の中間挿入/削除O(1)追加データを問い合わせる場合、すべてのスペースが満たされている場合は、新しいメモリスペースを割り当てる.すべてのスペースが満たされているが、最後のノードのみが動的に追加されている場合は、整理データに頻繁にアクセスし、Arrayを使用する!頻繁に挿入および削除する場合は、Liked-listを使用します.