Tanushree

  Other names: array list, growable array, resizable array, mutable array Quick reference Average Case Worst Case space O(n) O ( n ) O(n) O ( n ) lookup O(1) O ( 1 ) O(1) O ( 1 ) append O(1) O ( 1 ) O(n) O ( n ) insert O(n) O ( n ) O(n) O ( n ) delete O(n) O ( n ) O(n) O ( n ) A  dynamic array  is an  array  with a big improvement: automatic resizing. One limitation of arrays is that they're  fixed size , meaning you need to specify the number of elements your array will hold ahead of time. A dynamic array expands as you add more elements. So you  don't  need to determine the size ahead of time. Strengths: Fast lookups . Just like arrays, retrieving the element at a given index takes  O(1) O ( 1 )  time. Variable size . You can add as many items as you want, and the dynamic array will expand to hold them. Cache-friendly . Just like arrays, dynamic arrays place items right next to each other in memory, making efficient use of caches. Weak...

  An   in-place   function   modifies data structures or objects outside of its own   stack frame    (i.e.: stored on the   process heap   or in the stack frame of a calling function). Because of this, the changes made by the   function   remain after the call completes. In-place algorithms are sometimes called  destructive , since the original input is "destroyed" (or modified) during the  function  call. Careful: "In-place" does  not  mean "without creating any additional variables!"  Rather, it means "without creating a new copy of the input." In  general , an in-place  function  will only create additional variables that are  O(1) O ( 1 )  space. An  out-of-place   function  doesn't make any changes that are visible to other  function s. Usually, those  function s copy any data structures or objects before manipulating and changing them. In many lang...

  Array slicing   involves taking a subset from an array and   allocating a new array with those elements . In  Python 2.7  you can create a new  list  of the elements in  my_list , from  start_index  to  end_index  (exclusive), like this: my_list [ start_index : end_index ] You can also get everything from  start_index  onwards by just omitting  end_index : my_list [ start_index : ] Careful: there's a hidden time and space cost here!  It's tempting to think of slicing as just "getting elements," but in reality you are: allocating a new  list copying  the elements from the original  list  to the new  list This takes  O(n) O ( n )  time and  O(n) O ( n )  space, where  n n  is the number of elements in the  resulting   list . That's a bit easier to see when you save the result of the slice to a variable: tail_of_list = my_list [ 1 : ] Py...