[Abot資料構造]2Linked List

0、配列の欠点。

前の授業で、私たちは配列を勉強しました.
しかし、レイアウトの欠点は2つあります.
1.配列のサイズは変更できません.
2.アレイ内の要素を追加または削除するには、これらの要素を移動するのに時間がかかります.
そこで,Linked Listと呼ばれる資料構造を紹介する.

1.リンクリストとは？

リンクリストは、線形構造で形成されたノードの集合です.
各ノードは、データを担当する部分と、次のノードアドレスを参照する部分に分けられます.
「単純リンクリスト」(Single Linked List)のフォーマットは次のとおりです.

上図では、最初のノードがHead、Null(最後のノード)を指すノードをTailと呼ぶ.
Sigely Linked ListのTailを検索する場合は、Headから次のノードを検索するプロセスを繰り返してTailを検索することができます.上記の方法はLink shoppingまたはPointer Hoppingと呼ばれます.

2.リンクリストにノードを追加する方法

Case 1. Headに新しいノードを追加(擬似コードとして作成)

 Algorithm addFirst(e){
 	newNode = Node(e)
    newNode.next = head
    head = newNode
    size = size+1
    }

の新しいノードをnewNodeとして作成します.

newNodeの次のノードをheadに設定します.

headをnewNodeに設定します.

リンクリストのサイズを1に増やします.

Case 2. 新しいノードをTailに追加(擬似コードとして作成)

Algorithm addLast(e){
	newNode = node(e)
    tail.next = newNode
    tail = newNode
    size = size+1

新しいノードをnewNodeと呼びます.

tailの次の指向ノードはnewNodeである.

tailはNewnodeと呼ばれています.

リンクリストのサイズを1に増やします.

3.リンクリストのメリットとデメリット

長所

大きさは可変で、資料をいくら置いてもいいです.

短所

の資料がある部分と、次のノードアドレスを指す部分は、各ノードのサイズが配列時のサイズより大きくなります.そのため、メモリが限られている場合は実現しにくい.

の資料を検索する過程で、配列内の各要素にインデックスがあるため、簡単に見つけることができますが、リンクリストのソートにはHeadから検索する必要があるため、より長い時間がかかる可能性があります.

4.リンクリストのタイプ

Circular Linked List

Circular Linked Listとは、Sigely Linked ListおよびTailの次のノードを指すアドレスがHeadを指すLinked Listである.

Double linked List

Double Linked Listとは、データを含む部分、次のノードアドレスを含む部分、前のノードアドレスを含む部分からなるLinked Listをいう.
上図では、Prevは前のノードのアドレスを示し、Nextは次のノードのアドレスを示す.