- Due before 23:59 Wednesday, September 7
- Submit using the submit program
301 lab 02.
One data structure that we're going to talk about a lot is a Linked List. A Linked List is a pretty simple thing, and can be good practice of Object-Oriented Programming.
Linked Lists are essentially alternatives to arrays. Like with an array, each piece of data has a spot, and each spot has a single piece of data. It's built in a pretty different way, though.
Linked Lists are built from a series of Nodes, where a Node holds two
things: (1) a single piece of data, and (2) a pointer to the next Node in the
list. Below, for example, is a drawing of a linked list containing the
integers 1, 3, and 5. Each rectangle is a Node, and each arrow is a pointer
to the next Node. The value of the pointer in the Node containing 5 is
None (Python's equivalent of a null pointer), because there's no
more nodes for it to point to.
The first Node in the Linked List is commonly referred to as the "head," while the last is referred to as the "tail."
To build a Linked List, you're going to make two classes, Node and
LinkedList, both of which are in a the file
Node class will have two fields, one constructor (i.e., the
and no additional
methods. Your fields will be:
data: For holding the integer within the Node
nextNode: For holding the pointer to the next Node
Your constructor will take as an argument the data value, and should set that
field accordingly. The
nextNode field should be initially set to
This class will have two fields, one constructor, and five methods. Your fields will be:
head: For pointing to the first
Nodein the list (the one containing 1 in our example)
tail: For pointing to the last
Nodein the list (the one containing 5 in our example)
Your constructor should take no arguments (aside from
should set head and tail to
None, indicating this new LinkedList is empty, and
therefore has no head or tail Nodes.
Finally, you'll have five methods which alter your LinkedList, or find some information about it:
__str__(self): return all the data elements within the Linked List, separated by spaces. On our example, calling this on the example above should return the string
"1 3 5".
add_front(self,data): The data input as an argument should be put inside a new Node, which is then stuck on the front of the Linked List as the new head. In our example, calling
myLL.add_front(4)should result in this:
add_back(self,data): The data input as an argument should be put inside a new Node, which is then stuck on the back of the Linked List as the new tail. In our example, calling
myLL.add_back(4)should result in this:
contains(self, data): Calling
Trueif someNumber is contained within a Node somewhere in this LinkedList, and
Falseif it is not.
add_ordered(self, data): For this method, you may assume the elements of your Linked List are already in increasing order. This method takes
dataand adds it in the appropriate place. For example, if your LL has 1,3,5, and you call
myLL.add_ordered(4), it ends up as 1,3,4,5.
size(self): This should return the number of Nodes in your list. There are actually two ways to do this! One way is, you write a loop within your
sizemethod to walk through the nodes until hitting
None, and return the count. The other way is to store another field within your class that gets updated every time something is added.
Which way you do it is up to you! Whatever you decide, I hope you think about the advantages/disadvantages of each option. Try to think beyond "which way is easier for me to program". These are the kind of questions we have to think about in this class - which is the best way out of the many possible correct ways to write our programs.
When using OOP, you'll find it's most effective to build these things up in small pieces, testing as you go. In this case, LinkedList can't do much unless you have Node written, so start there. Build a Node class, and then write some code to test it. For example, here's some testing code for the Node class:
1 2 3 4 5 6 7 8 9 10 11
from linkedlist import Node if __name__ == "__main__": node1=Node(3) node2=Node(4) print(node1.data) #should print 3 print(node2.data) #should print 4 node1.data=5 print(node1.data) #should print 5 node1.nextNode=node2 print(node1.nextNode.data) #should print 4, see why?
Once you're confident in your Node class, you can work on your LinkedList class, assuming that if anything breaks, it's in LinkedList, and not Node. It is tempting to shoot in the dark, program your whole program, and then debug. However, I've written very, very few programs that work on their first try. If you test your methods as you go, then you keep it so any errors that come up, can only be in the most recently written few lines. This makes your life much, much easier.
When you submit your program or run the
some "unit tests" will be executed to test your program on some simple
examples like what's in the lab description here. If you want to understand
exactly what is being tested, the name of that unit test program is also
printed to the screen, so you can actually look at that file and figure it out!
Keep in mind that when I grade this, I'll run many more, harder test cases so we can really put your code to the test. I'm not going to give you this code beforehand. It is your responsibility to adequately test your code.
The rest of this lab is optional for your enrichment and enjoyment. Be sure to work on this only after getting everything else perfect. You should still submit this work, but make sure it doesn't break any of the parts you already had working correctly!
Try your hand at the following additional (and very useful) functions:
remove_all(self, data): Removes any Nodes in the list that contain the given data. (If there aren't any, then nothing changes.)
reverse(self): Changes the list to run in reverse order. So for example if it's initially 1,3,5, then it would change to 5,3,1.
Note: this would be kind of easy to do using one of Python's built-in lists temporarily, but try to see if you could do it just by using the Nodes.
sort(self): Changes the list to be in sorted order from least to greatest. I know you learned about some sorting algorithms already - which ones will work well for linked lists, and which ones won't, is something you'll have to try and figure out!