Linked list in Python which gets values from keyboard

Question

What do you think about my implementation of linked list, which gets values from keyboard? I implemented three basic functions: print, insert and size.

class Node:

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

class LinkedList:

       def __init__(self):
               self.head = None

       def insert(self,data):
               data = input("Add an element:")
               node = Node()
               node.data = data
               node.next = self.head
               self.head = node

       def print(self):
               print_list = self.head
               while print_list:
                       print(print_list.data)
                       print_list = print_list.next

       def size(self):
               i=0
               head = self.head
               while head:
                      i+=1
                      head = head.next
               print (i)


  MyList = LinkedList()

  while True:
       print("1. Add an element")
       print("2. Print the list")
       print("3. Size of the list")
       menu = int(input("Choose an action:"))

       if menu == 1:
               MyList.insert(1)
       elif menu == 2:
               MyList.print()
       elif menu == 3:
               MyList.size()

Answer 1

I don't see anything glaring, except for the size method. It has 2 major flaws:

• Every time you want to check the size, you must traverse the entire list, giving it a time complexity of O(n) (linear). This would likely be an unacceptable complexity for real world use. I'd expect that a size method would be O(1), meaning the length of time the operation takes has nothing to do with the number of elements in the list. What if your list contained a million elements and you needed to repeatedly get the size of it?

• It prints the size instead of returning it. Rarely should a method print its result; unless that's the sole purpose of the method. Return the result instead of printing it directly so the returned size can actually be used instead of just seen. If you want to print the data, print the return of the function instead. Let the caller of the function decide how the data is used instead of forcing it to be printed.

How can these points be fixed? Instead of calculating the size, give your list an n_nodes (or similar) field, and increment it inside of insert:

def insert(self,data):
    data = input("Add an element:")
    node = Node()
    node.data = data
    node.next = self.head
    self.head = node
    self.n_nodes += 1 # Here

Then just change your size method to return n_nodes. Notice that the number of elements in the list has no effect on the time this method will take to finish:

def size(self):
    return self.n_nodes

Then just print the size at the call site:

...
elif menu == 3:
    print(MyList.size())

Now that I've looked over your insert method though, it suffers from a similar problem: needless use of side-effects. Why ask for the data inside the method via input instead of passing the data in? What if you want to insert data that came from the internet, or from the disk?

Use the data parameter of the insert method to pass the data in, and get rid of the call to input. The data can still come from input, just ask for it outside of the method.

Answer 2

In addition to other answers:

1. Add a __len__ method (or use .__len__(self) instead of .size(self)): by convention, .__len__(self) is used to calculate the 'size' of an object. Using __len__ also has the benefit that users of your class can call len() on a linked list instance, in the same way as they would any other sequence.

   def __len__(self):
       return self.size()
   

Now we can do:

    l = LinkedList()
    l.insert(1)
    assert len(l) == 1

2. Make it iterable by having __iter__ return a generator: by returning a generator that yields consecutive node elements, users can traverse the list of nodes (see below example)

   def __iter__(self):
       node = self.head
       while node:
           yield node.data
           node = node.next
   

Now we can do:

    l = LinkedList()
    l.insert(1)
    l.insert(2)

    for i in l:
        print(i)

    # Outputs:
    # >> 2
    # >> 1

3. A nice addition might be a pop method that simultaneously returns the head of the linked list, and removes it from the list.

   def pop(self):
       data = self.head.data
       self.head = self.head.next
       return data
   

Now we can do:

    l = LinkedList()
    l.insert(1)
    l.insert(2)

    first = l.pop()
    second = l.pop()
    assert len(l) == 0

    print('List was: {}, {}'.format(first, second))

    # Outputs:
    # >> List was 2, 1

Answer 3

Instead of implementing a print method, I would override the __str__() method, and then the caller can do whatever they wanted with the string representation of your list.

def __str__(self):
    current = self.head
    str_list = []
    while current:
        str_list.append(str(current.data))
        current = current.next
    return "[" + ','.join(str_list) + "]"

my_list = LinkedList()
my_list.insert(1)
my_list.insert(3)
my_list.insert(4)
my_list.insert(2)

print(my_list)
# output: [2,4,3,1]

It would be quite unusual (and not very useful) for an object to have a method to print itself only. Returning a string allows much more flexibility.

you should also stick to PEP8 naming conventions where possible, MyList should be my_list. Class names should be UpperCamelCase (as you have now) and variable and function names should be in snake_case

Answer 4

In addition to the suggestions in other answers, consider adding optional parameters to Node's __init__:

class Node:

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

Then insert simplifies to:

def insert(self, data):
    self.head = Node(data, self.head)

Answer 5

Added __repr__, __iter__, renamed insert to append. Moved user interaction out of class.

class Node:
    def __init__(self):
        self.data = None
        self.next = None

class LinkedList:

    def __init__(self):
        self.size = 0
        self.head = None
        self.tail = None

    def append(self, data):
        node = Node()
        node.data = data
        if not self.head:
            self.head = node
            self.tail = node
            self.size = 1
            return
        self.tail.next = node
        self.tail = node
        self.size += 1

    def __repr__(self):
        return 'LinkedList(%s)' % str(self)

    def __iter__(self):
        current = self.head
        while current:
            yield current.data
            current = current.next

    def __str__(self):
        return '[%s]' % ', '.join([x for x in self])

    def __len__(self):
        return self.size


if __name__ == '__main__':
    lst = LinkedList()

    while True:
        print("1. Add an element")
        print("2. Print the list")
        print("3. Size of the list")
        menu = int(input("Choose an action:"))

        if menu == 1:
            data = input("Add an element:")
            lst.append(data)
        elif menu == 2:
            print(lst)
        elif menu == 3:
            print(len(lst))