從單鏈表到雙鏈表

Question

如何編寫一個函數，如'next（lst）'返回PREVIOUS值而不是NEXT值？

class EmptyNode(): 
    __slots__ =() 

class Node(): 
    __slots__ = ('data', 'next') 


class MyList(): 
"""A class that encapsulates a node based linked list""" 
    __slots__ = ('head', 'size', 'cursor') 

def mkEmptyNode(): 
    return EmptyNode() 

def mkNode(data, next): 
    node = Node() 
    node.data = data 
    node.next = next 
    return node 

def mkMyList(): 
    lst = MyList() 
    lst.head = mkEmptyNode() 
    lst.size = 0 
    lst.cursor = mkEmptyNode() 
    return lst 

在鏈表類似['a','b','c']，next(lst)將返回'a'，下一次將返回'b'，下一次將返回'c'，並在下一次會返回一個錯誤

def next(lst): 
    if isinstance(lst.cursor, EmptyNode): 
     raise IndexError("cursor is invalid") 

    val = lst.cursor.data 
    lst.cursor = lst.cursor.next 
    return val 

Answer 1

您需要在每個列表項（previous）中保留一個額外的指針。

class EmptyNode(): 
    __slots__ =() 

class Node(): 
    __slots__ = ('data', 'next', 'prev') 

class MyList(): 
    """A class that encapsulates a node based linked list""" 
    __slots__ = ('head', 'size', 'cursor') 

def mkEmptyNode(): 
    return EmptyNode() 

def mkNode(prev, data, next): 
    node = Node() 
    node.prev = prev 
    node.data = data 
    node.next = next 
    return node 

def mkMyList(): 
    lst = MyList() 
    lst.head = mkEmptyNode() 
    lst.size = 0 
    lst.cursor = mkEmptyNode() 
    return lst 

然後，您可以用它來導航向後名單：

def previous(lst): 
    if isinstance(lst.cursor, EmptyNode): 
    raise IndexError("cursor is invalid") 

    val = lst.cursor.data 
    lst.cursor = lst.cursor.prev 
    return val 

Answer 2

在常規的雙向鏈表，你會添加一個prev屬性節點類（指着以前節點），然後添加一個分組的方法，做一樣的東西：

class Node(): 
    __slots__ = ('data', 'next', 'prev') 

然後：

def prev(lst): 
    if isinstance(lst.cursor, EmptyNode): 
     raise IndexError("cursor is invalid") 

    val = lst.cursor.data 
    lst.cursor = lst.cursor.prev 
    return val