¿Qué es la estructura de datos inmutable?

Tu primera explicación es correcta. Cuando tiene datos inmutables, no puede cambiar (mutar) estos datos. Si desea agregar algo, debe crear nuevos datos con los cambios.

¿Por qué es esto bueno?
Por supuesto, necesitará asignar nueva memoria, que parece ser menos eficiente. Pero gana la posibilidad de un enfoque de concurrencia más fácil. Si no se permite que ningún subproceso, bifurcación o cualquier otra cosa cambie los datos, todos estos subprocesos, bifurcaciones, etc. pueden compartir estos datos. Así es como funciona la simultaneidad de Erlang o Elixir. Comparten datos y si algo necesita ser cambiado, se crean nuevos datos. Además, la recolección de basura se puede optimizar para eso

Otras respuestas han dado buenos resúmenes de cómo funcionan las estructuras de datos inmutables. Sin embargo, esto es solo la punta del iceberg. La inmutabilidad es solo una elección. Puede o no ser el correcto según sus casos de uso. La programación funcional favorece la inmutabilidad. La programación imperativa favorece las mutaciones. Para tener una idea de por qué este es el caso, debe comprender conceptos como los efectos secundarios, la pureza, la persistencia y la pereza. Encontrará que la inmutabilidad va de la mano con estos. Esto también revelará por qué las mutaciones son favorecidas en contextos imperativos. He escrito una publicación introductoria sobre esto aquí: Introducción a Immutable.js y los conceptos de programación funcional

Es posible que haya escuchado que una cadena es inmutable, mientras que un objeto buffer de cadena es mutable. La diferencia es que cada vez que desea cambiar el valor de un objeto buffer de cadenas, el objeto señala los cambios en la misma ubicación de memoria, mientras que en el caso de la cadena, cada vez que intenta hacer un cambio en el valor, se almacena el nuevo valor en una nueva ubicación de memoria y el objeto ahora apunta a la nueva ubicación de memoria con los contenidos de la antigua ubicación de memoria sin cambios. Por lo tanto inmutable y mutable.

Los objetos inmutables no pueden cambiar, si desea cambiarlos, debe crear otros nuevos.
La lista inmutable no puede cambiar, no puede agregar, eliminar o reasignar sus elementos. Si desea cambiarlos, debe crear nuevas listas y descartar, agregar o reemplazar sus elementos.

Como han dicho otros, debe hacer una copia de toda la estructura de datos: no hay elementos que se agreguen o cambien. Sin embargo, esto te llevaría a creer que esto es terriblemente ineficiente, ¿verdad? Aquí es donde entran en juego las estructuras de datos persistentes.

Imagina que tienes el siguiente código:

a = [1, 2, 3]
b = [4, 5, 6]
c = a ++ b

La concatenación en la última línea no copiará ambas listas, como supondría. Dado que estas son listas enlazadas individualmente, terminan luciendo así:

a: [1] -> [2] -> [3] -> final
b: [4] -> [5] -> [6] -> final
c: [1] -> [2] -> [3] -> b

Entonces, solo se copia la lista “a”, porque todo lo que tiene que hacer para alcanzar la semántica anterior es cambiar el último elemento de “a” para apuntar a la lista “b” (y “cambiar” significa “copiar”, por lo que tiene que copiar “a”). Como no hay mutación, puede hacerlo de forma segura sin preocuparse de que alguien cambie “b” y, por lo tanto, cambie “c”; puede encadenarlos de manera segura de esta manera.

Esta es también la razón por la cual agregar o eliminar elementos en la parte frontal es muy eficiente: no es necesario copiar nada, ya que el nuevo elemento solo está hecho para señalar los elementos antiguos (ya que, una vez más, puede estar seguro de que no cambiarán por alguna otra parte del programa).