Converting a list to a linked list

Question

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() +'>')

Answer 1

Matt'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()

Answer 2

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.next

Answer 3

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.reference

Answer 4

In 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()