Linked Lists Flashcards
Where is data read from?
A data source
Where is data stored to?
A data sink
Why is the way we store data in memory important?
We want the fastest possible access to data while using the least amount of memory
What are the options for storing data in memory?
Array or linked list
What are the advantages of an array?
Elements are contiguous, faster access to elements
What are the disadvantages of an array?
Can’t be resized
What are the trade-offs of the an array?
Allocating an: oversized array is a waste of memory, undersized causes error.
What are the advantages of a linked list?
No need to resize, use only as much memory as needed, elements can be inserted/removed/shifted anywhere
What are the disadvantages of a linked list?
Elements are not contiguous, access to elements is slower
What does a singly linked list consist of?
Pointer to head, pointer to tail (optional), set of nodes containing element data and pointer to next node
What value should uninitialized pointers have?
Zero or null
What are some problems with basic linked lists?
Same structure mixes element data with list data, each element is hard-coded to point to a specific other element
Why separate list nodes from list data?
Encapsulation, reuse
How do we insert elements into a list?
Shifting pointer values
Which four cases do we consider when inserting nodes into a linked list?
The element is added to an empty list, the element is added in the first position, middle position, and last position
How do we remove an element from the list?
Shift pointer values and deallocate the memory
Which six cases do we consider when removing nodes from a linked list?
List is empty, element removed is the only element in the list, element is not found in list, element is removed from first, middle, last
When cleaning up a list, remember to..
Deallocate nodes, only deallocate data if it own’t be used again
What is different about a doubly-linked list?
Pointer to head and tail, each node has a pointer forward and backwards
What is a dynamic array?
An array that is dynamically allocated
Why use a dynamic array?
They can be resized as needed to accommodate more or less data
What are the two kinds of arrays (module context)
Static arrays, dynamic arrays
What are the two kinds of data that can be stored in an arrray?
Actual data or pointers to the data
What is a function pointer?
Pointer variable that stores the address of a function’s code inside the code segment
Why use function pointers?
They allow us to choose which function to execute at runtime, but the functions must have the same prototype
