ImmutableJS's lists are collections which are implemented behind the scenes as trees. When you append to an immutable list a new list is returned so the comparison in shouldComponentUpdate() becomes simply a reference comparison between the old and new list (return nextState.list !== this.state.list).
That doesn't help reduce the computational complexity in this instance. After appending, the lists are different, so it renders the component, which starts iterating the children and checking each one in turn to see if it's changed. To reduce the computational complexity you'd need to do something like walking the tree that backs the list instead, so you can ask it "did any of the children under this node change?" which means you can start skipping the comparisons for big chunks of the list. I don't know if react and immutable.js can be combined in this way without significantly rewriting you or components. I suspect not.
