Arrays

Question 1

memory address

Answer 1

the index number of RAM

Question 2

Linked lists

Answer 2

• data structures that overcome problems of space by allocating blocks of memory on demand
• work by storing a series of nodes.
• primary operations in a linked list are insert, remove, and get (find)

Question 3

node

Answer 3

• unit of memory holding a single item in a linked list
• A node can be allocated from anywhere in the memory, it does not have to be next to the previously allocated node. Hence, linked lists are stored in non-contiguous blocks of memory.
• consists of a value and a pointer to the next node in the sequence
• node class is named with a _ (underscore). The underscore simply indicates that the node class is a private class that should not be accessible by anyone else other than the linked list class.

Question 4

singly linked list

Answer 4

• a type of linked list where each node contains one pointer to the next node

Question 5

doubly linked list

Answer 5

-where nodes contain a pointer to the previous node in addition to the next

Question 6

head

Answer 6

• indicates the beginning of the list.

- The head always contains the 1st node

Question 7

insertion

Answer 7

• at the beginning of the list (insertFirst).
• at the end of the list (insertLast).
• anywhere in the list, between 2 nodes (insert, insertAt).

Question 8

insertFirst

Answer 8

• Create a new node item

- Point the head to that new node

Question 9

insertLast

Answer 9

1. Create a new node item
2. Check to see if the list is empty, if it is, then insert the new item as the only item in the list
3. Start at the beginning of the list and move through the list until you reach the end of the list
4. Set the end node’s next pointer to the new node
5. The new node’s next pointer is null (indicating that the new node now is the last node on the list)

Question 10

get

Answer 10

1. traverse the list, comparing the value stored in each node with the value you are searching.
2. When the item is found, return the node.

Question 11

removal

Answer 11

1. delete from the beginning of the list.
2. delete from the end of the list.
3. delete a node between 2 other nodes.

Question 12

delete 1st

Answer 12

if you delete the 1st item in a list, you need to change the head to indicate the new 1st item on the list.

Question 13

end or between

Answer 13

you find the node before the node you are removing and update its next pointer to skip over the removed node.