リンクリストは、どのプログラミング言語でも最もよく使われるデータ構造の1つです。
この記事では、リンクリストについて詳しく学びます。
リンクリストの種類、リンクリストのトラバース方法、リンクリストの要素の挿入と削除、リンクリストのソート方法、リンクリストの逆引き方法など、リンクリストの様々なテクニックについて見ていきます。
この記事を読んだ後、あなたはすべてのリンクリストの面接の質問を解くことができるはずです。
リンクリストとは？
リンクリストとは何かを学ぶ前に、まず、配列がどのようにデータを格納するかを簡単に復習しておきましょう。
配列では、データは連続したメモリ位置に格納されます。
例えば、配列の最初の項目がメモリのインデックス10に格納され、サイズが15バイトの場合、2番目の項目はインデックス10+15+1=26番目のインデックスに格納されることになります。
したがって、配列をたどるのは簡単なことです。
配列の3番目の項目を見つけるには、最初の項目の開始インデックスに、最初の項目のサイズと、2番目の項目のサイズに1を足したものを使用すればよいのです。
リンクリストのデータ保存方法
一方、リンクリストは違います。
リンクリストは、連続したメモリ位置にデータを格納しません。
メモリ上の各項目に対して、リンクリストはその項目の値と次の項目への参照またはポインタを格納します。
リンクリストの項目と次の項目への参照の一対がノードを構成する。
例えば、34|10で構成されるノードは、ノードの値が30であり、次の項目がメモリ位置 “10 “に格納されていることを意味する。
リンクリストを走査するには、最初のノードのメモリ位置または参照を知っていればよく、残りのノードは各ノードの次の要素への参照を使用して順次走査することができる。
最初のノードへの参照は、スタートノードとも呼ばれる。
リンクリストと配列の比較。
- リンクリストは動的なデータ構造であり、リンクリストのために確保されたメモリは、実行時に増加または減少することができることを意味します。リンクリストのデータ構造には、事前にメモリが割り当てられることはありません。リンクリストに新しい項目を追加する必要がある場合、新しいノードのためのメモリが実行時に作成される。一方、配列の場合は、あらかじめ特定の項目数分のメモリーを確保する必要がある。配列のインデックスをすべて埋めるだけのアイテムがない場合、メモリ領域が無駄になります。
- 配列は連続したメモリ位置を必要とするため、多数の項目のメモリ位置を更新する必要があり、項目の削除や挿入が非常に困難です。一方、リンクリストの項目は連続したメモリ位置に格納されないため、リンクリストの更新が容易に行える。
- リンクリストは、その柔軟性から、スタック、キュー、リストなどのデータ構造の実装に適しています。
しかし、リンクリストにも欠点があります。
- リンクリストの各項目は、次の項目への参照を格納しなければならないので、余分なメモリが必要になります。
- 各リンクリストの項目には次の項目への参照を格納する必要があるため、メモリが余分に必要になる。ビッグ・オー的に言えば、最悪の場合のアクセス時間はO(n)です。
この連載では、以下の種類のリンクリストについて、それぞれの機能の違いと共に勉強していきます。
- シングルリンクリスト
- ダブリーリンクリスト
- サーキュラーリンクリスト（Circular Linked List
- ヘッダー付きリンクリスト
- ソートされたリンクリスト
この記事の最初の部分では、単一リンクリストとそのさまざまな操作に焦点を当てます。
単一リンクリスト
ノード・クラスの作成
シングルリンクリストクラスの作成
リンクリストのアイテムのトラバース
アイテムの挿入
要素のカウント
要素の検索
リンクリストの作成
要素の削除
リンクリストを元に戻す
シングルリンクリスト
単一リンクリストは、リンクリストのすべての種類の中で最も単純なものです。
単一リンクリストの各ノードには、項目と次の項目への参照が含まれ、それだけで構成されています。
このセクションでは、単一リンクリストのノードを作成する方法と、さまざまなタイプの挿入、走査、削除のための関数について説明します。
ノードクラスの作成
最初にしなければならないことは、ノード用のクラスを作成することです。
このクラスのオブジェクトは、リンクリストに挿入される実際のノードになります。
単一のリンクリストのノードには、項目と次のノードへの参照が含まれることが分かっています。
したがって、このノードクラスは 2 つのメンバ変数 item と ref を含むことになる。
itemの値はコンストラクタに渡された値で設定され、ref の値は初期値として null が設定される。
次のスクリプトを実行します。
class Node:
def __init__(self, data):
self.item = data
self.ref = None
単一リンクリストクラスの作成
次に、リンクリストのクラスを作成する必要があります。
このクラスは、リストの挿入、削除、トラバース、ソートのメソッドを含むことになります。
最初は、リストの最初のノードを指すメンバ start_node を1つだけ含むクラスを作成します。
リンクリストは作成時に空になるので、コンストラクタで start_node の値を NULL に設定します。
次のスクリプトは、リンクリストのクラスを作成します。
class LinkedList:
def __init__(self):
self.start_node = None
これで、単一リストのクラスが作成されました。
次は、リンクリストに項目を挿入するための挿入関数を追加します。
しかし、その前に、リンクリストをトラバースする関数を追加します。
この関数は、リスト内のデータを読み込むのに役立ちます。
リンクされたリストの項目を走査する
traverse 関数の Python コードは以下の通りです。
前節で作成した LinkedList クラスに、以下の関数を追加します。
def traverse_list(self):
if self.start_node is None:
print("List has no element")
return
else:
n = self.start_node
while n is not None:
print(n.item , " ")
n = n.ref
上の関数で何が起こっているか見てみましょう。
この関数は2つの主要な部分から成っています。
まず、リンクリストが空かどうかをチェックします。
次のコードはそれをチェックするものです。
if self.start_node is None:
print("List has no element")
return
リンクリストが空であれば，イテレートする項目がないことを意味する．このような場合、traverse_list()関数は単にリストにはアイテムがないというステートメントを表示します。
そうでない場合は、リストがアイテムを持っていれば、以下のようなコードが実行されます。
n = self.start_node
while n is not None:
print(n.item , " ")
n = n.ref
先ほど述べたように、変数 start には最初のノードへの参照が格納されます。
したがって、変数 n を変数 start で初期化する。
次に、n がゼロになるまでループを実行する。
ループの中では、現在のノードに格納されているアイテムを表示し、変数 n の値を次のノードへの参照を含む n.ref に設定する。
最後のノードの参照は、それ以降のノードが存在しないので None となる。
したがって、nが None になると、ループは終了する。
さて、リンクリストをたどる関数ができたので、1つのリンクリストに項目を追加する方法を見てみましょう。
項目の挿入
項目を挿入する場所によって、1つのリンクリストに項目を挿入する方法は異なります。
先頭の項目を挿入する
単一リンクリストに項目を挿入する最も簡単な方法は、リストの先頭に項目を追加することです。
次の関数は、リストの先頭に項目を挿入します。
この関数を、先ほど作成した LinkedList クラスに追加してください。
def insert_at_start(self, data):
new_node = Node(data)
new_node.ref = self.start_node
self.start_node= new_node
上のスクリプトでは、メソッド insert_at_start() を作成しています。
このメソッドは、基本的に挿入したいアイテムの値を1つのパラメータとして受け取ります。
このメソッドの内部では、Node クラスのオブジェクトを作成して、その参照を start_node に設定します。
なぜなら、start_node はこれまで最初のノードを格納していたので、新しいノードを開始位置に挿入した後は 2 番目のノードになるからです。
そのため、start_node の参照を新しいノードの ref 変数に追加します。
これで new_node が最初のノードになったので、 start_node 変数の値を new_node に設定します。
末尾に項目を挿入する
リンクリストの末尾に項目を追加するには、次の関数を使用します。
def insert_at_end(self, data):
new_node = Node(data)
if self.start_node is None:
self.start_node = new_node
return
n = self.start_node
while n.ref is not None:
n= n.ref
n.ref = new_node;
上のスクリプトでは、リンクリストの末尾に要素を挿入する関数 insert_at_end() を作っています。
挿入したい項目の値は、関数の引数として渡される。
この関数は2つの部分から構成されています．まず、リンクリストが空かどうかを調べます。
リンクリストが空の場合は、変数 start_node の値を new_node オブジェクトにセットするだけです。
一方、リストがすでにいくつかのノードを含んでいる場合。
変数 n を開始ノードで初期化します。
次に、traverse_list 関数の場合と同様に while ループを使用して、リスト内のすべてのノードを繰り返し処理します。
ループは最後のノードに到達すると終了します。
そして、最後のノードの参照を、新しく作成した new_node に設定します。
Insert_at_end()関数をLinkedList` クラスに追加してください。
別のアイテムの後にアイテムを挿入する
一つのリンクリストの中で、アイテムを別のアイテムの後に追加する必要があるかもしれません。
そのためには、以下に定義する insert_after_item() 関数を使用します。
def insert_after_item(self, x, data):
n = self.start_node
print(n.ref)
while n is not None:
if n.item == x:
break
n = n.ref
if n is None:
print("item not in the list")
else:
new_node = Node(data)
new_node.ref = n.ref
n.ref = new_node
関数 insert_after_item() は 2 つのパラメータを受け取ります。
xとdata` です。
最初のパラメータは新しいノードを挿入したいアイテムの後、2番目のパラメータは新しいノードの値を格納します。
まず、新しい変数 n を作成し、変数 start_node をそれに代入します。
次に、while ループを使ってリンクリストを走査します。
while ループは n が None になるまで実行されます。
各反復の間に、現在のノードに格納されている値が x パラメータで渡された値と等しいかどうかをチェックする。
もし比較が真を返したら、ループを抜ける。
次に、アイテムが見つかれば、変数 n は None ではなくなります。
nが格納する参照にnew_nodeが設定され、nの参照にはnew_nodeが設定されます。
LinkesList クラスに insert_after_item() 関数を追加します。
別のアイテムの前にアイテムを挿入する
def insert_before_item(self, x, data):
if self.start_node is None:
print("List has no element")
return
if x == self.start_node.item:
new_node = Node(data)
new_node.ref = self.start_node
self.start_node = new_node
return
n = self.start_node
print(n.ref)
while n.ref is not None:
if n.ref.item == x:
break
n = n.ref
if n.ref is None:
print("item not in the list")
else:
new_node = Node(data)
new_node.ref = n.ref
n.ref = new_node
上のスクリプトでは、insert_before_item()という関数を定義しています。
この関数は3つの部分から構成されています。
それぞれの部分について詳しく見ていきましょう。
if self.start_node is None:
print("List has no element")
return
上のスクリプトでは、リストが空であるかどうかをチェックしています。
もしリストが空なら、リストには要素がないことを表示して、この関数から戻ります。
次に、要素が最初のインデックスにあるかどうかをチェックする。
次のスクリプトを見てみよう。
if x == self.start_node.item:
new_node = Node(data)
new_node.ref = self.start_node
self.start_node = new_node
return
もし，新しいノードを挿入したい要素が最初のインデックスにあれば，そのノードの参照を設定する。
新しく挿入するノードの参照を start_node に設定し、次に start_node の値を new_node に設定するだけです。
最後に、リストが None でなく、最初のインデックスに要素が見つからない場合は、新しい変数 n を作成して、変数 start_node をそれに代入します。
次に、while ループを使ってリンクリストを走査します。
while ループは n.ref が None になるまで実行されます。
各反復の間に、現在のノードの参照に格納されている値が、 x パラメータで渡された値と等しいかどうかをチェックします。
比較の結果、true を返した場合は、ループを抜けます。
次に、アイテムが見つかった場合、 n.ref 変数は None ではありません。
nの参照がnew_nodeに設定され、nの参照はnew_node` に設定されます。
次のスクリプトを見てください。
if n.ref is None:
print("item not in the list")
else:
new_node = Node(data)
new_node.ref = n.ref
n.ref = new_node
LinkedListクラスにinsert_before_item()` 関数を追加する。
特定のインデックスにアイテムを挿入する
特定のインデックスにアイテムを挿入する必要がある場合、次のスクリプトを使用することで挿入できます。
def insert_at_index (self, index, data):
if index == 1:
new_node = Node(data)
new_node.ref = self.start_node
self.start_node = new_node
i = 1
n = self.start_node
while i < index-1 and n is not None:
n = n.ref
i = i+1
if n is None:
print("Index out of bound")
else:
new_node = Node(data)
new_node.ref = n.ref
n.ref = new_node
このスクリプトでは、まずアイテムを格納したいインデックスが1であるかどうかをチェックし、次に start_node を new_node の参照に割り当てて、start_node の値を new_node に設定するだけです。
次に、カウンタ i が index-1 以上になるまで実行する while ループを実行します。
例えば、3番目のインデックスに新しいノードを追加したい場合。
whileループの最初の繰り返しで、iは2になり、現在繰り返し実行されているノードは ‘2’ になります。
i` は現在 2 であり、index-1 と等しい (3-1=2) ので、ループは再び実行されることはないでしょう。
したがって、このループは中断されます。
次に、現在反復しているノード(ノード2)の後に新しいノードを追加します。
したがって、新しいノードはindexの位置に追加されます。
なお，引数として渡されたindexやlocationがリンクリストのサイズより大きい場合，indexが範囲外や境界外であるというメッセージが表示されます．
挿入関数のテスト
さて、挿入関数をすべて定義したので、テストしてみましょう。
まず、以下のようにリンクリストクラスのオブジェクトを作成します。
new_linked_list = LinkedList()
次に、まず insert_at_end() 関数を呼び出して、リンクリストに3つの要素を追加してみましょう。
次のスクリプトを実行する。
new_linked_list.insert_at_end(5)
new_linked_list.insert_at_end(10)
new_linked_list.insert_at_end(15)
実際にアイテムが挿入されたかどうかを確認するために、traverse関数を使ってリンクリストをトラバースしてみましょう。
new_linked_list.traverse_list()
次のような出力が表示されるはずです。
5
10
15
次に、先頭の要素を追加してみましょう。
new_linked_list.insert_at_start(20)
ここで、リストを走査すると、次のような出力が得られるはずである。
20
5
10
15
項目10の後に新しい項目17を追加してみましょう。
new_linked_list.insert_after_item(10, 17)
リストを走査すると、今度は次のような出力が返ってくる。
20
5
10
17
15
17 が 10 の後に挿入されているのがわかるでしょう。
では、次のように insert_before_item() 関数を使用して、アイテム 17 の前に別のアイテム 25 を挿入してみましょう。
new_linked_list.insert_before_item(17, 25)
これで、リストには次のような要素が含まれるようになります。
20
5
10
25
17
15
最後に、3番目の場所に要素を追加してみましょう。
現在10が占めている場所です。
10が1つ前に移動して、その場所に新しいアイテムが挿入されるのがわかるでしょう。
このためには、insert_at_index()関数を使用します。
次のスクリプトは、リストの3番目のインデックスにアイテム 8 を挿入します。
new_linked_list.insert_at_index(3,8)
ここで、リストを走査してみると、次のような出力が得られるはずです。
20
5
8
10
25
17
15
これで、すべての挿入関数をテストしました。
現在、リストには7つの要素があります。
では、リンクリストの要素数を返す関数を書いてみましょう。
エレメントを数える
次の関数は、要素の総数をカウントします。
def get_count(self):
if self.start_node is None:
return 0;
n = self.start_node
count = 0;
while n is not None:
count = count + 1
n = n.ref
return count
上のスクリプトでは、リンクリストの要素数を単純にカウントする get_count() 関数を作成しています。
この関数は、単純に配列のすべてのノードを走査し、whileループを使ってカウンタを増加させます。
ループの最後には、ループ内の要素の総数がカウンタに格納されます。
上記の関数を LinkedList クラスに追加して、LinkedList クラスをコンパイルし、前のセクションで行ったように LinkedList にいくつかの要素を挿入してみましょう。
前のセクションの終わりには、リンクリストに7つの項目がありました。
そこで、get_count() 関数を使って、リストに含まれるアイテムの総数を取得してみましょう。
new_linked_list.get_count()
出力には、リンクリストのアイテムの数が表示されるはずです。
あるいは、リストの ‘カウント’ を取得する別の方法として、 LinkedList クラスに属する単純なカウンター変数で、リストに挿入されたアイテムと削除されたアイテムの数を追跡することができます。
この方法は、クラスの外側からリストのデータ構造を操作できない場合に有効で、上記の get_count メソッドよりも高速に動作します。
検索対象要素
要素の検索は、リンクリストのカウントやトラバースとよく似ていて、各反復の間に検索する値とnodeの値を比較するだけでよい。
値が見つかれば、値が見つかったことを表示してループを抜けます。
search_item()`のスクリプトは以下の通りである。
def search_item(self, x):
if self.start_node is None:
print("List has no elements")
return
n = self.start_node
while n is not None:
if n.item == x:
print("Item found")
return True
n = n.ref
print("item not found")
return False
上記の関数を LinkedList クラスに追加する。
先に作成したリストの中の要素を検索してみよう。
以下のスクリプトを実行してください。
new_linked_list.search_item(5)
リンクリストに5を挿入したので、上の関数はtrueを返します。
出力はこのようになります。
Item found
True
リンクリストの作成
挿入関数のどれかを使って、1つずつ項目を追加していくことができますが。
ノードの要素数、そして個々の要素を入力してもらい、その要素をリンクリストに入力する関数を作ってみましょう。
def make_new_list(self):
nums = int(input("How many nodes do you want to create: "))
if nums == 0:
return
for i in range(nums):
value = int(input("Enter the value for the node:"))
self.insert_at_end(value)
上のスクリプトでは、まず make_new_list() 関数がユーザーにリスト内の要素数を尋ねます。
次に for ループを使って、各ノードの値を入力するように指示し、 insert_at_end() 関数を使ってその値をリンクリストに挿入しています。
次のスクリーンショットは make_new_list() 関数が動作している様子を示しています。
エレメントの削除
このセクションでは、単一リンクリストから要素を削除するさまざまな方法について説明します。
スタートから削除
リンクリストの先頭の要素や項目を削除するのは簡単です。
これは、以下のように、スタートノードの参照(2番目のノードを指している)の値をスタートノードに代入することで行えます。
def delete_at_start(self):
if self.start_node is None:
print("The list has no element to delete")
return
self.start_node = self.start_node.ref
上のスクリプトでは、まず、リストが空かどうかをチェックしている。
リストが空の場合は、リストに削除する要素がないことを示すメッセージを表示する。
そうでない場合は、start_node.ref の値を start_node に代入します。
これで start_node は2番目の要素を指すようになります。
linkedListクラスにdelete_at_start()` 関数を追加してください。
末尾の削除
リストの末尾から要素を削除するには、リンクリストを末尾から2番目の要素まで繰り返し実行し、末尾から2番目の要素の参照をnoneに設定して、末尾から2番目の要素を最後の要素に変換するだけでよい。
関数 delete_at_end のスクリプトは次のとおりです。
def delete_at_end(self):
if self.start_node is None:
print("The list has no element to delete")
return
n = self.start_node
while n.ref.ref is not None:
n = n.ref
n.ref = None
上記のスクリプトを LinkedList() クラスに追加する。
項目値による削除
値を指定して要素を削除するには、まず、指定した値の項目を含むノードを探し、そのノードを削除する必要があります。
指定した値を持つ項目を見つけるのは、項目を検索するのとほぼ同じです。
削除する項目が見つかったら、その項目より前のノードの参照を、削除する項目より後に存在するノードに設定します。
次のスクリプトを見てください。
def delete_element_by_value(self, x):
if self.start_node is None:
print("The list has no element to delete")
return
# Deleting first node
if self.start_node.item == x:
self.start_node = self.start_node.ref
return
n = self.start_node
while n.ref is not None:
if n.ref.item == x:
break
n = n.ref
if n.ref is None:
print("item not found in the list")
else:
n.ref = n.ref.ref
上のスクリプトでは、まずリストが空かどうかをチェックしている。
次に、削除する要素がリンクリストの先頭にあるかどうかをチェックする。
もし要素が先頭にあれば、最初のノードに最初のノードの参照（基本的には2番目のノードを参照）をセットして、その要素を削除する。
最後に、要素が最初のインデックスで見つからなかった場合、リンクリストを繰り返し、繰り返し実行されているノードの値が削除する値と等しいかどうかをチェックします。
削除関数のテスト
先ほど作成した削除関数をテストしてみましょう。
その前に、以下のスクリプトを使って、リンクリストにダミーデータを追加してみましょう。
new_linked_list.insert_at_end(10)
new_linked_list.insert_at_end(20)
new_linked_list.insert_at_end(30)
new_linked_list.insert_at_end(40)
new_linked_list.insert_at_end(50)
上のスクリプトは、リンクリストに5つの要素を追加するものです。
このリストを走査すると、次のような項目が見えるはずです。
10
20
30
40
50
まず、先頭の項目を削除してみよう。
new_linked_list.delete_at_start()
ここで、リストを走査すると、次のような出力が現れるはずである。
20
30
40
50
では、最後にある要素を削除してみましょう。
new_linked_list.delete_at_end()
このリストには、次のような項目が含まれています。
20
30
40
最後に、ある要素を値で削除してみましょう。
new_linked_list.delete_element_by_value(30)
これで、リストを走査しても、項目30は表示されないはずです。
リンクリストの反転
リンクリストを反転させるには、 prev、n、next という 3 つの変数が必要です。
prevは前のノード、nextは次のノード、n` は現在のノードに対応します。
変数 n に開始ノードを代入して while ループを開始し、変数 prev は None に初期化されます。
ループは n が none になるまで実行される。
whileループの内部では、以下の機能を実行する必要があります。
- カレントノードのリファレンスの値を
nextに代入する。 - カレントノード
nの参照の値をprevにセットする。 - カレントノード
nにprev変数をセットします。 - カレントノード
nにnextノードの値をセットする。
ループの最後には、 prev 変数が最後のノードを指しているので、これを最初のノードにする必要があります。
そこで、 self.start_node 変数の値を prev に設定します。
whileループは各ノードがその前のノードを指すようにし、結果として逆リンクリストができあがります。
スクリプトは以下の通りです。
def reverse_linkedlist(self):
prev = None
n = self.start_node
while n is not None:
next = n.ref
n.ref = prev
prev = n
n = next
self.start_node = prev
上記の関数を LinkedList クラスに追加する。
乱数のリンクリストを作成し、reverse_linkedlist()関数を使ってそれを反転させられるかどうか試してみてください。
結論
この記事では、単一のリンクされたリストについての議論を開始しました。
リンクリストの走査、リンクリストへの項目の挿入、リンクリストの項目の検索とカウント、リンクリストからの項目の削除、単一リンクリストの反転など、リンクリストに対して実行できるさまざまな関数について見てきました。
今回は、リンクリストに関する連載の第1回目です。
次のパート（近日公開）では、単一のリンクリストをソートする方法、ソートされたリンクリストをマージする方法、単一のリンクリストからサイクルを削除する方法について説明します。