The Self-Taught Computer Scientist

doubly linked list: A type of linked list where each node contains two pointers: one pointing to 
the next node and one pointing to the previous node, which allows you to move through a doubly 
linked list in either direction.

---

Data Structures
112
circular linked list: A type of linked list where the last node points back to the first node, which 
allows you to go from the last element of the list back to the front of the list.
cycle: When any node in a linked list points back to a previous node.
random access: When you can access data randomly in constant time.
Challenges
1. 
Create a linked list that holds the numbers from 1 to 100. Then, print every node in your list.
2. 
Create two linked lists: one that contains a cycle and one that doesn’t. Make sure each one has 
a 
detect_cycle
method to see if it has a cycle. Call 
detect_cycle
on each list.

---

11
Stacks
If you want to create and be a visionary, you’re probably going to be working with technology 
in some way.
Steph Curry
A stack is an abstract data type and a linear data structure that allows you to remove only the most 
recent element you added. You can imagine a stack as a pile of books or dishes. In a pile of books, 
you can add or remove only the top book. To reach the third book in a pile of books, you must first 
remove all the books above it.
A stack is an example of a last- in, first- out (LIFO) data structure. A last- in, first- out data structure 
is a data structure where the last item you put into the data structure is the first item to come out of 
it. Because you can access its contents one by one only, a stack is also an example of a limited- access 
data structure: a type of data structure that forces you to access its information in a particular order.
Stacks have two primary operations: pushing and popping (Figure 11.1). Pushing an item onto 
a stack means putting a new item in it. Popping an item from a stack means removing the last item 
from it. Stacks can also have additional operations, such as peeking, which means looking at the top 
element in a stack without removing it.
Stacks can be bounded or unbounded. A bounded stack is a stack that limits how many items you 
can add to it, while an unbounded stack is a stack that does not limit how many elements you can 
add to it. If you are still confused about the difference between an abstract data type and a data struc-
ture, a stack might help you understand the difference. The stack abstract data type describes the idea 
of a data structure that only allows you to access the most recent item you put on it. However, there 
are several different ways to create a data structure like this. For example, you can create a stack by 
defining a class that internally uses either a linked list or an array to track the stack’s items. When you 
are writing the code for a stack using either an array or a linked list, you’ve moved from the abstract 
idea of a stack to a data structure: the actual implementation of an abstract data type.

---