連結リストに関するメモ。
自分が腹落ちすることを優先で自分のイメージで書く。
連結リストについて
概要
通常のリストとの違い
Pythonのリストは先に箱を用意しておき、その箱の中に要素を格納していくイメージ。
一方で連結リストには箱はなく、それぞれの要素は次の要素への道標を持っているので、道標をつなぐイメージ。各要素がそれぞれ次の要素への道標をつなぎ続けることで、連結されたリストができあがる。
連結リストの実装と操作
単方向連結リストの実装
・以下はクラスListNodeの実装
|
1 2 3 4 |
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next |
これはListNodeという名前のクラス。
ListNodeと書いてある通り、連結リストの各ノード(要素)を指すオブジェクト。
普段よく使うリストから連想すると、各要素を格納しておく箱をイメージしてしまうかもしれないが、これは連結リストのそれぞれの要素を表している。
self.valにはこのノード(要素)の値、self.nextには次のノードが格納される。
最初の方に次のノードを指すというようなことを書いたが、
次のノードがself.nextに丸ごと格納されるような形になる。
node1 = [val1, next]
node1 = [val1,[node2]]
node1 = [val1, [val,2 next]]
node1 = [val1, [val2, [val3, next]]]
※node2はその中にvalとnode3を持つ。入れ子構造
・ListNodeのインスタンス、つまり連結リストの一つの要素を作る
|
1 2 3 4 5 6 7 8 9 10 11 |
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next node = ListNode() print(node) #↓これはコマンドプロンプトで実行した場合 #<__main__.ListNode object at 0x000・・・> #↓これはLeetCodeで実行した場合 #ListNode{val: 0, next: None} |
LeetCodeではもともと定義されているListNodeをインスタンス化してprintすると、以下のように表示される
ListNode{val: 0, next: None}
ただし、自分で全く同じ内容で再定義すると、コマンドプロンプトで実行した場合と同じように表示される
<__main__.ListNode object at 0x000・・・>
※これはこのインスタンスがメモリ上のどこにあるかを指しているかということで合っているんだろうか
・複数のノードをつないで連結リストを作ってみる。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# Definition for singly-linked list. class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def test(self, head): one = ListNode(1) two = ListNode(2) three = ListNode(3) head = one one.next = two two.next = three print(head) #ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: None}}} |
one,two,threeをそれぞれListNodeのインスタンスとして用意して、
one.の後ろ(one.next)にtwoを、twoの後ろ(two.next)にthreeを格納してからprintすると、
LeetCodeでは以下のように表示された。
ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: None}}}
・for文で連結リストを作る
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def test(self): head = ListNode() prev = head for i in range(1,4): node = ListNode(i) prev.next = node prev = prev.next print(head) #どのようにprintされるかは後述 return None |
LeetCode上ではprintすると↓このように表示される
ListNode{val: 0, next: ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: None}}}}
コマンドプロンプトで実行できるように少し変更してみる。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
# Definition for singly-linked list. class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next #連結リストheadの先頭の要素を作る。 head = ListNode() #for文内で、前のノードに新しくノードをつなぐためにprevを用意する #prevはheadのメモリ上の位置を指しているので、prevを変更するとheadも変更される prev = head #1~3までのノードをを作り、headの後ろに繋ぐ for i in range(1,4): #ノードを作る。iには1~3が入る node = ListNode(i) #前のノードのnextに今作ったノードを格納(実際にはメモリ上の位置を格納) prev.next = node #今作ったノードを追加したので、連結リストの最後尾が今作ったノードになった。 #次のループでさらに末尾にノードを追加する際、現在のノードは次のループで新しく作るノードにとって、1つ前のノードになる #prev.nextとは、つまり現在のノードのことなのでprev = nodeでも良いが、ともかくリストの最後尾ノードのnextをprevに保存しておく prev = prev.next print(head) #<__main__.ListNode object at 0x0000・・・・> print(head.val, head.next) #0 <__main__.ListNode object at 0x0000・・・・> print(head.next.val, head.next.next) #1 <__main__.ListNode object at 0x0000・・・・> print(head.next.next.val, head.next.next.next) #2 <__main__.ListNode object at 0x0000・・・・> print(head.next.next.next.val, head.next.next.next.next) #3 <__main__.ListNode object at 0x0000・・・・> |
コメント