up vote 4 down vote favorite

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.

share|improve this question
1  
do you really need a linked list? – Winston Ewert♦ Jan 24 '12 at 1:06
Comparisons with None are best done based on identity (since None is a singleton), so while current.next is not None will suffice. Given that Cell has no defined boolean truthness, it is as object "always True" and you could reduce the while loop to while current.next. – Elmer Jan 26 '12 at 14:50

4 Answers

up vote 3 down vote accepted

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
share|improve this answer
Of course, if you don't need the values of the Cells to be increasing the xrange statement could be drastically simplified. This would make the second, reverse, create_list function a lot easier on the eyes. – Elmer Jan 26 '12 at 14:55
up vote 1 down vote

Just assign to the previous node's next attribute directly in the loop:

def create_list(n):
    for i in range(n):
        c = cell.Cell(n)
        if i == 0:
            lst = c
        else:
            prev.next = c
        prev = c
    return lst
share|improve this answer
Do you propose to test i==0 at every step of the loop? – s.zakharov Feb 4 '12 at 20:09
up vote 1 down vote 
def list_concat(A, B):
    current = A
    while current.next != None:
        current = current.next
    current.next = B
    # Why 'return A' when the caller already gave A?

Aside from adding a function that implimented list_concat for arrays, you could just make a simple edit to create_list:

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

Now, every time list_concat runs, it starts at the end of the list and just appends b.

I'd recomend, over the above, writing a class that held the first and last nodes in the list. That way, it'd be as simple as

def create_list(n):
    list = List()
    for x in range( 0, n ):
        list.put_at_end( Cell(x) ) # or list.append_cell(x)
share|improve this answer
up vote 0 down vote 
def create_list(n):
    a = cell.Cell(0)
    for i in (range(1,n)):

You don't need the parens around range(1,n) 

        b = cell.Cell(i)
        new_list = cell.list_concat(a, b)   
    return new_list

It'll be faster if you build the list in reverse order.

share|improve this answer

Your Answer

 
or
required, but never shown
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.