기능 링크 된 목록에서 노드 제거 "

Question

특정 노드가없는 링크 된 목록을 반환하는 함수를 찾고 있습니다.

Nil = None     # empty node 

def cons(head, tail=Nil): 
    """ Extends list by inserting new value. """ 
    return (head, tail) 

def head(xs): 
    """ Returns the frst element of a list. """ 
    return xs[0] 

def tail(xs): 
    """ Returns a list containing all elements except the first. """ 
    return xs[1] 

def is_empty(xs): 
    """ Returns True if the list contains zero elements """ 
    return xs is Nil 

def length(xs): 
    """                                            
    Returns number of elements in a given list. To find the length of a list we need to scan all of its                    
    elements, thus leading to a time complexity of O(n).                                
    """ 
    if is_empty(xs): 
     return 0 
    else: 
     return 1 + length(tail(xs)) 

def concat(xs, ys): 
    """ Concatenates two lists. O(n) """ 
    if is_empty(xs): 
     return ys 
    else: 
     return cons(head(xs), concat(tail(xs), ys)) 

가 어떻게 remove_item 기능을 구현할 수 있습니다 여기에

는 예를 구현입니까?

Answer 1

def remove_item(xs, value): 
    if is_empty(xs): 
     return xs 
    elif head(xs) == value: 
     return tail(xs) # or remove_item(tail(xs), value) to remove all 
    else: 
     return cons(head(xs), remove_item(tail(xs), value)) 

참고 : 나는 Lisp 프로그래머가 아니며 가능한 최선의 방법으로 수행하지는 않았습니다.

[편집 : 특정 노드를 제거하여 의미를 잘못 해석했을 수도 있습니다. 당신이 꼬리 재귀 솔루션을 원하는 경우 오히려 xs의 값보다 xs의 접미사로 시작하는 경우 다음 원칙은 동일하지만 value을 포함하는 테스트가 다르다]

Answer 2

, 당신은 말할 수 :

을

def remove_item(xs, value): 
    before_rev, after = split_remove(Nil, xs, value) 
    return reverse_append(before_rev, after) 

def reverse_append(a, b): 
    if is_empty(a): 
    return b 
    else: 
    return reverse_append(tail(a), cons(head(a),b)) 

def split_remove(before_rev, xs, value): 
    if is_empty(xs): 
    return (before_rev, xs) 
    elif head(xs) == value: 
    return (before_rev, tail(xs)) 
    else: 
    return split_remove(cons(head(xs), before_rev), tail(xs), value) 

파이썬이 테일 호출 최적화를 수행하는지 알 수는 없지만