1. A linked list is a non-contiguous section of the memory where each element (i.e. memory cell) in the list holds its own data value AND a pointer referencing to the next element in the list. This makes insertion/deletion O(1), simply change the pointer of the N-1 element to the new cell and direct the new cell's pointer to the next element, but makes traveling the list O(N). A map is a DS where each entry is composed of 2 parts: key and value. the value is entered into a cell whose memory reference is the outcome of a hash function (which is why maps are sometimes called "hashes" or "hash maps(!)"). Entering, getting from a map is O(1), simply calculate the required key's hash and find out if there's something there. There is, however, no notion of traveling a map, nor is there any guarantees about the order of the key-value elements within it. There's also a risk if the hash function is poorly designed one, of a clash. A map doesn't have to be, though it could, in theory, be contiguous. An array, in the Java sense, is a static, contiguous section of the memory. Each element in the array can be accessed in O(1) using a reference to its number in the array (by offsetting the correct number of memory cells from the beginning/end of the array). However, it can't be grown, so, once full, an insertion is O(N)... building a new array of N+1 elements. Deleting is O(1) and traveling, though possible, doesn't make much sense and is O(N). 2. Inner join in SQL is a join operation where the join goes on as long as both tables being joined have values to join. Once a table has run out of values, regardless of the other table, the operation is finished. An outer join runs a join on ALL the values of the first declared table in the join statement (the "outer" table). Where the inner table doesn't have any more values to join, the value is NULL and the operation continues until the outer table runs out of values to join.