Literally Loving Linked Lists LOL
In this project, your team will implement a sentineled doubly-linked list. Recall that
a linked list is composed of Node objects that are linked together. This means that
we will need to create two classes in this implementation. One class will represent
the Nodes of data and how they are linked together. The other class will represent
the actual Linked List, defining methods for adding and removing elements, creating
a string representation of the object, and obtaining its length.
We have discussed a variety of methods for inserting and removing values in a linked
list. This project will use index-based addressing. Recall from our studies of arrays
that index zero identifies the location of the first datum. This approach also means
that the maximum valid index is one less than the length of the sequence. We will
replicate that indexing paradigm here. Note that index zero identifies the first Node
object that contains data, and not the header. Neither the header nor the trailer has
Your implementation should support the following methods, keeping in mind that the
words index, head, and tail are used descriptively only and should not appear as
attributes of either class:
append_element(self, val) This method should increase the size of the
list by one, adding the specified value in the new tail position. This is
the only way to add a value as the tail.
insert_element_at(self, val, index) If the provided index identifies a
valid zero-based position within the list, then insert the specified value
at that position, increasing the length by one. This method can be used
to insert at the head of a non-empty list, but cannot append to a list.
The provided index must be within the current bounds of the list. If the
index is not valid, raise an IndexError exception.
remove_element_at(self, index) If the provided index identifies a valid
zero-based position within the list, then remove and return the value
stored in a Node at that position. If the index is not valid, raise an
get_element_at(self, index) If the provided index identifies a valid
zero-based position within the list, then obtain the value from the Node
at that position and return it. Do not unlink the Node object. If the index
is not valid, raise an IndexError exception.
rotate_left(self) Without constructing any new node objects and
without returning anything, rotate the list left so that each node moves
one position earlier than it was and the original head becomes the new
tail. The length of the list should not change. If the list is empty, this
method has no effect.
__len__(self) Return the number of values currently stored in the list.
__str__(self) Return a string representation of the values currently
stored in the list. An empty list should appear as [ ] (note the single
space). A list with one integer object should appear as [ 5 ] (note the
spaces inside the brackets). A list with two integer objects should appear
as [ 5, 7 ], and so on. Pay close attention to the format of this string,
and remember that strings can be concatenated with the + operator. To
convert other objects to strings, use str(other_object). As long as the
class for the other object implements the __str__() method, this
approach will work.
__iter__(self) See "Iterators" below.
__next__(self) See "Iterators" below.
In lecture, we have silently ignored bad method calls (such as requesting the value
of an index that is equal to or greater than the length of the list) by detecting that
condition at the beginning of the method and returning. In practice, it is better to
inform the programmer that her request was invalid, and allow her to handle the
problem. The mechanisms for achieving this are called exceptions and try blocks.
When you detect an error condition, instead of returning, raise the appropriate
exception using the syntax
When the programmer calls a method that could potentially generate an exception,
she does so in what we call a try block. Suppose she calls a method that could raise
a ValueError. Her code to invoke that method would have to look like this:
my_object = Awesome_Class()
asplode = random.randint(1,10)
print("whew... made it.")
print("on the other side.")
Perhaps the dangerous_call(num) method raises a ValueError if the value of num is 5,
and raises no exception otherwise. Because asplode is equally likely to be one of ten
values (one through ten, inclusive) in the example above, she will get with 90%
whew... made it.
on the other side.
or with 10% probability (when asplode is the one of ten possible values, the value
5, that is problematic)
on the other side.
Each method in your Linked List class that takes an index as a parameter should raise
an IndexError (this type is built-in to Python) if the provided index is out of bounds.
For our implementation, indices that are either too large or negative should be
A common mistake when implementing exceptions is where to place the try/except
sequence. If a method is dangerous, it should only raise an exception. The location
in the code that called the dangerous method should have done so in a try block so
that it can catch any exception that the method raises. Do not include a try/except
sequence in the method itself.
One thing that we have mentioned briefly during lecture that is relevant to this project
is the concept of inner classes. We already know that the Linked List implementation
will employ objects of a Node class, so these two classes will be working together.
An important point, though, is that the end user of the Linked List doesn't actually
see Nodes. Think back to arrays for a moment; when you use an array, you don't
actually see the cells that store the data. You see and interact with the data
themselves. The same will be true for Linked Lists. The person using your list
implementation doesn't actually care about Nodes. All she cares about is that her
data are stored in the list. Because of this, it is not necessary (or even desirable) for
the Node class to be exposed to the world. It should only be used internally by the
Linked List implementation methods. When a user inserts data into the list, she
provides the data as an object of whatever type she is storing. If she is dealing with
integers, she will insert the number 5, not a Node containing the number 5. The use
of a Node object to encapsulate the value 5 is completely internal to the Linked List
and is never exposed.
To help provide this encapsulation, your solution should implement the Node class
itself as a private member of the Linked List class. By marking the class private (with
two leading underscores) and implementing it inside of the Linked List class, we
indicate that it should only be used internally to Linked Lists. The concept is similar
to private attributes, but instead of being declared as self.__attr_name inside of the
constructor, the inner class is defined at the same level as the methods. This means
that even if the Node attributes are public (and they must be because of how Python
implements privacy), only the Linked List methods can reach them. This is a desirable
Using the method get_element_at(index), we could visit every node in the list by
looping through all of the valid indices. The problem with that approach is that instead
of linear time performance, we have quadratic time. Notice that the
get_element_at(index) method is linear. It must do a current-walk to reach position
index, which is at the tail position in the worst case. Retrieving the first element will
take 1 step; retrieving the second element will take 2 steps. You should recognize
this pattern from our analysis of insertion sort. The sum of 𝑛 consecutive integers
beginning at 1 is bounded by 𝑛
. Considering how frequently we use loops to visit
every value in a sequence, quadratic performance is not desirable.
To keep the time linear as expected, we employ a programming structure called an
iterator. You have used iterators many times. Consider the following code segment:
arr = [5,2,-4,1]
for val in arr:
The loop iterates through the values in the array. When Python encounters the loop,
it initializes an index for the array. On every entrance of the loop, it assigns val the
value contained at that index, then increments the index. When the index reaches
the length of the array, the iteration terminates.
You can replicate this behavior for any class you write by implementing two special
methods: __iter__(self) and __next__(self). Analogous to the code segment above
is the following version that uses a linked list object instead of an array:
ll = Linked_List()
for val in ll:
Right before the for loop, the object ll should contain the elements 5, 2, -4, and 1.
When Python encounters the for loop, it invokes the __iter__() method on the ll
object (after the keyword in). This is Python’s way of telling the ll object to prepare
to cycle through its elements. In your __iter__() method, you should initialize a
current pointer in preparation for walking the list. Each time Python enters the
indented for block, it assigns val whatever is returned by a hidden call to __next__().
In your __next__() method, you should decide whether there is another value to
return. If so, advance to the node whose value should be returned and return that
value. If not, raise a StopIteration exeption. Python will automatically handle the
exception as a signal to stop calling your __next__() method. This terminates the for
Below is the skeleton implementation that you will complete. The Python file attached
to this assignment contains comments describing each method.
def __init__(self, val):
def append_element(self, val):
def insert_element_at(self, val, index):
def remove_element_at(self, index):
def get_element_at(self, index):
if __name__ == '__main__':
Most importantly, notice that the Node class is defined within the Linked List class
and is private to that class. This means that only the methods inside of the Linked
List implementation have access to Nodes; they are not exposed to the user. It also
means that to create a new node inside of an insert method, the syntax is
new_node = Linked_List.__Node(my_val)
Then, new_node is a Node object that can be linked in at the appropriate location.
Because the Node class is implemented as a member of the Linked List class, it is
accessible to the methods inside of the Linked List implementation. The attributes of
the Node class should be public; python does not support transitivity of privacy in
inner classes (though other languages do). This means that the Node class does not
require any methods other than its constructor.
In the main section of your Python file, provide some test cases to ensure that your
Linked List implementation functions correctly. Though this is not an exhaustive list,
some things to consider are:
• Does appending to the list add an element at the new tail position and
increment the size by one?
• Does inserting an item at a valid index increase the size by one and correctly
modify the list's structure?
• Does inserting an item at an invalid index leave the list completely
• Does removing an item at a valid index decrease the size by one and
correctly modify the list's structure?
• Does removing an item at an invalid index leave the list completely
• Does length always return the number of values stored in the list (not
including sentinel nodes)?
• Is the string representation of your list correct for a variety of lengths?
• Does a for loop like
for val in my_list
visit every value?
An Application of LL: The Josephus Problem
The story is slightly bloody. During the Jewish-Roman war, Josephus was among a
band of 41 Jewish rebels trapped in a cave by the Romans. Preferring suicide to
capture, the rebels decided to form a circle and, proceeding around it, to kill every
third remaining person until no one was left. But Josephus, along with a friend,
wanted none of this suicide nonsense; he quickly calculated where he and his friend
should stand in the vicious circle. The end of the story is that both Josephus and his
friend lived and Josephus later became a famous historian.
In our variation, we start with n people numbered 1 to n around a circle, and we
eliminate every second remaining person until only one survives. The problem is to
determine the survivor’s number. We first try a small example. Let n = 10. Then the
elimination order is 2, 4, 6, 8, 10, 3, 7, 1, 9, so 5 survives.
How to solve the problem? You may pause here and think about the possible
algorithm and data structure by yourself. Well, you may have some idea that seems
“not so easy,” and you may realize you could use either arrays or linked lists as the
data structure. Here, we provide you one efficient algorithm to solve the problem
using the linked list class that you implemented. The algorithm is smart and simple:
rotate the list to the left by one position circularly, and then delete the first
element; repeat it until there is only one element left in the list. Make sure
you understand why.
Once you have your Linked_List class implemented, use it to solve the Josephus
problem, for which we have provided a skeleton file. In the main function of this
implementation, fill in the #TODO section by creating a doubly linked list object called
ll (2 Ls) with n elements named 1 to n. Then call the function Josephus() by passing
the ll. In the function Josephus(), fill in the #TODO section by using the algorithm
described above. Print the sequence of survivors after each death. Finally print the
Below is a run of the code for n = 21 rebels. The sequence of survivors is shown after
each death, but rotated a bit. Your implementation should give the output in
the same format. Discuss about this algorithm's performance in your writeup.
Input the total number of people: 21
Initial order: [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 ]
[ 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 1 ]
[ 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 1, 3 ]
[ 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 1, 3, 5 ]
[ 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 1, 3, 5, 7 ]
[ 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 1, 3, 5, 7, 9 ]
[ 13, 14, 15, 16, 17, 18, 19, 20, 21, 1, 3, 5, 7, 9, 11 ]
[ 15, 16, 17, 18, 19, 20, 21, 1, 3, 5, 7, 9, 11, 13 ]
[ 17, 18, 19, 20, 21, 1, 3, 5, 7, 9, 11, 13, 15 ]
[ 19, 20, 21, 1, 3, 5, 7, 9, 11, 13, 15, 17 ]
[ 21, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ]
[ 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 ]
[ 7, 9, 11, 13, 15, 17, 19, 21, 3 ]
[ 11, 13, 15, 17, 19, 21, 3, 7 ]
[ 15, 17, 19, 21, 3, 7, 11 ]
[ 19, 21, 3, 7, 11, 15 ]
[ 3, 7, 11, 15, 19 ]
[ 11, 15, 19, 3 ]
[ 19, 3, 11 ]
[ 11, 19 ]
[ 11 ]
The survivor is: 11
1. Linked_List.py: A file containing your completed Linked List class
implementation. Though you are free to add additional methods as you deem
necessary, you must not change the names (including spelling) or parameter
lists of any methods in the skeleton file. The main section at the bottom of this
file must contain your testing code.
2. Josephus.py: Your implementation of the Josephus problem that imports
and uses your Linked_List class. Your implementation must use only the
public methods defined in the Linked_List specification.
3. Writeup.pdf: A prose document that details why you performed the test cases
that you did and explains why those tests are complete. You must also describe
the performance characteristics of each of the methods append_element(...),
insert_element_at(...), remove_element_at(...), and get_element_at(...).