# Linked list in Python which gets values from keyboard

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

def __init__(self):

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

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

def size(self):
i=0
i+=1
print (i)

while True:
print("2. Print the list")
print("3. Size of the list")

MyList.insert(1)
MyList.print()
MyList.size()

• Why is it the job of a linked list to read from STDIN? What if I want to initialize such a linked list from a generator function, list comprehension or as a copy of a list's contents? I would split this into a separate LinkedList and LinkedListSTDINPopulator – Alexander Sep 13 '17 at 23:54

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):
node = Node()
node.data = data
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:

...
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.

• "Add a data parameter to the insert method,", in fact, the code already takes a data parameter, it just immediately overwrites it with input(...) – mbrig Sep 13 '17 at 21:33
• @mbrig Whoops. Fixed. – Carcigenicate Sep 13 '17 at 21:36
• Good points, but your method using n_nodes won't work, because n_nodes is not an attribute of LinkedList. – Piotr Koller Sep 14 '17 at 12:03
• @P-box I said "give your list an n_nodes (or similar) field". I didn't want to bloat the code up just to show adding it. – Carcigenicate Sep 14 '17 at 13:15

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

1. 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):
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

1. 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):
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

• "Turn it into an iterator" - what? No! A list should be able to produce iterators on demand, but it shouldn't be its own iterator. If you make it its own iterator, you can't do things like have two nested loops over the same list, and you run into all sorts of other nasty statefulness bugs. – user2357112 supports Monica Sep 13 '17 at 21:49
• Very good point. Will edit to reflect this. – act Sep 13 '17 at 21:50
• Better, but your items() method is skipping an element, and it should just be __iter__ instead of items. – user2357112 supports Monica Sep 13 '17 at 22:16
• Good catch. I've updated the answer accordingly. – act Sep 13 '17 at 22:25

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):
str_list = []
while current:
str_list.append(str(current.data))
current = current.next
return "[" + ','.join(str_list) + "]"

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

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):

• I would even remove the default None from data. Assuming that Node is only used from LinkedList (it should be), data will always be passed whatever is passed to insert. I suppose next would be None for the last node in the list. – Brian McCutchon Sep 14 '17 at 6:55
• @BrianMcCutchon I considered it, and honestly I'd remove the default on data too, but I think it's subtle enough that it isn't obviously correct one way or the other. Making both the new parameters optional also has the benefit of being obviously "safe" in that it won't break existing usage - which is worth considering when refactoring code without tests. – starchild Sep 14 '17 at 21:00

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

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

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

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

def __repr__(self):

def __iter__(self):
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__':

while True: