LinkedLists

Question 1

What is a faster queue than a linked list?

Answer 1

An array deque due to better locality of reference

Question 2

Doubly Linked List

Answer 2

identical to a Singly Linked List except that each node also contains a previous pointer, allowing each node to be aware of both the node before it and after it.

Question 3

Memory locality questions aside, when is a good idea to use a LinkedList?

Answer 3

if insertion and deletion will be heavily utilized. As both have O(1) time

But ofc with this data type you lose search and indexing and range capabilities etc

Question 4

How to reverse linked list iteratively

Answer 4

Technique: update while traversing

function reverse(head) {

If (!head) return null
let prev = null, cur = head, next = head.next

while (cur){
cur.next=prev

prev = cur
cur = next
next = next && next.next 

}

Return prev // because prev will now be the last item that’s not null (bc cur is null) and this prev variable will point to the first item in the now reversed list

}

Question 5

How to detect cycle in a linkedlist

Answer 5

Tortoise and hare technique

By traversing at two speeds, if there is a cycle, traversing will never end and both pointers will eventually point to the same element, otherwise the traversing WILL end

function hasCycle(head) {

if (!head) return false

let slow = head
let fast = head.next

while ( fast) {// you could check fast && slow, but not necessary and that’s at least one more operation
 if (slow === fast) {
   return true}
 slow = slow.next
 fast = fast.next && fast.next.next 
}
return false
}

Question 6

advantage of a double linked list

Answer 6

for remove(Node n ) you can remove a node with just a reference to that node, without having to pass any other arguments

Question 7

LRU cache implementation UML

Answer 7

DLLNode
+constructor()
+remove()

DLLList
\+constructor()
\+removeFirst()
\+append()
- looks like: head  node1  node2  nodeN  tail

LRUCache
\+constructor()
\+get(key)
\+put(key,Val)
-contains map, size, capacity, and dlList (with two dummy nodes head and tail)

the put function will remove the node just after the head (dummy head) if at capacity and append just before the tial.

the get function will only move whatever node is looked up to just before the tail.

Question 8

LRU Cache implementation low level

Answer 8

function DLNode(key = null, val = null ){
this.key = key
this.val = val
this.next = null
this.prev = null 
}
function DLList() {
this.head = new DLNode()
this.tail = new DLNode()
this.head.next = this.tail
this.tail.prev = this.head

this.size=0

}
DLList.prototype.append = function(node /*: DLNode */ {
const lastNode = this.tail.prev // last non dummy node

lastNode.next = node

node. prev = lastNode
node. next = this.tail
this. tail.prev = node

this.size++

}
DLList.prototype.remove(node) {
node.prev.next = node.next
node.next.prev = node.prev

node. prev = null
node. next= null

this.size—
return node
}

//assumes will never get called when there is no data other than dummy nodes
DLList.prototype.removeFirst() {
const firstNode = this.head.next
return this.remove(firstNode)
}

var LRUCache = function(capacity) {
this.capacity = capacity.
this.map = {} // slightly faster than new Object()
this.list = new DLList()
}
LRUCache.prototype.get(key) {
const node = this.map[key]
if (!node) {
return -1
}
this.list.remove(node)
this.list.append(node) // for cache locality reasons it may be better to 1) recreate a new node (which would probably take next adjacent spot in memory) (with the old nodes key and value) and then append that node to the list and 2) use that node to replace the old one in memory in the hasmap
return node.val
}
LRUCache.prototype.put(key,val) {
//first remove node if a node exists with this key
Const n = this.map[key]

if(n){
  this.list.remove(n)
}
else {// if key is new
  if (this.capacity === this.list.size) {
    const removed = this.list.removeFront()
    delete this.map[removed.key]
  }
}
const newN = new DLNode(key, Val)
this.list.append(newN)
this.map[key] = newN

}

Question 9

optimizations for high performant LRU cache

Answer 9

https://medium.com/@udaysagar.2177/fastest-lru-cache-in-java-c22262de42ad

Question 10

List two applications for circular linked list

Answer 10

1) Circularly linked lists have applications to games, for example: keeping track of whose turn it is in an online version of a multi-player board game or to represent the game board in games like Life or Monopoly.
2) In general, circularly linked lists are useful when implementing algorithms for round-robin style scheduling.