13
\$\begingroup\$

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()
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Alexander Sep 13 '17 at 23:54
15
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ "Add a data parameter to the insert method,", in fact, the code already takes a data parameter, it just immediately overwrites it with input(...) \$\endgroup\$ – mbrig Sep 13 '17 at 21:33
  • \$\begingroup\$ @mbrig Whoops. Fixed. \$\endgroup\$ – Carcigenicate Sep 13 '17 at 21:36
  • \$\begingroup\$ Good points, but your method using n_nodes won't work, because n_nodes is not an attribute of LinkedList. \$\endgroup\$ – Piotr Koller Sep 14 '17 at 12:03
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Carcigenicate Sep 14 '17 at 13:15
14
\$\begingroup\$

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
  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):
        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
  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):
        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
\$\endgroup\$
  • \$\begingroup\$ "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. \$\endgroup\$ – user2357112 supports Monica Sep 13 '17 at 21:49
  • \$\begingroup\$ Very good point. Will edit to reflect this. \$\endgroup\$ – act Sep 13 '17 at 21:50
  • \$\begingroup\$ Better, but your items() method is skipping an element, and it should just be __iter__ instead of items. \$\endgroup\$ – user2357112 supports Monica Sep 13 '17 at 22:16
  • \$\begingroup\$ Good catch. I've updated the answer accordingly. \$\endgroup\$ – act Sep 13 '17 at 22:25
11
\$\begingroup\$

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

\$\endgroup\$
6
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Brian McCutchon Sep 14 '17 at 6:55
  • \$\begingroup\$ @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. \$\endgroup\$ – starchild Sep 14 '17 at 21:00
2
\$\begingroup\$

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))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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