Now that we have a working LinkedList class, what are some of the
pros and cons of linked lists vs python lists?
Remember, here is a picture of how each is stored/implemented in the computer's memory:
To add an item to the end of a python list, we need to find the correct spot in memory (python does this for us). Since this is just a simple calculation (base address + len(L)), appending to a python list is an O(1) operation. That is, it doesn't matter how long the list is (assuming there is available free memory at the end of the list).
The same is true for a linked list: adding a node to the end of the list is O(1), since it doesn't depend on the size of the list. There are only a few steps required: create new node, connect it to the tail, reset the tail, increment the size.
So for appending to the list, both are the same.
To add an item to the beginning of a python list, if we want to preserve the current base address, requires moving all other items in the list over by one slot. This clearly depends on the size of the list, making it an O(N) operation.
You can see this by running some simple tests using append(item) and insert(0,item):
$ cat testpythonlists.py
"""
test/time various python list operations
"""
from time import time
# ------------------------------------------------ #
def main():
N = int(raw_input("N: "))
L = []
t1 = time()
for i in range(N):
L.append(i)
t2 = time()
total = t2 - t1
print("append time: %6.3f (for L of size %d)" % (total, len(L)))
L = []
t1 = time()
for i in range(N):
L.insert(0, i)
t2 = time()
total = t2 - t1
print("insert@0 time: %6.3f (for L of size %d)" % (total, len(L)))
# ------------------------------------------------ #
main()
Here's a simple run of the above program. Notice the difference between adding to the end and adding to the beginning of a python list:
$ python testpythonlists.py
N: 100000
append time: 0.015 (for L of size 100000)
insert@0 time: 2.573 (for L of size 100000)
$ python testpythonlists.py
N: 200000
append time: 0.021 (for L of size 200000)
insert@0 time: 10.259 (for L of size 200000)
For the linked list, again, just a few steps needed to add a node to the beginning of a list: create node, connect it to the current head, reset the head, increase the size. This is clearly an O(1) operation, so the linked list does better here.
How about for indexing, or finding the ith item in a list? For the python list, that is an O(1) operation, since it is just a simple calculation to find the correct memory location (base address + i). For the linked list, to get to the ith node, we need to start at the head of the list and move over i times. This is an O(N) operation, so the python list does better at indexing (which we've used a lot this semester!).
See if you can figure out whether each method we have written (e.g., deleteHead(),
__str__(), deleteTail(), etc) is O(1), O(N), or something else. And compare
that to the python list.