The Self-Taught Computer Scientist

base address: The memory location of the first element in an array.
one- dimensional array: An array where you access each element in the array by an integer index.
multidimensional array: An array where you access each element using an index tuple.
overallocation: Reserving more memory for a list than what it would strictly need and keeping 
track of how many elements the list is storing and how much unused space the list has.
set: A data structure that cannot contain duplicate elements.
Challenge
1. 
Given an array called 
an_array
of non- negative integers, return an array consisting of all the 
even elements of 
an_array
, followed by all the odd elements of 
an_array
.

---

10
Linked Lists
Learning to write programs stretches your mind and helps you think better [and] creates 
a way of thinking about things that I think is helpful in all domains.
Bill Gates, Co- founder, Microsoft
A linked list is another implementation of the list abstract data type. Like an array, you can append, 
prepend, search for, and delete items in a linked list. However, elements in a linked list do not have 
indexes because your computer does not store the items in a linked list in sequential memory locations. 
Instead, a linked list contains a chain of nodes, with each node holding a piece of data and the next 
node’s location in the chain. The data in each node that stores the next node’s location in the linked 
list is called a pointer. The first node in a linked list is called the head. The last element in a linked list 
often contains a pointer that points to 
None
, so you know it is the last node in the list (Figure 10.1).
Unlike an array, your computer can store the nodes in a linked list in nonconsecutive memory 
locations (Figure 10.2).
In Figure 10.2, your computer stores the character 
a at the memory location 41860. Your computer 
does not have to store the next element in the list, 
b, at the next sequential memory location (41861). 
Instead, your computer can store 
b anywhere in memory. In this case, your computer is storing it at 
memory location 41862.
Head
None
a
b
c
Figure 10.1: A linked list is a chain of nodes.
0x41860
“a”
0x41861 0x41862 0x41863 0x41864 0x41865
“b”
“c”
“d”
“e”
0x41866
Figure 10.2: A linked list does not need to store nodes 
in consecutive memory locations.

---