問題2.3

世界で闘うプログラミング力を鍛える150問

問題自体は簡単。
Pythonのオーバーライドや、doctestのELLIPSISの使い方は多少参考になるかも？
ってかこの本、邦訳が悪いのか、たまに質問の意味がわからないですね。

問題

単方向連結リストにおいて、中央の要素のみアクセス可能であるとします。その要素を削除するアルゴリズムを実装してください。

例
入力：a->b->c->d->eという連結リストのcが与えられます。
結果：何も返しませんが、リストはa->b->d->eのように見えます。

importしてるpylist.pyは問題2.1で作ったものです。

http://d.hatena.ne.jp/takuto1981/20121211/1355198127

pylist2.py (単方向連結リスト)

#encoding: utf-8
from pylist import Cell
from pylist import LinkedList


class LinkedList2(LinkedList):
    '''
    LinkedListとほぼ同じだが、insert関数だけ変更したクラス
    >>> linked_list = LinkedList2()
    >>> linked_list.get_top()
    >>> linked_list.insert(0, 100) # doctest:+ELLIPSIS
    <pylist.Cell instance at ...>
    >>> print linked_list.index(100)
    0
    '''
    # オリジナルのinsertと同じだが、作成したCellのポインタを返す関数
    def insert(self, offset, data):
        # offsetが0もしくはリストが空の時
        if offset == 0 or not self.top:
            self.top = Cell(data, self.top)
            return self.top
        else:
            cell = self.top
            while cell.get_next():
                offset -= 1
                if offset == 0:
                    break
                cell = cell.get_next()
            # 新たにセルを作成し、リストに挿入する
            added_cell = Cell(data, cell.get_next())
            cell.set_next(added_cell)
            return added_cell


def _test():
    import doctest
    doctest.testmod()


if __name__ == '__main__':
    _test()

2-3.py (指定セルの削除)

#encoding: utf-8
from pylist2 import Cell
from pylist2 import LinkedList2


def delete_cell(linked_list, cell):
    '''
    linked_listよりcellを削除する関数。
    linked_listの先頭セルはアクセス不可とする。
    >>> linked_list = LinkedList2()
    >>> target_cell1 = linked_list.insert(0, 'a')
    >>> linked_list.insert(1, 'b') #doctest:+ELLIPSIS
    <pylist.Cell instance at ...>
    >>> linked_list.insert(2, 'c') #doctest:+ELLIPSIS
    <pylist.Cell instance at ...>
    >>> target_cell2 = linked_list.insert(3, 'd')
    >>> linked_list.insert(4, 'e') #doctest:+ELLIPSIS
    <pylist.Cell instance at ...>
    >>> target_cell3 = linked_list.insert(5, 'f')
    >>> linked_list.index('d')
    3
    >>> delete_cell(linked_list, target_cell2)
    True
    >>> linked_list.index('d')
    -1
    >>> delete_cell(linked_list, target_cell1)
    True
    >>> linked_list.index('a')
    -1
    >>> delete_cell(linked_list, target_cell3)
    False
    '''
    if cell.get_next():
        # 指定されたセルの次のセルを、指定されたセルに上書き。
        next_cell = cell.get_next()
        cell.set_data(next_cell.get_data())
        cell.set_next(next_cell.get_next())
        return True
    # 末尾のセルは削除対象外
    else:
        return False


def _test():
    import doctest
    doctest.testmod()


if __name__ == '__main__':
    _test()