Fichas
Lists
Fichas del conjunto (42)
- 1define a listlist implies that there is a positional ordering
- 2operations performed on listsget(i) // Returns the i-th element (but doesn’t remove it)
set(i,e) // Replaces the i-th element with e
add(i,e) // Inserts element e into the i-th position
add(e) // Inserts element e (e.g. at the end of the list)
remove(i) // Removes the i-th element from list
remove(e) // Removes element e from the list (if it is there)
clear() // Empties the list.
isEmpty() // Returns true if empty, false if not empty.
size() // Returns number of elements in the list - 3what's the extra property of array liststhe elements are squeezed into the lowest indices possible so that there are no holes
- 4what's the difference between length and size?size is the number of elements in the array, length (also called capacity) is the number of spots.
capacity is always >= size - 5get(i) alg arr lget(i)
if (i >= 0) & (i < size)
return a[i] - 6set(i) alg arr lset(i,e)
if (i >= 0) & (i < size)
a[i] = e - 7add(i, e) alg arr l
- 8remove(i) alg arr l
- 9what is fast and what is slow with array lists?Adding to or removing from near the back end of the list is fast since few shift operations are necessary.
From the front is slow. - 10define the Java ArrayList classimplements the various methods such as we discussed and uses an array as its underlying data structure
- 11how do you construct an ArrayList object? what's to watch out for?ArrayList shapes = new ArrayList();
the generic type needs to be a reference type; it cannot be a primitive type.
(e.g. use the wrapper class Integer) - 12How do you access elements in the array list?NOT using a[i] cuz we don't know the underlying array.
USING get or set or other methods! - 13Time complexity for array lists?add and remove from the front is O(n) slow
get and set in constant time - 14what does an ArrayList object look like?
- 15define a linked list define a list nodeeach element in the list is referenced by a list node
A linked list node is an object that contains:
- a reference to an element of a list
- a reference to the next node in the linked list.
class SNode{
T element;
SNode next;
} - 16define head and taillinked list has variables head and tail which reference the first and last node, respectively
If there is only one node in the list, then head and tail point to the same node. - 17basic skeleton of a SLinkedList class
- 18suppose we have a linked list with size = 4. How many objects do we have in total? how many for an array list?We have the four SNode objects. We have the four elements (objects of type Shape, say) that are referenced by these nodes. We also have the SLinkedList object which has the head and tail references. So this is 9 objects in total.
(for an arraylist, 6) - 19important difference between array lists and linked listslinked list nodes can be anywhere in memory (no notion of running out of room)(but no constant time access to elements), whereas the underlying array in array list is a block of consecutive locations in memory
- 20s l l addFirst(e) alg and time complexityconstant amount of time
- 21s l l removeFirst() alg
- 22s l l addLast(e) alg
- 23s l l removeLast() alg and time complexityrequires about size steps.
- 24computational complexity of arraylist and linked list methods
- 25define nodes of doubly linked listsEach node of a doubly linked list has two links rather than one, namely references to the previous node in the list and to the next node in the list. These reference variables are typically called prev and next
- 26skeleton for DLinkedList class
- 27advantage of DLinked lists over SLinked listsdoubly linked lists allows us to quickly access elements near the back of the list
- 28removeLast() alg doubly l l
- 29what to watch out for in d l l and solutionthe edge cases are the first and last elements
head.prev and tail.next will be null
To avoid such errors, it is common to define doubly linked lists by using a “dummy” head
node and a “dummy” tail node, instead of head and tail reference variables. - 30skeleton for DLinkedList class with dummy nodes
- 31how many objects for a d l l of 4 elements
- 32d l l getNode(i) alg for get( i ){ node = getNode(i) return node.element }
- 33faster version of getNode(i) d l l
- 34remove(i) alg d l l
- 35time complexity remove(i) d l ltakes size/2 operations in the worst case so O(N)
- 36define the Java LinkedList classLinkedList class which is implemented as a doubly linked list. Like the ArrayList class, it uses a generic type which is write as T below.
LinkedList list = new LinkedList(); - 37time complexity for methods on the 3 kinds of lists
- 38implementation of enhanced for loop for a linked list
- 39what's the space complexity of different kinds of lists?Array lists use the least amount of total space since they require just one reference for each element of the list.
Singly linked lists take twice as much space as array lists, since for each element in a singly linked lists, we require a reference to the element and a reference to the next node in the list.
Doubly linked lists require three times as much space as array lists, because they require a reference to each element and also references to the previous and next node.
BUT they all require O(N) space. - 40define a shallow copy of a linked list
- 41define a deep copy of a linked list
- 42how do you make a shallow copy of a linked list?Java LinkedList class has a clone method
Información
- Descripción
- Computer Science Fichas sobre Lists, creado por Virginie Gagné el 18/04/2022.
- Creado por
- Virginie Gagné
- Visitas
- 1
- Valoración