I'm trying to figure out to convert a list to a linked list. I already have a class for the link but I'm trying to figure out how to convert a list to linked list, for example:
def list_to_link(lst): """Takes a Python list and returns a Link with the same elements. >>> link = list_to_link([1, 2, 3]) >>> print_link(link) <1 2 3> """
class Link: empty = () def __init__(self, first, rest=empty): assert rest is Link.empty or isinstance(rest, Link) self.first = first self.rest = rest
def print_link(link): """Print elements of a linked list link.""" >>> link = Link(1, Link(2, Link(3))) >>> print_link(link) <1 2 3> >>> link1 = Link(1, Link(Link(2), Link(3))) >>> print_link(link1) <1 <2> 3> >>> link1 = Link(3, Link(Link(4), Link(5, Link(6)))) >>> print_link(link1) <3 <4> 5 6> """ print('<' +helper(link).rstrip() +'>')4 Answers
I have an idea using dummy ListNode. This makes code simple and neat.
class ListNode: def __init__(self, x): self.val = x self.next = None
def lst2link(lst): cur = dummy = ListNode(0) for e in lst: cur.next = ListNode(e) cur = cur.next return dummy.nextMatt's answer is good, but it's outside the constraint of the function prototype described in the problem above.
Reading the abstract/prototype, it looks like the creator of the problem wanted to solve this with recursive/dynamic programming methodology. This is a pretty standard recursive algorithm introduction. It's more about understanding how to write elegant recursive code more than creating linked-list in Python (not really useful or common).
Here's a solution I came up with. Try it out:
class Link: empty = () def __init__(self, first, rest=empty): assert rest is Link.empty or isinstance(rest, Link) self.first = first self.rest = rest
def print_link(link): """Print elements of a linked list link. """ print('<' + helper(link).rstrip() +'>')
def list_to_link(lst): """Takes a Python list and returns a Link with the same elements. """ if len(lst) == 1: return Link(lst[0]) return Link(lst[0], list_to_link(lst[1:])) # <<<< RECURSIVE
def helper(link): if isinstance(link.first, Link): first = '<' + helper(link.first).rstrip() + '>' # <<<< RECURSIVE else: first = str(link.first) if link.rest != Link.empty: return first + ' ' + helper(link.rest) # <<<< RECURSIVE else: return first + ' '
def main(): """ Below are taken from sample in function prototype comments """ link = list_to_link([1, 2, 3]) print_link(link) link = Link(1, Link(2, Link(3))) print_link(link) link1 = Link(1, Link(Link(2), Link(3))) print_link(link1) link1 = Link(3, Link(Link(4), Link(5, Link(6)))) print_link(link1)
if __name__ == '__main__': main()This is what you want.
class Node(object): def __init__(self, value, next=None): self.value = value self.reference = next
class LinkedList(object): def __init__(self, sequence): self.head = Node(sequence[0]) current = self.head for item in sequence[1:]: current.reference = Node(item) current = current.reference
a = range(10)
li = LinkedList(li)
current = li.head
while current is not None: print current.value current = current.referenceIn case it helps anyone, here is an example for converting a set (could be a list or array etc...some sequence) to a singly linked list or a doubly linked list:
class LinkedList: def __init__(self): self.head = None def print_in_order(self): ''' print linked list element starting from the head, walking until the end of the list ''' curr_node = self.head print(curr_node.val) while curr_node.next is not None: print(curr_node.next.val) curr_node = curr_node.next
class LinkedListNode: def __init__(self, val=None, next=None): ''' singly linked list individual node ''' self.val = val self.next = next
class SinglyLinkedList(LinkedList): ''' singly linked list ''' def populate_from_set(self, set_to_use: set): ''' iteratively populate a singly linked list from a set of values ''' if len(set_to_use) == 0: raise ValueError('Cannot start a singly linked list from an empty set.') # then iterate through to the end of the set, linking each node to the next node_prev = None for set_i in range(len(set_to_use)): # set the current node node_curr = LinkedListNode(val = set_to_use[set_i]) # set the head of the SLL on the first pass through the set if set_i == 0: self.head = node_curr # otherwise we link the previous node to the current node else: node_prev.next = node_curr # then set the previous node to the current node for the next iteration node_prev = node_curr
class DoublyLinkedListNode(LinkedListNode): def __init__(self, val=None, prev=None, next=None): self.val = val self.prev=prev self.next=next
class DoublyLinkedList(LinkedList): def __init__(self, tail=None): self.tail=tail def populate_from_set(self, set_to_use: set): ''' iteratively populate the doubly linked list from a set of values ''' if len(set_to_use) == 0: raise ValueError('Cannot populate a doubly linked list from an empty set.') prev_node = None for set_i in range(len(set_to_use)): curr_node = DoublyLinkedListNode(val=set_to_use[set_i]) # if we are on the first element, we assign the head if set_i == 0: self.head = curr_node # otherwise we assign a next value to the previous and a # previous to the current else: prev_node.next = curr_node curr_node.prev = prev_node # if we are on the last set element, we assign a tail value if set_i == len(set_to_use)-1: self.tail = curr_node prev_node = curr_node def print_in_reverse_order(self): ''' print all linked list elements starting from the tail and walking along until you hit the head ''' curr_node = self.tail print(curr_node.val) while curr_node.prev is not None: print(curr_node.prev.val) curr_node = curr_node.prev
def main(): days = ('Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat', 'Sun') print('SINGLE:') sll = SinglyLinkedList() sll.populate_from_set(days) sll.print_in_order() print('\n\nDOUBLE:') dll = DoublyLinkedList() dll.populate_from_set(days) print('\n\nforward:') dll.print_in_order() print('\n\nreverse:') dll.print_in_reverse_order()
if __name__=='__main__': main()
