1 Linked Lists

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."

2 The Assignment

To build a Linked List, you're going to make two classes, Node and LinkedList, both of which are in a the file linkedlist.py.

Node

Your Node class will have two fields, one constructor (i.e., the __init__ method), 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 None.

LinkedList

This class will have two fields, one constructor, and five methods. Your fields will be:

• head: For pointing to the first Node in the list (the one containing 1 in our example)
• tail: For pointing to the last Node in the list (the one containing 5 in our example)

Your constructor should take no arguments (aside from self), and 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 myLL.contains(someNumber) should return True if someNumber is contained within a Node somewhere in this LinkedList, and False if 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 data and 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 size method 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.

3 Your Approach

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 301sanity script, 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.

4 Going farther

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!