Basic DS Flashcards
What are the key 3 differences between an array and a list?
An array is of static size, while a list has a dynamic size. Also, all indices of an array are accessible with O(1) . Lastly, you can’t have any implicit null space between elements in a list
What is a link list?
A list that consists of nodes with a data field and a pointer to the next node
What is a singly-linked list?
A list where each node points to the next in a single direction
What special nodes are included in a linked list field to allow traversal?
A head node @ the beginning or a tail node @ the end
How do doubly-linked nodes and singly-linked nodes differ?
doubly-linked nodes have a previous feild
What special cases arise for the list add/contains method?
null parameter, which is signalled with a IllegalArgumentException
What special cases arise for the remove method?
invalid position & empty list which are signalled by IndexOutOBoundsException
What fields does an array implemented list have in general?
An array that holds the data and a numItems feild
How does a circularly list node differ from a regular linked list?
A circularly linked node’s last node points to the first & vice versa if it is also doubly-linked
What type is a stack?
Last-In-First-Out (LIFO)
What three unique operations does a stack have?
- push: adds to the top of the stack
- pop: remove and returns the top of the stack
- peek: returns the top of the stack
What type is a queue?
First-In-First-Out (FIFO)
What two operations does a queue have?
- enqueue: add to the rear
- dequeuer: removes from the front
To implement a queue with a linked list, what must be done to make the methods efficient?
Create a circularly linked list
What fields are included in the linked list constructor?
A reference to a header node and/or tail pointer and a numItems variable
What type of variables ARE the members of a list with the array implementation vs. the linked list implementation?
arbitrary object, list node object that holds an arbitrary object (with a next field)
What iterator must be used to traverse a list?
An indirect iterator, since the array is not accessible by the iterator class since the data is only accessible through the list field in the iterator class
What main problem does a doubly linked node fix?
The need to traverse to the node just before n
What special cases have to be dealt with when removing a node from a doubly linked list?
When the node is either the first or last node. Thiss can be fixed by making it circular
What special case needs to be dealt with in the remove method of a circular list?
When removing the header node the header pointer needs to be adjusted
What is one main disadvantage of a doubly linked list?
It takes up more memory since each node has more fields
What does pop and peek throw?
EmptyStackException
What does dequeuer throw?
EmptyQueueException
What fields are in the constructor of the array implementation of a stack?
- ) array of objects
- )size constant
- )numItems
What location is the most efficient to have the top of the stack?
The end of the array so data members don’t have to be shifted
For a DS that implements an array what options are there to expand the array?
shadow array (O(1)) and creating a larger array and copying the values
Why is the top of the linked list implementation of a stack at the beginning (@header node) rather than the end?
Because the header node can directly access the top without traversing
What is the problem with the naiive array implementation of the queue?
To remove from the front, the members have to be shifted to array[0]. This is solved by keeping a front and rear index field.
What index points to the rear where elements are added in a queue?
The rear index
When the circular array is expanded (rear & front index are adjacent) where are the new values copied to?
- All indexes from the front index to the end of the array are copied to the same front index
- Add values from the beginning of the array to the rear index after the first sequence of insertions
What three fields are in the LList implementation of a queue?
The front node
The rear node
numItems
What is the advantage of the array implementation of a stack and queue?
The indices point to the data themselves and not list nodes (this goes for any array implementation)
