Python-data-structure-python-linked-lists
Python-リンクリスト
リンクリストは、リンクを介して互いに接続されたデータ要素のシーケンスです。 各データ要素には、別のデータ要素へのポインタ形式の接続が含まれています。 Pythonの標準ライブラリにはリンクリストがありません。 前の章で説明したノードの概念を使用して、リンクリストの概念を実装します。 ノードクラスを作成する方法と、ノードの要素をトラバースする方法については既に説明しました。 この章では、単一リンクリストと呼ばれるリンクリストの種類について学習します。 このタイプのデータ構造では、2つのデータ要素間に1つのリンクしかありません。 このようなリストを作成し、リストから要素を挿入、更新、削除する追加のメソッドを作成します。
リンクリストの作成
リンクリストは、前の章で学習したノードクラスを使用して作成されます。 Nodeオブジェクトを作成し、このodeオブジェクトを使用する別のクラスを作成します。 次のデータ要素を指すようにノードオブジェクトを介して適切な値を渡します。 以下のプログラムは、3つのデータ要素を含むリンクリストを作成します。 次のセクションでは、リンクリストを走査する方法を見ていきます。
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3
リンクリストをたどる
単一リンクリストは、最初のデータ要素から始まる順方向でのみトラバースできます。 次のノードのポインターを現在のデータ要素に割り当てることにより、次のデータ要素の値を単に印刷します。
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3
list.listprint()
上記のコードが実行されると、次の結果が生成されます。
Mon
Tue
Wed
リンクリストへの挿入
リンクリストに要素を挿入するには、既存のノードから新しく挿入されたノードにポインターを再割り当てする必要があります。 新しいデータ要素がリンクリストの最初に挿入されるのか、中間に挿入されるのか、最後に挿入されるのかに応じて、以下のシナリオがあります。
リンクリストの先頭に挿入する
これには、新しいデータノードの次のポインターをリンクリストの現在のヘッドにポイントすることが含まれます。 したがって、リンクリストの現在のヘッドが2番目のデータ要素になり、新しいノードがリンクリストのヘッドになります。
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
# Print the linked list
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
def AtBegining(self,newdata):
NewNode = Node(newdata)
# Update the new nodes next val to existing node
NewNode.nextval = self.headval
self.headval = NewNode
list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
list.headval.nextval = e2
e2.nextval = e3
list.AtBegining("Sun")
list.listprint()
上記のコードが実行されると、次の結果が生成されます。
Sun
Mon
Tue
Wed
リンクリストの最後に挿入する
これには、リンクリストの現在の最後のノードの次のポインターを新しいデータノードにポイントすることが含まれます。 したがって、リンクリストの現在の最後のノードは2番目の最後のデータノードになり、新しいノードはリンクリストの最後のノードになります。
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
# Function to add newnode
def AtEnd(self, newdata):
NewNode = Node(newdata)
if self.headval is None:
self.headval = NewNode
return
laste = self.headval
while(laste.nextval):
laste = laste.nextval
laste.nextval=NewNode
# Print the linked list
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
list.headval.nextval = e2
e2.nextval = e3
list.AtEnd("Thu")
list.listprint()
上記のコードが実行されると、次の結果が生成されます。
Mon
Tue
Wed
Thu
2つのデータノード間に挿入する
これには、特定のノードのポインターを変更して、新しいノードを指すことが含まれます。 これは、新しいノードと既存のノードの両方を渡すことで可能になり、その後に新しいノードが挿入されます。 したがって、新しいノードの次のポインターを中間ノードの次のポインターに変更する追加のクラスを定義します。 次に、新しいノードを中間ノードの次のポインターに割り当てます。
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
# Function to add node
def Inbetween(self,middle_node,newdata):
if middle_node is None:
print("The mentioned node is absent")
return
NewNode = Node(newdata)
NewNode.nextval = middle_node.nextval
middle_node.nextval = NewNode
# Print the linked list
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Thu")
list.headval.nextval = e2
e2.nextval = e3
list.Inbetween(list.headval.nextval,"Fri")
list.listprint()
上記のコードが実行されると、次の結果が生成されます。
Mon
Tue
Fri
Thu
いいねリストからアイテムを削除する
そのノードのキーを使用して、既存のノードを削除できます。 以下のプログラムで、削除するノードの前のノードを見つけます。 次に、このノードの次のポインターを、削除するノードの次のノードに向けます。
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class SLinkedList:
def __init__(self):
self.head = None
def Atbegining(self, data_in):
NewNode = Node(data_in)
NewNode.next = self.head
self.head = NewNode
# Function to remove node
def RemoveNode(self, Removekey):
HeadVal = self.head
if (HeadVal is not None):
if (HeadVal.data == Removekey):
self.head = HeadVal.next
HeadVal = None
return
while (HeadVal is not None):
if HeadVal.data == Removekey:
break
prev = HeadVal
HeadVal = HeadVal.next
if (HeadVal == None):
return
prev.next = HeadVal.next
HeadVal = None
def LListprint(self):
printval = self.head
while (printval):
print(printval.data),
printval = printval.next
llist = SLinkedList()
llist.Atbegining("Mon")
llist.Atbegining("Tue")
llist.Atbegining("Wed")
llist.Atbegining("Thu")
llist.RemoveNode("Tue")
llist.LListprint()
上記のコードが実行されると、次の結果が生成されます。
Thu
Wed
Mon