Today, we will extend the capabilities of the our existing linked list class. Thus far, you have simply been able to remove elements from one of the two ends of the list. Today, you will implement code that can remove an arbitrary element from the list.
To remove an element from the front of the list, you simply moved the head reference. This way, when you printed the list, you would skip over that front element. Removing an arbitrary node is very similar. Consider the following list:
Assume we wanted to remove the node containing the data "4" from said list. We simply want to make any node that "points" to that node to point around that node:
In order to accomplish this, we first need to find the node that "points" to the node who contains the data that we are trying to remove. You can simply perform a linear search through the list, until the data in the next node is the element to be removed. Finally, you can set that found nodes next reference to the node following the node being removed.
Define a method in your linked list class
called remove(self, element). remove
should take as a parameter the data in the node to be
removed. If element is not contained within the list, remove should
raise a ValueError. Otherwise, you should remove the
correct node from the list, and decrement the size counter.
Make sure you thoroughly test your remove method. Can you
successfully remove the first or last elements
using remove? What happens if you try to remove
something from an empty list? Your code should gracefully handle
all of these scenarios.
Right now, your linked list is largely complete. However, traversing the list is a bit of a pain. You create a variable called current, and continually move the current pointer to until it reaches to the end of the list. Wouldn't it be nice if you could do something more akin to this:
linked_list = LinkedList()
...
for i in linked_list:
print(i)
Luckily, you can. And it is not too difficult.
In order to use the above for loop syntax, your class needs to
create an iterator. An iterator is a special object that allows for
the traversal of some specified container, such as a linked list.
In Python, anything that overrides the __next__ method
are considered iterators.
The __iter__ returns some object which contains an
implementation of the __next__ method.
This __next__ continually returns the next item in the
container, until there are no more items to return. It then raises
a StopIteration exception, which is handled internally
in python.
In your linked list class, define a private internal class
called _Iterator. The constructor for this class
should take a reference to the linked list to iterate over, and
declare any attributes necessary to traverse the linked list. You
should define a method called __next__ within this
class. Each call to this method should return the next data from
the linked list.
Define a method in your LinkedList class
called __iter__, which simply constructs an instance of
your private _Iterator class, and returns it. At this
point, you should be able to iterate over the list using the above syntax.
For the purposes of this lab, you do not have to worry about some more complex issues related to iterators. One that you may run into as you use this iterator, is that if you remove items from the list, they may still exist as far as the iterator is concerned. Bonus points will be provided for any iterator implementations that solve this issue in particular.
Eratosthenes was a Greek mathematician and astronomer from the 2nd century B.C.E. He is widely known as being the one of the first humans to estimate the circumference of the Earth, with an error of less that 2%. Another contribution of Eratosthenes is the Sieve of Eratosthenes, a mechanism for computing a list of primes up to a specified number.
The algorithm for generating such a list of primes is fairly
straight forward. Consider a list of numbers numbers
in the range [2,n].
The first item in the list is always the next prime p.
p should be removed, and stored in the current list of
known primes. Then, every multiple of p should be
removed from the list numbers.
Using your LinkedList, you can implement this algorithm to get a
list of primes up to n. First, populate the numbers
list with all of the numbers from 2 until n. Also, create an empty
list called primes. Remove the first
element, and put it in the primes list. Then, remove all of the
multiples of n in the list numbers. You can continue
to remove a prime and its multiples, until there are no more elements in
the numbers list to remove.
After this algorithm is complete, the list primes
contains all of the prime numbers up to n. This list can be used to
compute the prime factorization of numbers up to n. The faster that
such a list can be generated, the faster numbers can be factored.
Time the Eratosthenes algorithm. What does its Big-O class look
like? Compare this algorithm to the old, brute-force algorithm we
discussed way back in week 1. Is this one faster?
Submit a zip file of your code on the course Inquire site that uses your last names as the file name.