Why are linked lists important, and where are they used?

linkedlists.md

Linked Lists

What is a vector?

std::vector

• One dimensional array

Pointers

Expanding Vector Example

• Cache efficiency of a vector
• Say you have a vector that points to 100 elements
  • What would you do when you want to add 200 more elements to that vector?
  • Bad option: Create a new vector and copy all 300 elements
  • Better option: Add pointer to end of vector to point to the 200 more elements

Memory Allocation in C-based languages

• How to keep track of memory? Use a linked list
• C languages have memory allocation (mem alloc)
• Only higher level languages have collection objects (like arrays and hashes in Ruby?!?)
• i.e. vectors in c++ are in a standard library, but are not a core language feature -Versus java, python, ruby -> vectors are part of the language itself

Local Memory Threads

mem alloc

• Issue: system calls are usually quite slow
  • Would use system calls to get new memory

-In a single thread, could use alloc to release and get new memory, and keep it local

• (Eventually, if memory is not used, can release it back to the system)

-How to keep track of what memory you have access to? With a linked list

Collisions in Hash Tables

Linked lists are also used to alleviate collisions in hash tables i.e. multiple key/value pairs at one index

Real life example:

http://goog-perftools.sourceforge.net/doc/tcmalloc.html