33813990
Description
Flashcards by Malachy Moran-Tun, updated more than 1 year ago
More
| Question | Answer |
| What is a List? | > Abstract data type consisting of a number of items > The same items can occur more than once > Sequenced, so you can refer to the first to last element > Whilst list can refer to dynamic or static lists (the latter being arrays), they are usually dynamic unless specified |
| What Abstract Data Structures can be Implemented using a List? | > Queues > Stacks > Trees |
| What Operations can be Performed on a List? | > isEmpty() - Returns true if the list is empty, false if not > append(item) - Adds a new item to the end of the list > remove(item) - Removes the first occurrence of an item > search(item) - Returns true if a specific item is found in the list, false if not > length() - Returns the number of items > index(pos, item) - Inserts a new items at the specified position > pop() - Removes the last item in the list and returns it > pop(pos) - Removes the item at the specified position and returns it |
| How would an Item be Inserted into a Static List? | 1. Check to see if the list is already full, if it isn't proceed, if it is, quit (and print a message) 2. Determine where the new item needs to be inserted 3. Starting at the end of the list, move all the other items up to where the item needs to be inserted up one 4. Insert the new item in the correct place |
| How would an Item be Deleted from a Static List? | 1. Replace the item with a blank value 2. Move up all items, until the blank value, by copying them to the previous spot 3. Replace the last element (which is duplicated) with a blank |
| What is a Linked List? | > Dynamic data structure > Used to hold an ordered sequence > Items in the sequence are not (necessarily) held in contiguous (consecutive) data locations, or even in the order in which they occur in the sequence > Each item in the list is called a node > Each node contains a data field, and a link or pointer field > The data field holds the node's data, the link field holds the next item's memory address > If the link field is null, it indicates that there are no further items > The list needs a pointer variable, which contains the memory address of the first node in the list |
| How would you Insert an Item into a Linked List? | 1. Store the new item in the node pointed to by the "nextfree" variable 2. Determine, by following the links, where the new item should be inserted 3. Change the "nextfree" variable to point to the next free location 4. Change the new item's pointer to point to the appropriate item 5. Change the item before the new item's pointer to point to the new item (this sounds long winded and complicated, but it's really not, just hard to explain; certain steps can be in a different order too, as long as the result is the same) Pseudocode in textbook |
| How would you Delete an Item from a Linked List? | 1. Follow the pointers until the item to be deleted is found 2. Change the item before the item to be deleted's pointer to the item after the one to be deleted 3. Change the item to be deleted's pointer to the "nextfree" variable's value 4. Change the "nextfree" variable to point to the item to be deleted (this means that the item will be overwritten when necessary) (this sounds long winded and complicated, but it's really not, just hard to explain, once again) Pseudocode in textbook |
Want to create your own Flashcards for free with GoConqr? Learn more.