The Self-Taught Computer Scientist

Data Structures
102
Each node carries a pointer to the next node’s address in the list, connecting all the list elements 
(Figure 10.3). The first element in the linked list, 
a, carries a pointer to memory address 1862, which 
is the location of 
b, the second element in the list. The element b contains a pointer to the location 
of the next node’s memory address, 
c, etc. This design creates a sequence of elements that are all 
mapped together.
When you insert an element into a linked list, your computer does not have to shift any data because 
it has to adjust only two pointers. For example, Figure 10.4 shows what happens when you add the 
element 
f into your list after a.
Your computer changes the pointer for 
a to the memory location of f and adds a pointer in f to the 
next item, 
b (see Figure 10.4). Nothing else needs to change.
There are many different types of linked lists. The linked list in Figure 10.4 is singly linked. A 
singly linked list is a type of linked list with pointers that point only to the next element. In a doubly 
linked list, each node contains two pointers: one pointing to the next node and one pointing to the 
previous node. This allows you to move through a doubly linked list in either direction (Figure 10.5).
pointer
0x41860
“a”
0x41861 0x41862 0x41863 0x41864 0x41865 0x41866
“b”
“c”
“d”
“e”
Figure 10.3: Pointers map the nodes of a linked list.
change one
change two
0x41860
“a”
“f”
0x41861 0x41862 0x41863 0x41864 0x41865 0x41866
“b”
new
element
“c”
“d”
“e”
Figure 10.4: Inserting an element into a linked list requires 
adjusting two pointers.
0x41860
“a”
“f”
0x41861 0x41862 0x41863 0x41864 0x41865
“b”
“c”
“d”
“e”
Figure 10.5: A doubly linked list has pointers that go 
in two directions.

---