LinkedLists

Question 1

what is a linkedlist

Answer 1

• a collection of nodes and data is stored in the Node objectl
• connections between nodes is done by having each node point to the next node in the list
• data is NOT stored contiguously like in an arraylist/array

Question 2

SLL with head & tail pointers
- adding to the front
- adding to the back
- adding to elsewhere
- removing from the front
- removing from the back
- removing from elsewhere

Answer 2

• adding to the front: O(1)
• adding to the back: O(1)
• adding to elsewhere: O(n)
• removing from the front: O(1)
• removing from the back: O(n)
• removing from elsewhere: O(n)

Question 3

DLL with head & tail pointers
- adding to the front
- adding to the back
- adding to elsewhere
- removing from the front
- removing from the back
- removing from elsewhere

Answer 3

DLL with head & tail pointers
- adding to the front: O(1)
- adding to the back: O(1)
- adding to elsewhere: O(n)
- removing from the front: O(1)
- removing from the back: O(1)
- removing from elsewhere: O(n)

Question 4

CLL with head (usually doesn’t include a tail pointer)
- adding to the front
- adding to the back
- adding to elsewhere
- removing from the front
- removing from the back
- removing from elsewhere

Answer 4

• adding to the front: O(1)
• adding to the back: O(1)
• adding to elsewhere: O(n)
• removing from the front: O(1)
• removing from the back:O(n)
• removing from elsewhere: O(n)

Question 5

how to add to the front of a CLL

Answer 5

• create a new node right after the head
• copy head data over to the new node
• override head data to the new data

Question 6

how to add to the back of a CLL

Answer 6

• create a new node right after the head
• copy head data over to the new node
• override head data to the new data
• set head to the new node (at index 1)

Question 7

how to remove from the front of a CLL

Answer 7

• move the data from head.next into the head
• remove the second node from the list

Question 8

how to remove from the back of a CLL

Answer 8

• traverse to the node before the last node and perform removal operation like in SLL