Linked Lists

Question 1

Basics

Answer 1

• Very similar to an array, but different in how they are stored in memory
• Besides the value of a linked list, a node also has a pointer to the next element:
• The value is stored in some memory slot
• The pointer is stored in the next memory slot to the value (a back-to-back slot). Points to anywhere in memory (not a back-to-back memory slot) that has the value of the next node
• The final node points to a null address, so the memory slot next to the final value is a null address

Question 2

Singly Linked List

Answer 2

• When every node has one pointer to the next node
• Has two properties: value and next
• The first element is referred to as the head
• The last element is known as the tail, whose next property points to null
• Typically only exposes its head to the user

Question 3

Doubly Linked List

Answer 3

• When every node has two pointers, one to the previous node, and the other to the next node
• Has three properties: value, prev, and next
• The first element is referred to the head, whose prev property points to null
• The last element is known as the tail, whose next property points to null
• Exposes its head and tail to the user

Question 4

Circular Linked List

Answer 4

• It has no clear head or tail because its tail points to its head, forming a closed circle
• Can be a singly circular linked list or a doubly circular linked list

Question 5

Space-time complexities 1

Answer 5

• Getting and setting an element depends on the node position and type of linked list:
  * The head: O(1) T, O(1) S
  * The middle: O(N) T, O(1) S
  * The tail: O(N) T in singly, O(1) T in doubly, O(1) S
• Initializing a linked list is a linear operation. It’s O(N) ST
• Built-in operations that traverse a linked list have the same space-time complexities as the traversing operation. It’s O(N) T, O(1) S

Question 6

Space-time complexities 2

Answer 6

• Copying a linked list is a linear operation. It’s O(N) ST
• Inserting and removing a value in a linked list depends on the node position and type of linked list:
  * The head: O(1) T, O(1) S
  * The middle: O(N) to access + O(1) T, O(1) S
  * The tail: O(N) to access + O(1) T in singly, O(1) T in doubly; O(1) S