Linked Lists

Question 1

Where is data read from?

Answer 1

A data source

Question 2

Where is data stored to?

Answer 2

A data sink

Question 3

Why is the way we store data in memory important?

Answer 3

We want the fastest possible access to data while using the least amount of memory

Question 4

What are the options for storing data in memory?

Answer 4

Array or linked list

Question 5

What are the advantages of an array?

Answer 5

Elements are contiguous, faster access to elements

Question 6

What are the disadvantages of an array?

Answer 6

Can’t be resized

Question 7

What are the trade-offs of the an array?

Answer 7

Allocating an: oversized array is a waste of memory, undersized causes error.

Question 8

What are the advantages of a linked list?

Answer 8

No need to resize, use only as much memory as needed, elements can be inserted/removed/shifted anywhere

Question 9

What are the disadvantages of a linked list?

Answer 9

Elements are not contiguous, access to elements is slower

Question 10

What does a singly linked list consist of?

Answer 10

Pointer to head, pointer to tail (optional), set of nodes containing element data and pointer to next node

Question 11

What value should uninitialized pointers have?

Answer 11

Zero or null

Question 12

What are some problems with basic linked lists?

Answer 12

Same structure mixes element data with list data, each element is hard-coded to point to a specific other element

Question 13

Why separate list nodes from list data?

Answer 13

Encapsulation, reuse

Question 14

How do we insert elements into a list?

Answer 14

Shifting pointer values

Question 15

Which four cases do we consider when inserting nodes into a linked list?

Answer 15

The element is added to an empty list, the element is added in the first position, middle position, and last position

Question 16

How do we remove an element from the list?

Answer 16

Shift pointer values and deallocate the memory

Question 17

Which six cases do we consider when removing nodes from a linked list?

Answer 17

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

Question 18

When cleaning up a list, remember to..

Answer 18

Deallocate nodes, only deallocate data if it own’t be used again

Question 19

What is different about a doubly-linked list?

Answer 19

Pointer to head and tail, each node has a pointer forward and backwards

Question 20

What is a dynamic array?

Answer 20

An array that is dynamically allocated

Question 21

Why use a dynamic array?

Answer 21

They can be resized as needed to accommodate more or less data

Question 22

What are the two kinds of arrays (module context)

Answer 22

Static arrays, dynamic arrays

Question 23

What are the two kinds of data that can be stored in an arrray?

Answer 23

Actual data or pointers to the data

Question 24

What is a function pointer?

Answer 24

Pointer variable that stores the address of a function’s code inside the code segment

Question 25

Why use function pointers?

Answer 25

They allow us to choose which function to execute at runtime, but the functions must have the same prototype