add elements to the end of an linked list

Question

I have done the following linked list in python, it works fine, but I was wondering if there is another way to to the part add_item to a linked list. In that part what I want to do is to keep a pointer in the first element, and so adding the elements in front of it, for example:

1 first

1----->2 first

1----->2----->3 first

my code is:

class Node:
    def __init__(self,elem=None,next=None):
        self.elem=elem
        self.next=next
    def __repr__(self):
        return 'Node(elem={}, next={})'.format(self.elem, self.next)


class LinkedList:
    def __init__(self):
        self.size=0
        self.first=None
        self.linkedlist=Node()

    def add(self,elem):
        node=Node(elem)
        if self.size==0:
            self.first=node
        else:
            self.linkedlist.next=node
        self.linkedlist=node
        self.size=self.size+1

is there another way to perform this behaviour wihout using the auxiliar self.linkedlist that I have in the builder of the LinkedList class?

Thanks

I think a [dequeue](http://stackoverflow.com/questions/280243/python-linked-list) based implementation would give better performance — Sidharth Shah, Oct 01 '14 at 11:55
one but simple simple solution will be at link to prev node. it's will gives you an ability tto add a node to the head of the list. — Dmitry Zagorulkin, Oct 01 '14 at 11:56

score 1 · Answer 1 · answered Oct 01 '14 at 12:02

Keep track of last element and always a new node to its next. Then update the last

class Node:

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


class LinkedList:

    def __init__(self):
        self.size = 0
        self.first = None
        self.last = None

    def add(self, elem):
        node = Node(elem)
        if self.size == 0:
            self.first = node
            self.first.next = node
            self.last = node
        else:
            self.last.next = node
            self.last = node
        self.size += 1

score 1 · Answer 2 · edited Oct 01 '14 at 12:19

I think that something like the following method would work:

class LinkedList:
    # what you have so far

    def add_to_front(self, elem):
        if self.size == 0:
            self.add(elem)
        else:
            node = Node(elem, self.first)
            self.first = node
            self.size += 1

You currently have a reference to the head of the list in self.first and a reference to the current tail in self.linkedlist. That allows efficient additions at either point.

ll = LinkedList()
for i in xrange(3):
    ll.add_to_front(i)

>>> ll.linkedlist
Node(elem=0, next=None)
>>> ll.first
Node(elem=2, next=Node(elem=1, next=Node(elem=0, next=None)))
>>> ll.add('x')
>>> ll.linkedlist
Node(elem=x, next=None)
>>> ll.first
Node(elem=2, next=Node(elem=1, next=Node(elem=0, next=Node(elem=x, next=None))))
>>>

score 0 · Answer 3 · answered Oct 01 '14 at 12:04

Try this(I've changed the add method only. This doesn't involve the linkedlist class member.) -

class LinkedList:
    def __init__(self):
        self.size=0
        self.first=None

    def add(self,elem):
        if self.size == 0:
            self.first = Node(elem)
        else:
            self.first = Node(elem, self.first)
        self.size += 1

add elements to the end of an linked list

3 Answers3