《19》連結リスト課題（補足）〈Python 2.x 版〉

実録：はじめてのプログラミング《記事一覧》
《19》連結リスト課題（補足）

《著》小粒ちゃん＋α《監修》小泉ひよ子とタマゴ倶楽部

2009年2月9日(月)

実録はじめての…《19》連結リスト課題 - 続・ひよ子のきもち〈Python 2.x 版〉

連結リスト課題（補足）

連結リストの末尾に要素を追加する様子を、図解とともに解説します。

class myList(object):
    def __init__(self):
        self.head = self.tail = Node()

def ex():
    s = myList()        ; print s

>>> ex()
[]

連結リストのインスタンスを生成（初期設定）したときには、属性 head および tail は、空のノード Node() を参照しています。

連結リストにメソッド append を利用して、新たなノード Node() を追加するときには、次の３つのステップを踏みます。

class myList(object):
    def append(self, item):
        node = Node(item, self.tail.next)    # (1)
        self.tail.next = node                # (2)
        self.tail = node                     # (3)

def ex():
    s = myList()        ; print s
    s.append("A")       ; print s

>>> ex()
[]
['A']

（1）新たなノードの後続は、属性 self.tail.next と同じものを参照します。すると、新たなノードの後続は None になり、そこが終端になります。
（2）旧い末尾のノード self.tail.next は、新たなノード node を参照します。すると、そのノードが末尾に追加（挿入）されます。
（3）末尾のノードを表わす属性 self.tail は、新たなノード node を参照します。すると、そのノードが新たな末尾になります。

    s.append("B")       ; print s

>>> ex()
...
['A', 'B']

ノード A の後続として、新たなノード B を追加（挿入）します。

    s.append("C")       ; print s

>>> ex()
...
['A', 'B', 'C']

ノード B の後続として、新たなノード C を追加（挿入）します。

Tips

図解にすることが目的ではありませんが、それで理解が深まるなら、それを躊躇する理由はありません。図解にすることは、理解を助ける手段のひとつにすぎないのです。《ひよ子》

Last updated♪09/03/10

関連記事

連結リスト課題（補足）

Tips