LinkedList
classLast time we wrote a Node
class to be used to create our linked lists.
A Node
is just a "container" to hold two things: the item or data we want
stored in the list, plus a next
"pointer" to point to the next node in the list.
Here is an example of how we could manually create nodes and link them together:
>>> from node import *
>>> n1 = Node("jeff")
>>> n2 = Node("zach")
>>> n3 = Node("lauri")
>>>
>>> print(n1)
(jeff)--|
>>>
>>> n1.setNext(n2)
>>> n2.setNext(n3)
>>>
>>> print(n1)
(jeff)-->
>>> print(n2)
(zach)-->
>>> print(n3)
(lauri)--|
Instead of doing this manually, we could create a LinkedList
class to allow
us to create linked lists just like python lists. Here is what I would like
to be able to do:
>>> from linkedlist import *
>>> LL = LinkedList()
>>> LL.append("jeff")
>>> LL.append("zach")
>>> LL.append("lauri")
>>> print(LL)
head-->(jeff)(zach)(lauri)<--tail
Each linked list should have three instance variables: self.head
, self.tail
, and self.size
.
All methods we write should make sure all three are updated accordingly. For example, when appending
to the list, the self.tail
pointer should be adjusted, as well as the size of the list. And if
it is the first node being added/appended to the list, then the self.head
pointer will also
need to be set (i.e., if there is just one node in the list, both the head and the tail should
point to that one node).
For the constructor, we want to build an empty linked list object, so self.head
and
self.tail
don't point to anything, and the size is zero. We use python's None
type
when things don't point to anything:
def __init__(self):
"""construct an empty linked list"""
self.head = None
self.tail = None
self.size = 0
append
methodTo append a new node, we need to create the node with the given item stored in the node, and then add it to the end of the list. That means connecting the current tail of the list to the newly-created node, then resetting the tail to be the newly-created node. Something like this:
n = Node(item)
self.tail.setNext(n) # connect to end
self.tail = n # reset tail pointer
self.size += 1
However, this only works if there are already nodes in the list. If this is the
first node in the list, we have to account for that (set the head to point to
this node, and don't connect the current tail). Here is the final version of
our append()
method:
def append(self, item):
"""add new node, containing item, to end of the list"""
n = Node(item)
if self.size == 0:
self.head = n
else:
self.tail.setNext(n)
self.tail = n
self.size += 1
prepend
methodCan you create a similar method called prepend
, to add nodes to the beginning
of the list?
str
methodIt would be nice to be able to print the list, to make sure it is set up correctly. Something like the above example would be useful:
head-->(jeff)(zach)(lauri)<--tail
However, to get each item stored in the list, we need to access each node in the list. This is typically done with a loop to visit each node in the list (i.e., list traversal). Here is how you could manually set a pointer to the first node in the list, get the item stored there, and then move the pointer over to the next node in the list:
s = "head-->"
curr = self.head
s += "(%s)" % str(curr.getItem())
curr = curr.getNext()
Note the curr = curr.getNext()
...this moves the pointer from one node to the next.
Putting this in a loop, we can visit each node in the list and create/accumulate a
string-representation of the list:
def __str__(self):
"""return string representation of linked list"""
s = "head-->"
curr = self.head
for i in range(self.size):
s += "(%s)" % str(curr.getItem())
curr = curr.getNext()
s+="<--tail"
return s
Note: if the list is empty, the for
loop never executes, so all we get is
"head--><--tail", which shows an empty list.
If you want you can change the str
method to use square brackets and commas
between items, so the linked list prints exactly like the python list.
len()
methodAdding a getter for self.size
could be useful. Calling it __len__()
allows you to use len(LL)
, just like we've done with python lists.
Once you have the above methods written, add some test code to make sure everything works. Try to test all possible cases. Thoroughly testing now will help eliminate bugs that can cause lots of headaches later!!
Use the assert
statement to add as many tests as you can think of.
# test init,str,append,len
LL = LinkedList()
assert len(LL) == 0
assert str(LL) == "head--><--tail"
LL.append("A")
LL.append("B")
LL.append("C")
assert len(LL) == 3
assert str(LL) == "head-->(A)(B)(C)<--tail"