Generally you build the new list using the tail of the old list (which is unchanged), your inserted value, and each of the values in front inserted onto that. S

Generally you build the new list using the tail of the old list (which is unchanged), your inserted value, and each of the values in front inserted onto that. So, immutability is preserved. Any existing references will not see their values changed. And the new references will share some memory with the old ones (how much depends on where in the list the value was inserted). You can learn more in Okasaki's great book: http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 http://www.amazon.com/Purely-Functional-Structures-Chris-Oka...