The Self-Taught Computer Scientist

Chapter 10 Linked Lists
105
Next, you define a class to represent your linked list, with an instance variable called 
head
that 
holds your list’s head:
class LinkedList:
def __init__(self):
self.head = None
Inside your 
LinkedList
class, you create an append method that adds a new node to your list:
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
if not self.head:
self.head = Node(data)
return
current = self.head
while current.next:
current = current.next
current.next = Node(data)
Your method 
append
accepts a piece of data as a parameter, creates a new node with it, and adds it 
to your linked list.
If your list doesn’t have a head yet, you create a new node, and it becomes the head of your 
linked list:
if not self.head:
self.head = Node(data)
return
Otherwise, if your list already has a head, you find the last node in your linked list, create a new 
node, and set its instance variable 
next to it. To accomplish this, you create a variable called 
current
and assign it to your list’s head:
current = self.head
Then you use a 
while
loop that continues as long as 
current.next
is not 
None
because you know 
you are at the end of your linked list when it is:
while current.next:
Inside your 
while
loop, you continually assign 
current
to 
current.next
until 
current
is 
None
(and you’ve reached the end of your list), and your 
while
loop terminates:
while current.next:
current = current.next

---

Data Structures
106
The variable 
current
now holds the last node in your list, so you create a new node and assign it 
to 
current.next
:
current.next = Node(data)
Here is an example of using 
append
to add new nodes to your linked list:
a_list = LinkedList()
a_list.append("Tuesday")
a_list.append("Wednesday")
You can also add the 
__str__
method to your 
LinkedList
class so you can easily print all of the 
nodes in your list:
def __str__ (self):
node = self.head
while node is not None:
print(node.data)
node = node.next
a_list = LinkedList()
a_list.append("Tuesday")
a_list.append("Wednesday")
print(a_list) 
>> Tuesday
>> Wednesday
In Python, 
__str__
is a “magic method.” When you define 
__str__
inside a class, Python calls that 
method when you print the object.
While Python does not have linked lists built into the language, it does have a built- in data struc-
ture called a 
deque, which uses linked lists internally. Using Python’s built- in deque data structure 
allows you to take advantage of a linked list’s efficiency without having to code one yourself.
from collections import deque
d = deque()
d.append('Harry')
d.append('Potter')
for item in d:
print(item)
>> 'Harry'
>> 'Potter'

---