A & LL

Question 1

Describe arrays

Answer 1

• A linear data structure used to store collections of elements
• Arrays consist of element, which are the individual pieces of data and stored at an index (usually an incrementing integer that starts with 0).
• Commonly implement several methods for adding and removing elements, including push (adds an element to the end), pop (removes an element from the end), shift (adds an element to the beginning) and unshift (removes an element from the beginning)

Question 2

List common uses for arrays

Answer 2

• Storing collections of elements (vectors, matrices, data tables)
• Implementing more complex data structures (stacks, queues, strings)

Question 3

Describe linked lists

Answer 3

• Linear data structure comprised of a sequence/chain of nodes
• Considered a dynamic data structure and do not need to be contiguous
• Always begin with the “head” node, which is the only entry point to the list and its corresponding elements
• Traversed via pointers (references to another node, or null if at the end of the list)
• Do not end with a node, but rather a node that points to null.
• Nodes can be added or removed to the beginning, end, and before/after any node.

Question 4

List common uses for linked lists

Answer 4

• Complex data structures (stacks and queues)
• Adding dynamic functionality to arrays (easily handle variable sizing, and store data of variable size)
• Making real-time apps that need constant time insertion and deletion

Question 5

What are the tradeoffs between arrays and linked lists?

Answer 5

• Inserting and removing from linked lists doesn’t reorganize the whole list, unlike an array, which is more efficient.
• Linked lists do not need to be contiguous in memory.
• Randomly accessing nodes in linked lists is more difficult than in arrays, which are indexed.
• Linked lists take up more space because they have to store pointers to nodes in addition to just the data.

Question 6

How do you add a node to the beginning of a singly linked list?

Answer 6

• Create a new node
• Set the next property of the new node to the current head of the linked list
• Set the head to the new node

Question 7

Differentiate between singly and doubly linked lists.

Answer 7

• Singly linked lists only go in one direction. There is a single track the list can be traversed in - you start at the head node, and traverse from the root until the last node.
• Doubly linked lists can be traversed forwards or backwards. Nodes on doubly linked lists contain two references, one to the next node and one to the previous one. This also means they take up more memory.

Question 8

How do you prepend one node before another supplied node in a doubly linked list?

Answer 8

• Create a new node
• Set the next property of the new node to point to the supplied node
• Set the previous property of the new node to the previous property of the supplied node
• Go to the previous node of the supplied node and set its next property to the new node
• Set the previous property of the supplied node to the new node

Question 9

How do you remove a supplied node from the middle of a doubly linked list?

Answer 9

• Set the next property of the previous node to the next node
• Set the previous property of the next node to the previous node
• Delete the supplied node