Initialise two variables to point to same reference in Python-CodePudding

I have seen many similar questions here, but none of them deal with what I want to know. Let's take an example.

I want to make a linked list from an array. Ignoring all the boilerplate, let's get to the meat of this question.

arr = [1, 2, 3, 4, 5]
tail = head = None  # this is the problematic line
for item in arr:
  tail = Node(val=item, next=None)
  tail = tail.next
return head

Needless to say, this does not work. Head always points to None, no matter what tails points to.

Some other things I have tried:

head = tail = [] # head will point to the empty list after finishing
head = tail = any_other_singleton # does not work

I know why this happens. Its because I am reassigning tail to point to a Node. But I want to keep a reference to the head of the liked list in 'head'. How can I make this work? In other programming languages this is trivial, but in python you have to assign a value to variable when declaring, which is causing me problems.

CodePudding user response：

Just handle the first item separately.

arr = [1, 2, 3, 4, 5]
head = tail = Node(val=arr[0], next=None)
for item in arr[1:]:
    tail.next = Node(val=item, next=none)
    tail = tail.next
return head

CodePudding user response：

Could use a dummy before the real list. That won't crash if arr is empty.

arr = [1, 2, 3, 4, 5]
tail = dummy = Node(val=None, next=None)
for val in arr:
    tail.next = tail = Node(val=val, next=None)
return dummy.next

Not tested, due to missing Node class.

CodePudding user response：

What you want to achieve can probably be done like this.

from collections import namedtuple


Node = namedtuple('Node', ['val', 'next'])


def array_to_list(arr):
    lst = None
    for a in reversed(arr):
        lst = Node(val=a, next=lst)
    return lst
    

x = array_to_list([1, 2, 3]) 
print(x)

Next code might help with understanding if you never worked with persistent (immutable) data structures:

def insert_recursive(lst, pos, value):
    if not pos or not lst:
        return Node(val=value, next=lst)
    return Node(val=lst.val, next=insert_recursive(lst.next, pos - 1, value))
    

def insert_nonrecursive(lst, pos, value):
    values = []
    while lst and pos:
        values.append(lst.val)
        lst = lst.next
        pos -= 1
    result = Node(val=value, next=lst)
    while len(values):
        result = Node(val=values.pop(), next=result)
    return result
    

y = insert_recursive(x, 1, 42)
print(y)

z = insert_nonrecursive(x, 1, 42)
print(z)

CodePudding user response：

I know functools.reduce is a bit of black-sheep in the Python world, but it makes a nice one-liner for this if you process the list in reverse. For example:

from functools import reduce
from collections import namedtuple

Node = namedtuple('Node', ['next', 'val']) # or alternatively a class with next, val members
        
arr = [1, 2, 3, 4, 5]

# Make Linked List
lst = reduce(Node, reversed(arr), None)

# Try printing them
head = lst
while head:
    print(head.val)
    head = head.next

Will print: