Faster way to create linked list of length n in Python

I'm attempting to create a linked list of length n using Python. I have the simple list implemented, a working concatenation function, and a working create_list function; however, I just want to know if there is a more efficient method at making the linked list than using my concatenate function (made for testing).

Simple List Class:

class Cell:

    def __init__( self, data, next = None ):
        self.data = data
        self.next = next

Concatenate Function:

def list_concat(A, B):
    current = A
    while current.next != None:
        current = current.next
    current.next = B
    return A

List create (that takes forever!):

def create_list(n):
    a = cell.Cell(0)
    for i in (range(1,n)):
        b = cell.Cell(i)
        new_list = cell.list_concat(a, b)   
    return new_list

This is an assignment, but efficiency is not part of it. I am just wondering if there is a more efficient way to create a large list using this implementation of the structure.

The current algorithm has a failure in using the list_concat during list creation. The list_concat function walks to the end of the list for each node you want to add. So adding a node becomes O(n). This means creating a list of 10,000 items takes 1+2+3...+10,000 steps. That's O(n*n) performance.

As hinted, you should add the next node in the creation loop. You then get code that looks like this (I left out the list_concat function as it's not used):

class Cell(object):
  def __init__(self, data, next=None):
    self.data = data
    self.next = next

def create_list(length=1):
  linked_list = Cell(0)
  head = linked_list
  for prefill_value in xrange(1, length):
    head.next = Cell(prefill_value)
    head = head.next
  return linked_list

You could also create the list in reverse order, allowing you to immediately fill the next attribute of the Cell. Your create_list function then looks like this (the reversed function should not be used for really huge lengths (several million) because it's created in-memory):

def create_list(length=1):
  tail = Cell(length - 1)
  for prefill_value in xrange(length - 2, -1, -1):
    tail = Cell(prefill_value, tail)
  return tail

StackExchange Code Review Q#8237, answer score: 4