Why is appending to a list bad?

by

The key is that x :: somelist does not mutate somelist, but instead creates a new list, which contains x followed by all elements of somelist. This can be done in O(1) time because you only need to set somelist as the successor of x in the newly created, singly linked list.

If doubly linked lists were used instead, x would also have to be set as the predecessor of somelist‘s head, which would modify somelist. So if we want to be able to do :: in O(1) without modifying the original list, we can only use singly linked lists.

Regarding the second question: You can use ::: to concatenate a single-element list to the end of your list. This is an O(n) operation.

List(1,2,3) ::: List(4)

More Related Contents:

  1. Apache Spark: map vs mapPartitions?
  2. What’s the (hidden) cost of Scala’s lazy val?
  3. Does Scala support tail recursion optimization?
  4. SET vs. SELECT – What’s the difference?
  5. SET vs. SELECT – What’s the difference?
  6. What is the best way to set a register to zero in x86 assembly: xor, mov or and?
  7. Why are loops always compiled into “do…while” style (tail jump)?
  8. Enhanced REP MOVSB for memcpy
  9. Why is Skylake so much better than Broadwell-E for single-threaded memory throughput?
  10. How to speed up A* algorithm at large spatial scales?
  11. Branch alignment for loops involving micro-coded instructions on Intel SnB-family CPUs
  12. Why is XCHG reg, reg a 3 micro-op instruction on modern Intel architectures?
  13. What methods can be used to efficiently extend instruction length on modern x86?
  14. What is the difference between Scala’s case class and class?
  15. Should I use multiplication or division?
  16. Lost Cycles on Intel? An inconsistency between rdtsc and CPU_CLK_UNHALTED.REF_TSC
  17. postgresql COUNT(DISTINCT …) very slow
  18. Java compile speed vs Scala compile speed
  19. Why should recursion be preferred over iteration?
  20. LCP time between LightHouse and Performance – Google Chrome
  21. simplest tool to measure C program cache hit/miss and cpu time in linux?
  22. Why is division more expensive than multiplication?
  23. Should a developer aim for readability or performance first? [closed]
  24. Find prime numbers using Scala. Help me to improve
  25. Return address prediction stack buffer vs stack-stored return address?
  26. When should we use prefetch?
  27. Relative performance of x86 inc vs. add instruction
  28. Efficient sse shuffle mask generation for left-packing byte elements
  29. Performance of function slice parameter vs global variable?
  30. How to find Cumulative Layout Shift problems if Page Speed Insights says one thing and Search Console says another

Leave a Comment